UVA 441 using python

#   MH RIYAD
#   Daffodil Intl. Univarsity
import functools

printf = functools.partial(print, end="")
lis = list()
li = list()
vec = list()
a = 0
flag = False


def call( n ):
 
    if len(vec)==6:
        for i in range (0,6):
            if i == 0:
                printf(vec[i])
            else:
                printf("",vec[i])
        print("")
        return
  
    if n>=a:
        return
    vec.append(lis[n])
    call(n+1)
    vec.pop()
    call(n+1)
   
       
if __name__ == "__main__":
   
    while True:
   
       
        li = list(map(int ,input().split()))
        a = li[0]
        if a==0:
            break
        if flag == True:
            print("\n")
        flag = True
       
        for i in range(1,len(li)):
            lis.append(li[i])
        #print(lis," ",a)
       
        call(0)
        del lis[:]
        del vec[:]
        del li[:]

Selection Sort in python

Time Complexity:O(n*n)
a=[5,4,3,2,1]

for i in range(0,4):
    x=i
    for j in range(i+1,5):
       
        if (a[x]>a[j]):
            x=j
           
    temp=a[i]
    a[i]=a[x]
    a[x]=temp

           
       
print(a)

Difference between training set and Cross validation in weka?

Changing the test option to “use training set” changes the nature of the experiment and the results are not really comparable. This change tells you how well the model performed on the data to which was trained (already knows the answers).

This is good if you are making a descriptive model, but not helpful if you want to use that model to make predictions. To get an idea at how good it is at making predictions, we need to test it on data that it has not “seen” before where it must make predictions that we can compare to the actual results. Cross validation does this for us .With cross-validation, we divide it just once, but we divide into, say, 10 pieces. Then we take 9 of the pieces and use them for training, and the last piece we use for testing. Then, with the same division, we take another 9 pieces and use them for training and the held-out piece for testing. We do the whole thing 10 times, using a different segment for testing each time. In other words, we divide the dataset into 10 pieces, and then we hold out each of these pieces in turn for testing, train on the rest, do the testing and average the 10 results. That would be "10-fold cross-validation".

BLOOM'S TAXONOMY

Bloom’s Taxonomy is a classification system developed in 1956 by education psychologist Benjamin Bloom to categorize intellectual skills and behavior important to learning. Bloom identified six cognitive levels: knowledge, comprehension, application, analysis, synthesis, and evaluation, with sophistication growing from basic knowledge-recall skills to the highest level, evaluation.

History of Bloom’s Taxonomy

Bloom’s Taxonomy was created in 1948 by psychologist Benjamin Bloom and several colleagues. Originally developed as a method of classifying educational goals for student performance evaluation, Bloom’s Taxonomy has been revised over the years and is still utilized in education today. The original intent in creating the taxonomy was to focus on three major domains of learning: cognitive, affective, and psychomotor. The cognitive domain covered “the recall or recognition of knowledge and the development of intellectual abilities and skills”; the affective domain covered “changes in interest, attitudes, and values, and the development of appreciations and adequate adjustment”; and the psychomotor domain encompassed “the manipulative or motor-skill area.” Despite the creators’ intent to address all three domains, Bloom’s Taxonomy applies only to acquiring knowledge in the cognitive domain, which involves intellectual skill development.

The original Bloom’s Taxonomy contained six developmental categories: knowledge, comprehension, application, analysis, synthesis, and evaluation. The first step in the taxonomy focused on knowledge acquisition and at this level, students recall, memorize, list, and repeat information. In the second tier, students classify, describe, discuss, identify, and explain information. Next, students demonstrate, interpret, and write about what they’ve learned and solve problems. In the subsequent step, students compare, contrast, distinguish, and examine what they’ve learned with other information, and they have the opportunity to question and test this knowledge. Then students argue, defend, support, and evaluate their opinion on this information. Finally, in the original model of Bloom’s Taxonomy, students create a new project, product, or point of view.

 Knowledge

 Comprehension

 Application

