DSU implementation by blue mary


int f i n d ( int x )
{ // i d e n t i f y t h e r o o t
 int r o o t = x ;
 while ( parent [ r o o t ] >= 0 )
r o o t = p a ren t [ r o o t ] ;
// p a t h compress ion
 while ( x ! = r o o t )
{ int ol d = x ;
x = p a ren t [ x ] ;
 p a ren t [ ol d ] = r o o t ;
 }
return r o o t ;
}
 /∗ Combines t h e s e t s t h a t x and y occupy . Re turns t r u e on ∗ s u c c e s s , or f a l s e i f x and y are a l r e a d y in t h e same s e t . ∗/
 bool merge ( int x , int y )
 { // i d e n t i f y r o o t s
 x = f i n d ( x ) ;
 y = f i n d ( y ) ;
 // c heck f o r no−op
i f ( x == y ) return f a l s e ;
 // make s u re t h a t x i s t h e l a r g e r s e t . p a re n t [ x ] i s t h e // neg a te d s i z e o f t h e s e t c o n t a i n i n g x .
i f ( paren t [ x ] > p a ren t [ y ] )
 swap ( x , y ) ;
// u p d a te t h e s i z e o f x
p a ren t [ x] += p a ren t [ y ] ;
 // p l a c e y under x p a ren t [ y ] = x ;
return true
; }

http://olympiad.cs.uct.ac.za/presentations/camp1_2006/unionfind-handout.pdf 

Root of the Problem  Problem code: TREEROOT

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Chef has a binary tree. The binary tree consists of 1 or more nodes. Each node has a unique integer id. Each node has up to 2 children, which are identified by their ids, and each node is the child of at most 1 other node. A node X is considered to be an ancestor of node Y if node Y is a child of node X or if there is some node Z for which X is an ancestor of Z and Y is a child of Z. No node is an ancestor of itself. A special node called the root node is an ancestor of all other nodes.

Chef has forgotten which node of his tree is the root, and wants you to help him to figure it out. Unfortunately, Chef's knowledge of the tree is incomplete. He does not remember the ids of the children of each node, but only remembers the sum of the ids of the children of each node.

Input

Input begins with an integer T, the number of test cases. Each test case begins with an integer N, the number of nodes in the tree. N lines follow with 2 integers each: the id of a node, and the sum of the ids of its children. The second number will be 0 if the node has no children.

Output

For each test case, output on a line a space separated list of all possible values for the id of the root node in increasing order. It is guaranteed that at least one such id exists for each test case.

Constraints

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 30
• All node ids are between 1 and 1000, inclusive

Sample Input

2
1
4 0
6
1 5
2 0
3 0
4 0
5 5
6 5

Sample Output

4
6

Explanation

In the first sample test case, there is only one node, which is clearly the root. In the second test case, there are two non-isomorphic trees that satisfy the constraints, as seen in the following picture:

  6           6
   \         / \
    5       1   4
   / \       \
  1   4       5
 / \         / \
2   3       2   3

This question is highly disguised as the nature of the problem will suggest us to

seek many kind of brute force solution. However, the mathematical fact lies beneath.