Analysis

 Synthesis

Evaluation

In the 1990s, one of Bloom’s students, Lorin Anderson, revised the original taxonomy. In the amended version of Bloom’s Taxonomy, the names of the major cognitive process categories were changed to indicate action because thinking implies active engagements. Instead of listing knowledge as a part of the taxonomy, the category is divided into different types of knowledge: factual, conceptual, procedural, and metacognitive. This newer taxonomy also moves the evaluation stage down a level and the highest element becomes “creating.”

Category	Examples, key words (verbs), and technologies for learning (activities)
Remembering: Recall or retrieve previous learned information.	Examples: Recite a policy. Quote prices from memory to a customer. Recite the safety rules. Key Words: defines, describes, identifies, knows, labels, lists, matches, names, outlines, recalls, recognizes, reproduces, selects, states Technologies: book marking, flash cards, rote learning based on repetition, reading
Understanding: Comprehending the meaning, translation, interpolation, and interpretation of instructions and problems. State a problem in one's own words.	Examples: Rewrite the principles of test writing. Explain in one's own words the steps for performing a complex task. Translate an equation into a computer spreadsheet. Key Words: comprehends, converts, defends, distinguishes, estimates, explains, extends, generalizes, gives an example, infers, interprets, paraphrases, predicts, rewrites, summarizes, translates Technologies: create an analogy, participating in cooperative learning, taking notes, storytelling, Internet search
Applying: Use a concept in a new situation or unprompted use of an abstraction. Applies what was learned in the classroom into novel situations in the work place.	Examples: Use a manual to calculate an employee's vacation time. Apply laws of statistics to evaluate the reliability of a written test. Key Words: applies, changes, computes, constructs, demonstrates, discovers, manipulates, modifies, operates, predicts, prepares, produces, relates, shows, solves, uses Technologies: collaborative learning, create a process, blog, practice
Analyzing: Separates material or concepts into component parts so that its organizational structure may be understood. Distinguishes between facts and inferences.	Examples: Troubleshoot a piece of equipment by using logical deduction. Recognize logical fallacies in reasoning. Gathers information from a department and selects the required tasks for training. Key Words: analyzes, breaks down, compares, contrasts, diagrams, deconstructs, differentiates, discriminates, distinguishes, identifies, illustrates, infers, outlines, relates, selects, separates Technologies: Fishbowls, debating, questioning what happened, run a test
Evaluating: Make judgments about the value of ideas or materials.	Examples: Select the most effective solution. Hire the most qualified candidate. Explain and justify a new budget. Key Words: appraises, compares, concludes, contrasts, criticizes, critiques, defends, describes, discriminates, evaluates, explains, interprets, justifies, relates, summarizes, supports Technologies: survey, blogging
Creating: Builds a structure or pattern from diverse elements. Put parts together to form a whole, with emphasis on creating a new meaning or structure.	Examples: Write a company operations or process manual. Design a machine to perform a specific task. Integrates training from several sources to solve a problem. Revises and process to improve the outcome. Key Words: categorizes, combines, compiles, composes, creates, devises, designs, explains, generates, modifies, organizes, plans, rearranges, reconstructs, relates, reorganizes, revises, rewrites, summarizes, tells, writes Technologies: Create a new model, write an essay, network with others

Bloom’s Taxonomy in the Classroom

Bloom’s Taxonomy can be used across grade levels and content areas. By using Bloom’s Taxonomy in the classroom, teachers can assess students on multiple learning outcomes that are aligned to local, state, and national standards and objectives. Within each level of the taxonomy, there are various tasks that move students through the thought process. This interactive activity demonstrates how all levels of Bloom’s Taxonomy can be achieved with one image.

In order for teachers to develop lesson plans that integrate Bloom’s Taxonomy, they write their lessons in the language that focuses on each level. The United States Geological Survey provides a list of verbs for each level of Bloom’s Taxonomy for teachers to use when developing lesson plans. (Although the list is designed for environmental science teachers, the examples will work for any discipline.)

uva 11747 - Heavy Cycle Edges solution

/*********************************   MH RIYAD  *************************************/
#include <bits/stdc++.h>
#include<unordered_map>
#include<iostream>
#define  pb     push_back
#define  MAX    1000006
#define  mod    100000007
#define  read   freopen("input.txt","r",stdin);
#define  write  freopen("output.txt","w",stdout);
#define  inf   (1<<30)
using namespace std;
typedef long long ll ;
typedef unsigned long long ull ;

struct nod
{
    int a,b,w;
} ary[1002];
int node,edge,par[1002];
vector<int>ans;

bool cmp(nod  m,nod n)
{
    return m.w<n.w;
}
int find_par(int x)
{
    if(par[x]==x) return x;
    return par[x]=find_par(par[x]);
}
void mst()
{
    for(int i=0; i<node; i++) par[i]=i;
    for(int i=0; i<edge; i++)
    {
        int u=find_par(ary[i].a);
        int v=find_par(ary[i].b);
        if(v!=u) par[v]=u;
        else ans.pb(ary[i].w);
    }
}
int main()
{

   //  read;
    while(~scanf("%d %d",&node,&edge))
    {
        if(node==0&&edge ==0) break;
        ans.clear();
        for(int i=0; i<edge; i++) scanf("%d %d %d",&ary[i].a,&ary[i].b,&ary[i].w);
        sort(ary,ary+edge,cmp);
        mst();
        if(ans.size()==0) puts("forest");
        else
        {
            sort(ans.begin(),ans.end());
            printf("%d",ans[0]);
            for(int i=1; i<ans.size(); i++) printf(" %d",ans[i]);
            puts("");
        }
     
    }

    return 0;
}

uva 929 Number Maze solution

/*********************************   MH RIYAD  *************************************/
#include <bits/stdc++.h>
#include<unordered_set>
#define  pb     push_back
#define  MAX    1010
#define  mod    100000007
#define  read   freopen("input.txt","r",stdin);
#define  write  freopen("output.txt","w",stdout);
#define  inf   (1<<30)
using namespace std;
typedef long long ll ;
typedef unsigned long long ull ;


//struct node
//{
//    int index,w;
//
//};
//bool cmp(node i,node j)
//{
//    return i.w>j.w;
//
//}
//vector<node>v[160006];
//bool mark[160006];
//int main()
//{
//    read;
//    int n,s;
//    scanf("%d",&n);
//    for(int i=2; i<=n*2; i++)
//    {
//        for(int j=1; j<i; j++)
//        {
//            scanf("%d",&s);
//            node no,no2;
//            no.index=i;
//            no.w=s;
//            v[j].pb(no);
//            no2.index=j;
//            no2.w=s;
//            v[i].pb(no2);
//        }
//    }
//
//    for(int i=1; i<=n*2; i++)
//    {
//
//        for(int j=0; j<v[i].size(); j++)
//        {
//            node p=v[i][j];
//            cout<<p.index<<" "<<p.w<<"    ";
//        }
//        cout<<endl;
//    }
//    for(int i=1; i<=n*2; i++)
//    {
//
//        sort(v[i].begin(),v[i].end(),cmp);
//        int len=v[i].size();
//        for(int j=0; j<len; j++)
//        {
//            node p=v[i][j];
//          //  if(!mark[p.w])
//          //  {
//                cout<<p.index<<" ";
//             //   mark[p.w]=true;
//                break;
//           // }
//        }
//    }
//
//    return 0;
//}

int dx[]= {-1,0,0,+1};
int dy[]= {0,+1,-1,0};