Denote by "id(node v)" the id of the node v, and "sid(node v)" the sum of the id's of v's children. Consider x = sum(id(v) - sid(v)) over all nodes v. If a binary tree exists, then its root node has to have id x. This is because, for each node v other than the root, its id is counted once in the sum (as id(v)) and it cancels out once in the sum (as -sid(v's parent)). Since the root node doesn't have a parent, its id is left uncanceled in the sum.

If we sum up all ids and then subtract from it it the sum of all child present then what we are left with is the id of the root of the tree...

This question was entirely mathematical and didnot require any grpahical algorithms.

#include<iostream> 

#include<stdio.h>

 using namespace std; 

int main()

 {
 int t;
 cin>>t;

 int a,b; 

 while(t--) 

      {
   int n; 

             cin>>n;
   int sumid=0;
   int sumchild=0; 

                    for(int i=0;i<n;i++) 

                      {
       cin>>a>>b;
       sumid+=a; 

                      sumchild+=b;

                   } 

                 cout<<sumid-sumchild<<endl; 

        }

     return 0; 

}

After IOI Ilya decided to make a business. He found a social network called "TheScorpyBook.com". It currently has N registered users. As in any social network two users can be friends. Ilya wants the world to be as connected as possible, so he wants to suggest friendship to some pairs of users. He will suggest user u to have a friendship with user v if they are not friends yet and there is a user w who is friends of both of them. Note that u, v and w are different users. Ilya is too busy with IPO these days, so he asks you to count how many friendship suggestions he has to send over his social network.

Input

The first line contains an integer number N — the number of users in the network. Next N lines containN characters each denoting friendship relations. j^th character if the i^th lines equals one, if users i and jare friends and equals to zero otherwise. This relation is symmetric, i.e. if user a is friend of b then b is also a friend of a.

Output

Output a single integer — number of friendship suggestions Ilya has to send.

Constraints

• 1 ≤ N ≤ 2000

Example

Input:
4
0111
1000
1000
1000

Output:
6

This question requires some insight , first of all we need to understand that  we need to send a suggestion to only that user which has a distance of 2 . For this (1)  we make an adjacency list of the given matrix

(2) we traverse the list for all i starting from i=0 to n and search if i need to send a suggest a friend request to j where j starts from i+1

  now for any user k that is adjacent to the present index i we just find if j is directly connected to the particular adjacent of i.  If it is then we increment the counter by 1 and break;

  This is evident from the portion 

 i 

                               if(frn[*it][j]=='1')

which clearly checks if the present adjacent of i is adjacent to j th node then we increase the count 

The final output is 2*cnt as we have counted for user i to j and not for j to i.

************* code runs her *******

#include<list>
#include<stack>
#include<iostream>
#include<stdio.h>
using namespace std;
char str[2020];
char frn[2010][2010];
int main()
{
 int n;
 cin>>n;
 list<int> li[2010];
 for(int i=0;i<n;i++)
 {
   cin>>str;
   for(int j=0;j<n;j++)
   {
       frn[i][j]=str[j];
       if(str[j]=='1')
    {
     li[i].push_back(j);
    }
   }
 }
int req=0;
 for(int i=0;i<n;i++)
 {
   for(int j=i+1;j<n;j++)
   {
    if(frn[i][j]=='0')
    {
     list<int> ::iterator it;
     for(it=li[i].begin();it!=li[i].end();it++)
     {
      if(frn[*it][j]=='1')
      {
       req++;
       break;
      }
     }
    }
   }
 }
 cout<<req*2<<endl;
 return 0;
}

      **** code ends here ******

The above thing can also be done using the concept of warshall where squaring the matrix will give us the number of walks of length 2 from i to j .   For more refer to warshall algorithm.

However squaring the matrix is o(n^3) complex but with binary matrices , this can be reduced using Four Russian Rule 

The setters code gives us the idea..

https://s3.amazonaws.com/codechef_shared/download/Solutions/COOK48/Setter/RRFRNDS.java

Line Segments

Authored by Adigha on Oct 14 2014

• Problem
• Submissions
• Leaderboard
• Discussions
• Editorial

Problem Statement

You are given N line segments. All of them lie on the same line. We will describe the ith line segment with two integers, Ai and Bi. This means it starts at Ai and ends at Bi. It will be denoted as (Ai;Bi).

Let's say a pair of line segments is good, if one of them is not covering the other one. For example, the pair of (1;4) and (2;5) is good. But the pair of (1;6) and (2;5) is bad because (1;6) covers (2;5).

Let's assume that we have the ith and jth line segments. If Ai≤Aj and Bi≥Bj, we can say "the ith line segment covers jth line segment."

You must find the size of the biggest subset of these line segments that contains no badpairs.

Input Format 
In the first line you are given an integer N, the total number of line segments. 
The next N lines contain two integers, Ai and Bi.

Constraints 
1≤N≤105 
1≤ Ai≤Bi≤109

Output Format 
You must print one integer denoting the size of the biggest subset.

First of all, we must observe that we are trying to choose a subset so the order is not important. If we sort the line segments in ascending order by the start points we just need to compare end points when we need to know a pair of line segments is good or bad. For example if we need to know about i-th line segment and j-th line segment (1≤i≤j≤N) we just need to compare their end points. Because we already know that Ai ≤ Aj. So if Bi ≥ Bj then i-th line segment covers j-th line segment. 

Now if we choose an increasing subsequence (not non-decreasing) from B, this can be the answer subset. Because there will be no bad pairs in that increasing subsequence. 

Few important points 

We sort the vector in ascending order of starting time . howerever when the 

starting time are same we sort the second element according to the decreasing second element. 

suppose the point are 

5

1 9

1 7

1 8

1 6

2 10

the vector sorted should be 

1 1 1 1 2

9 7 8 6 10

and not 

1 1 1 1 2

6 8 7 9 10

Now we find the LIS in the end points. The reason the array was sorted in this

manner was to ensure the points are strictly increasing.

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<vector>

using namespace std;

long long int arr[1000010];

struct sort_pred {

    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {

        if( left.first==right.first)

        return left.second >right.second;

        else

            return left.first <right.first;

    }

};

 int CeilIndex(int A[], int l, int r, int key) {

    int m;

    while( r - l > 1 ) {

        m = l + (r - l)/2;

        (A[m] >= key ? r : l) = m; // ternary expression returns an l-value

    }

    return r;

}

 int LIS(long long int A[], int size) {

    // Add boundary case, when array size is one

    int *tailTable   = new int[size];

    int len; // always points empty slot

    memset(tailTable, 0, sizeof(tailTable[0])*size);

    tailTable[0] = A[0];

    len = 1;

    for( int i = 1; i < size; i++ ) {

        if( A[i] < tailTable[0] )

            // new smallest value

            tailTable[0] = A[i];

        else if( A[i] > tailTable[len-1] )

            // A[i] wants to extend largest subsequence

            tailTable[len++] = A[i];

        else

            // A[i] wants to be current end candidate of an existing subsequence

            // It will replace ceil value in tailTable

            tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i];

    }

    delete[] tailTable;

    return len;

}

int main()

{

     int n;

     cin>>n;

     long long int a,b;

     vector<pair<long long int ,long long int> >v;

     for(int i=0;i<n;i++)

     {

        cin>>a>>b;

v.push_back(make_pair(a,b));  

     }

     sort(v.begin(),v.end(),sort_pred());

     for(int i=0;i<n;i++)

     {

      cout<<v[i].first<<" ";

     }

     for(int i=0;i<n;i++)

     {

      cout<<v[i].second<<" ";

     }

     cout<<endl;

     for(int i=0;i<n;i++)

     {

         arr[i]=v[i].second;

     }

     int ans=LIS(arr,n);

cout<<ans<<endl;

return 0;     

}