struct node
{
    int x,y,w;
    friend bool operator<(node i,node j)
    {
        return i.w>j.w;
    }
};
priority_queue<node>Q;
void dijkstra(int a,int b);
int row,col,graph[MAX][MAX],cost[MAX][MAX];
bool mark[MAX][MAX];
int main()
{
  //  read;
    int test;
    scanf("%d",&test);
    while(test--)
    {
        memset(mark,false,sizeof(mark));
        scanf("%d%d",&row,&col);
        for(int i=0; i<row; i++)
        {
            for(int j=0; j<col; j++)
            {
                scanf("%d",&graph[i][j]);
                cost[i][j]=inf;
            }
        }
        dijkstra(0,0);
        printf("%d\n",cost[row-1][col-1]);
    }
    return 0;
}

void dijkstra(int r,int c)
{
    cost[r][c]=graph[r][c];
    node q;
    q.x=r;
    q.y=c;
    q.w=graph[r][c];
    Q.push(q);

    while(!Q.empty())
    {
        node p=Q.top();
        Q.pop();
        mark[p.x][p.y]=true;
     //   cout<<p.x<<" "<<p.y<<" "<<p.w<<endl;
        for(int i=0; i<4; i++)
        {
            int R=dx[i]+p.x;
            int C=dy[i]+p.y;
            if(R>=0&&R<row&&C>=0&&C<col&&mark[R][C]==false)
            {
                if(cost[p.x][p.y]+graph[R][C]<cost[R][C])
                {
                    cost[R][C]=cost[p.x][p.y]+graph[R][C];
                    node yo;
                    yo.x=R;
                    yo.y=C;
                    yo.w=cost[R][C];
                    Q.push(yo);
                }
            }
        }

    }

}

Two pointer (nice and easy tutorial )

Ref#https://tp-iiita.quora.com/The-Two-Pointer-Algorithm

Introduction

The legendary two pointer approach is one such technique which is less of a talk and more of a discussion on the problems. Binary search is a kind of optimization on the number of trials taken to reach the optimal position and so is the two pointer technique. The approach relies on the sequence following one specific property on which our pointers can move.

​

Lets try to learn how we apply two pointers and what advantages does they offer us. We will be discussing a lot of problems that may help you to understand the technique better and for that, it is highly recommendable that you sit with a pen and a paper.

Motivation Problem: Given a sorted array  A,$A,$ having N$N$ integers. You need to find any pair(i,j)$(i,j)$ having sum as given number X$X$.

Constraints:  Array A$A$ contains about 105${10}^5$ integers with each having values around 109${10}^9$.

Solution: No doubt, we always have an option of iterating all the array values and finding their corresponding integer Aj$A_j$ having value as X$X$ −$-$ Ai$A_i$ using binary search. But, lets see how does the two pointer uses the fact that the array is sorted. For this, we keep two pointers, one at the starting tip of the array and another at the tail. Moving on, we now sum up the values contained at both the pointers. In case, value is greater than required sum, we need to shift the right pointer to the left in order to decrease the value by whatever we can since we don't have any other choice. Similarly, if we encounter the sum of values less than required sum, that we can shift the left  pointer, one unit to the right to bring us more closer to required sum. We keep moving the pointers unless we encounter the situation where Al$A_l$ +$+$ Ar$A_r$   reaches the required given sum as X$X$.

C++ implementation of above approach

#define lli long long
 
bool f(lli sum) {
    int l = 0, r = n-1; //two pointers
    while ( l <= r ) {
       if ( A[l] + A[r] == sum ) return 1;
       else if ( A[l] + A[r] > sum ) r--;
       else l++;
    }
    return 0;
}

Overall complexity of the above solution is O(N)$O(N)$.

Motivation Problem: Given two sorted arrays A$A$ and B,$B,$ each having length N$N$and M$M$ respectively. Form a new sorted merged array having values of both the arrays in sorted format.

Constraints: Array A$A$ and  B$B$ contains about 105${10}^5$ integers,$,$ each having value around 109${10}^9$.

Solution: Since the two arrays are given in sorted order, we can surely do something with two pointers. Let us go step by step.

1. We will introduce read-indices l1$l1$, l2$l2$ to traverse arrays A$A$ and B,$B,$ respectively. and another write-index cnt$cnt$ to store position of the first free cell in the resulting array. Initially all l1,l2$l1,l2$ and cnt$cnt$ will be 0$0$
2. Moving on, if both indices are in range (l1$l1$  <$<$ N$N$ and l2$l2$ <$<$ M$M$), choose minimum of (Ai,$A_i,$   Bj$B_j$) and write it to C[cnt],$C[cnt],$ and increase the respective pointer.

C++ implementation of  the above approach

#define MAX 100005
 
lli C[2*MAX];
 
void merge(lli A[], lli B[])
{
    int l1 = 0, l2 = 0, cnt = 0;
    while ( l1 < n || l2 < m ) {
       if ( l1 < n && l2 < m ) {
          if ( A[l1] < B[l2] ) {
              C[cnt++] = A[l1]; 
              l1++;
          }
          else if ( A[l1] > B[l2] ) {
              C[cnt++] = B[l2];
              l2++;
          }
       }
       else if ( l1 < n ) {
          C[cnt++] = A[l1];
          l1++;
       }
       else if ( l2 < m ) {
          C[cnt++] = B[l2];
          l2++; 
       }
    }
    return;
}

We basically traversed both the arrays in the sorted order of combined elements and hence kept inserting the elements into the new array that we needed.

Overall complexity of the solution is O(N+M).$O(N+M).$  

Move on to the next problem if you are sure, you understood the above problems right and have implemented them yourself. I would like you to think as much as you can in all the problems and question yourself, Why?. Thinking is a healthy process and good for exercising your brain to understand the concepts a lot better.

Motivation Problem: Given an array having N$N$ integers,$,$ find the contiguous subarray having sum as great as possible,$,$ but not greater than M$M$. For details on the statement, refer the problem link here

Constraints: Array can have atmost 105${10}^5$ elements and each number will be non-negative and can be as big as 109${10}^9$.

Solution: As the given array contains positive elements, cumulative sum will indeed be increasing as you go on from left to right in the array. If you have already read the binary search tutorial, I am pretty sure you must have found out a way to solve it already.

Solution using binary search:

• Store cumulative sum at each index in a separate auxiliary array.
• Treat each index as startIndex of the required contiguous subarray, find a corresponding endIndex such that the following equation holds true.

cum[endIndex] - cum[startIndex-1] <= M and cum[endIndex+1] - cum[startIndex-1] > M

I leave the implementation for this on the part of the reader to discuss in comments. Now, let us see how can we solve the problem using the two pointers technique.

• We introduce two pointers l,r$l,r$  denoting startIndex and endIndex of our contiguous subarray, with both of them at the tip of the array.
• We now start extending our right pointer r$r$  provided sum[l,r]$sum[l,r]$ <=$<=$ M$M$ Once, we reach at such a stage, we don't have any option but to move the left pointer as well and start decreasing the sum until we arrive at the situation where we can extend our right pointer again.
• As and when we reach the point, where we need to shift the left pointer, we keep updating our maximum sum we have achieved so far.

C++ implementation of the above approach

#include <bits/stdc++.h>
#define lli long long
#define MAX 1000005
 
using namespace std;
 
lli A[MAX];
 
int main()
{
    int n;
 lli sum = 0;  
    cin >> n;
   
    for ( int i = 0; i < n; i++ ) cin >> A[i];
    
    int l = 0, r = 0;
 lli ans = 0;
 
    while ( l < n ) {
       while ( r < n && sum + A[r] <= M ) {
           sum += A[r];
           r++;
       }
       ans = max(ans, sum);
       sum -= A[l];
       l++;
    }
 
    cout << ans << endl;
    return 0;
}

That was a lot of fun, learning one topic in such a less amount of time. Excited still!? Lets see how much more you can grasp. Moving on to the next problem...

Motivation Problem: Given an array containing N$N$ integers, you need to find the length of the smallest contiguous subarray that contains atleast K$K$ distinct elements in it. Output "−1$-1$" if no such subarray exists.

Constraints: Number of elements in the array are around one million with each of them having value as large as 109${10}^9$ .

Solution: Now, thats where the legendary two pointer technique is the only way to your rescue. If you are reading this, I am pretty much sure that you have read the tutorial on STL containers. The STL container you need to know about here is set.

Going by our own traditional way as we approached in the previous problem, we take two pointers l,r$l,r$  with both at the tip of the array. We keep on shifting the right pointer unless we have K$K$ elements into the set as set will only contains distinct elements and will ignore the insertion of duplicate elements. As soon as we meet our condition, we now shift the left pointer unless the size of the set becomes <$<$ K$K$. We also update the length of our minimum contiguous subarray as soon as we are ready to shift the left pointer.

C++ implementation of above approach

int l = 0, r = 0, ans = INF;
map <int , int >  cnt;
 
while ( l < n ) {
    while ( r < n && s.size() < K ) {
       s.insert(A[r]);
       cnt[A[r]]++;
       r++;
    }
    if (s.size() >=K) {
  ans = min(ans, r-l);
 }
    if ( cnt[A[l]] == 1 ) s.erase(A[l]); 
    cnt[A[l]]--; 
    l++;
}
if ( ans == INF ) ans = -1;
 
cout << ans << endl;

Great, that was just kind of similar to previous problem. Lets move on to the final problem and you shall be ready to explore.

Motivation Problem:  Given an array having N$N$ integers, you need to find out a subsequence of K$K$ integers such that these  K$K$ integers have the minimum hustle. Hustle of a sequence is defined as sum of pair-wise absolute differences divided by the number of pairs. For details on the statement, refer the problem link here

Constraints: Both N$N$ and K are less than or equal to 105${10}^5$ and each element has absolute value of around 109${10}^9$.

Solution: Since, this will be the last problem, let us try to spend some more time discussing the solution in detail.

You really don't want this to be the last problem of the discussion, don't you?

Anyway, lets see what the problem demands this time. The number of pairs in the function wont be of much significance since we will always be dividing by fixed number of C(K,2)$C(K,2)$ pairs. So, we can ignore the denominator here and the way function "hustle"  is defined surely tells us that the numerator of the function will be minimum as much as those K$K$ integers will be close to each other. Since, hustle function is nothing but merely summation of absolute difference of pairs. Why not just sort the numbers and consider each consecutive contiguous subarray of length K$K$ for this? That's it. You are done for good !

If you still doubt how we have reduced the problem from subsequence of length K$K$to contiguous substring of length K$K$, try to contradict yourself by removing one element from contiguous K$K$ elements and taking some other element, you will surely realize, what wrong happened their and how much the absolute difference increased overall. Try to prove this way to give yourself complete satisfaction about the greedy technique used over here.

C++ implementation of above approach.

#include <bits/stdc++.h>
using namespace std;
 
#define lli long long
#define MAX 1000006
 
lli A[MAX],C[MAX];
 
int main()
{
    int l = 1, r = 2, st,en,n;
    
    lli sum,ans;
 
    cin >> n >> k;
    
    for ( int i = 1; i <= n; i++ ) cin >> A[i];
 
    sort(A+1, A+n+1);
 
    cum[0] = 0;
    for ( int i = 1; i <= n; i++ ) cum[i] = cum[i-1] + A[i];
    
    while ( r <= k ) {
       sum += (A[r]*(r-l) - (cum[r-1] - cum[l-1]));
       r++;
    }
 
    st = 1, en = k, ans = sum;
 
    while ( r <= n ) {
       sum -= (cum[r-1] - cum[l] - A[l]*(r-l-1));
       l++;
       sum += (A[r]*(r-l) - (cum[r-1] - cum[l-1]));
        
       if ( ans > sum ) {
          ans = sum;
          st = l;
          en = r;
       }
       r++;
    }
    return 0;
}

Overall complexity of the solution is O(NlogN)$O(NlogN)$ +$+$ O(N)