D. Gargari and Permutations

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations. Each of them consists of numbers 1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?

You can read about longest common subsequence there:https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Input

The first line contains two integers n and k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). Each of the next k lines contains integers 1, 2, ..., n in some order — description of the current permutation.

Output

Print the length of the longest common subsequence.

Sample test(s)

input

4 3
1 4 2 3
4 1 2 3
1 2 4 3

output

3

Note

The answer for the first test sample is subsequence [1, 2, 3].

#include<list>

#include<vector>

#include<stack>

#include<iostream>

#include<stdio.h>

using namespace std;

int arr[7][1003];

int Val[7][1003];

list<int> lst[1004];

int visited[1002];

int dist[1004];

int ans=INT_MIN;

void dfs(int st)

{

visited[st]=1;

list<int>::iterator it;

for(it=lst[st].begin();it!=lst[st].end();it++)

{

if(!visited[*it])

dfs(*it);

dist[st]=max(dist[st],dist[*it]+1);

}

    dist[st]=max(dist[st],1);

ans=max(ans,dist[st]);

}

int main()

{

int N;

int K;

int a;

int f=0;

cin>>N>>K;

for(int i = 1; i <= K; ++ i)

        for(int j = 1; j <= N; ++ j)

        {

            scanf("%i", &Val[i][j]);

            arr[i][ Val[i][j] ] = j;

        }

 

    for(int i = 1; i <= N; ++ i)

        for(int j = 1; j <= N; ++ j)

        {

            if(i == j) continue;

            bool flag = 1;

            for(int k = 1; k <= K; ++ k)

                if(arr[k][i] >= arr[k][j])

                    flag = 0;

            if(flag==1) lst[i].push_back(j);

        }

for(int i=1;i<=N+1;i++)

{

dist[i]=INT_MIN;

}

    for(int i=1;i<=N;i++)

    {

    if(visited[i]==0)

    {

      dfs(i);

}

    }

   cout<<ans<<endl;    

    return 0;

}

  

               **code ends here**

The question can be generalised as finding the LCS of k strings. It is implemented using directed acyclic graph. The procedure of composed of 2 steps 

(1) Forming the graph 

We can build a directed acyclic graph with n nodes.If j is after i in all vectors then we add in graph edge (i,j).

The graph using adjacency list representation would look like 

1 - 2 , 3

2- 3

3- none

4-3

Now we have formed a directed acyclic graph . Now the 2nd part is finding longest path in the graph

(2) Finding longest path in the graph

 Now we recursively call dfs from all unvisited nodes. As soon as we reach the leaf we update its value by max(dist[leafnode],1) and then update the answer accordingly. 

as the call to a dfs ends we update the value of the parent as max of the (1*dist[child], dist[st]).

The answer is max of all values.

Remembering this question is very important as these helps in finding LCS of many strings. This can be also done using DP the solution of which is highly recommended. Here is the Dynamic Programming solution

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int pos[6][1003];
int a[6][1003];
int dp[1003];
int N, K;
int main(){
    scanf("%d%d", &N, &K);
    for(int i=1;i<=K;++i){
        for(int j=1;j<=N;++j){
            scanf("%d", &a[i][j]);
            pos[i][a[i][j]] = j;
        }
    }
    int ans = 1;
    dp[N] = 1;
    for(int i=N-1;i>=1;--i){
        dp[i] = 1;
        for(int j=i+1;j<=N;++j){
            bool ok = true;
            for(int k=1;k<=K;++k){
                if(pos[k][a[1][i]] > pos[k][a[1][j]]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                dp[i] = max(dp[i], 1+dp[j]);
            }
        }
        ans = max(ans, dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

                                            Back to Underworld

The Vampires and Lykans are fighting each other to death. The war has become so fierce that, none knows who will win. The humans want to know who will survive finally. But humans are afraid of going to the battlefield.

So, they made a plan. They collected the information from the newspapers of Vampires and Lykans. They found the information about all the dual fights. Dual fight means a fight between a Lykan and a Vampire. They know the name of the dual fighters, but don't know which one of them is a Vampire or a Lykan.

So, the humans listed all the rivals. They want to find the maximum possible number of Vampires or Lykans.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 10⁵), denoting the number of dual fights. Each of the next n lines will contain two different integers u v (1 ≤ u, v ≤ 20000) denoting there was a fight between uand v. No rival will be reported more than once.

Output

For each case, print the case number and the maximum possible members of any race.

Sample Input	Output for Sample Input
2 2 1 2 2 3 3 1 2 2 3 4 2	Case 1: 2 Case 2: 3

Note

Dataset is huge, use faster I/O methods.

###############################editorial ##########################################

in this problem we need to find  maximum no  of node which can be coloured with same colour .

so we treat each disconnected components as different problem and .. for each dissconnected component we  colour this disconected  component  whith two different colours (colur which is not used yet in any other disconnected component ) ... and finally we find sum of (maxim from each disconnected components ).. since that maximium  sinc all those  nodes can be coloured with same colour .......(think ..)

################################code ###################

#include<iostream>

using namespace std;

#include<bits/stdc++.h>

 int read_int(){

char r;

bool start=false,neg=false;

int ret=0;

while(true){

r=getchar();

if((r-'0'<0 || r-'0'>9) && r!='-' && !start){

continue;

}

if((r-'0'<0 || r-'0'>9) && r!='-' && start){

break;

}

if(start)ret*=10;

start=true;

if(r=='-')neg=true;

else ret+=r-'0';

}

if(!neg)

return ret;

else

return -ret;

}

int bfs(int pos,int val,int visited[],list<int>li[])

 {

    queue<int >q;

    q.push(pos);

      while(!q.empty())

       {

          int start=q.front();

          q.pop();

          list<int> :: iterator it;

          for(it=li[start].begin();it!=li[start].end();it++)

           {

            if(visited[*it]==0)

            {

            visited[*it]=-1*visited[start];

            q.push(*it);

            }

           }

       }

 }

int main()

{

int tt;

cin>>tt;

int t=1;

   while(tt--)

    {

    int n;

   

    n=read_int();

      int visited[20000+10];

      list<int> li[20000+10];

      

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

       {

           int a,b;

          // cin>>a>>b;

           a=read_int();

           b=read_int();

           li[a].push_back(b);

           li[b].push_back(a);

           

           

       }

      for(int i=0;i<=20010;i++) visited[i]=0;

       

       int ll=1;

        

        for(int i=1;i<=20000;i++)// call bfs for all disconnected components 

         {

          if(!visited[i] && !li[i].empty())

           {

           visited[i]=ll;

            bfs(i,-ll,visited,li);// fill with ll colour

            ll++;

           }

         }

       

       

         int ans=0;

         for(int i=1;i<ll;i++)// find no of node coloured with i and  -i colour and ans=max (a1,a2)

          {

          int a1=0,a2=0;

          for(int j=0;j<=20000+1;j++)

          {

          if(visited[j]==i) a1++;

          if(visited[j]==-1*i) a2++;

          }

          ans+=max(a1,a2);

           

          }

       

    cout<<"Case "<<t++<<":"<<" "<<ans<<endl;

     

    }

    return 0;

}

B. Om Nom and Dark Park

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Om Nom is the main character of a game "Cut the Rope". He is a bright little monster who likes visiting friends living at the other side of the park. However the dark old parks can scare even somebody as fearless as Om Nom, so he asks you to help him.

The park consists of 2n + 1 - 1 squares connected by roads so that the scheme of the park is a full binary tree of depth n. More formally, the entrance to the park is located at the square 1. The exits out of the park are located at squares 2n, 2n + 1, ..., 2n + 1 - 1 and these exits lead straight to the Om Nom friends' houses. From each square i (2 ≤ i < 2n + 1) there is a road to the square . Thus, it is possible to go from the park entrance to each of the exits by walking along exactly n roads.

To light the path roads in the evening, the park keeper installed street lights along each road. The road that leads from square i to square  has ai lights.

Om Nom loves counting lights on the way to his friend. Om Nom is afraid of spiders who live in the park, so he doesn't like to walk along roads that are not enough lit. What he wants is that the way to any of his friends should have in total the same number of lights. That will make him feel safe.

He asked you to help him install additional lights. Determine what minimum number of lights it is needed to additionally place on the park roads so that a path from the entrance to any exit of the park contains the same number of street lights. You may add an arbitrary number of street lights to each of the roads.

Input

The first line contains integer n (1 ≤ n ≤ 10) — the number of roads on the path from the entrance to any exit.

The next line contains 2n + 1 - 2 numbers a2, a3, ... a2n + 1 - 1 — the initial numbers of street lights on each road of the park. Here ai is the number of street lights on the road between squares i and . All numbers ai are positive integers, not exceeding 100.

Output

Print the minimum number of street lights that we should add to the roads of the park to make Om Nom feel safe.

Sample test(s)

input

2
1 2 3 4 5 6

output

5

Note

Picture for the sample test. Green color denotes the additional street lights.

####################################editorial#################################

note:: arr[i] holds the number of street light betn i and floor(i/2)

First  of all we need to find the path which has the maximum number of street lights. This can be done by simply dividing all the leaf node by 2 till we reach the root node.

Now we need to place the max lights on each node. This is bit tricky. 

Suppose we are at node i, then we traverse all possible paths from here and see the maximum street light present , and we travel upwards from i to see the required number of lights to be added. We put the required number of lights on that edge that connects it to the heavy side(in terms of street light) and the go and repeat the same for levels below it. In case if street lights cannot be added at that level we further go down and add it to a position where it doesnot violate the condition of maximum count.  

   #########################code########################################

#include<iostream>

#include<stdio.h>

using namespace std;

long long int ret=0;

long long int  arr[200000];

long long int up=0;

long long int all(long long int start,long long int sum)

 {

  if(start>up)

  {

  if(sum>ret)ret=sum;

  }#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long c,hr,hb,wr,wb,f,s,ht,wt,wl,max=0;

    cin>>c>>hr>>hb>>wr>>wb;

        f=c/wr;

        wt=f*wr;

        ht=f*hr;

        wl=c-wt;

        s=wl/wb;

     //   wt+=s*wb;

        ht+=s*hb;

        max=ht;

        f--;

        while(f>=0)

        {

            wt=f*wr;

            ht=f*hr;

            wl=c-wt;

            s=wl/wb;

          //  wt+=s*wb;

            ht+=s*hb;

            if(ht>max)

                max=ht;

            f--;

        }

    cout<<max<<endl;

    return 0;

}

Chat Conversation End

  else

  {

  all(2*start,sum+arr[start]);

  all(2*start+1,sum+arr[start]);

  }

 }

int main()

{

long long int n;

cin>>n;

long long int x=1;

for(long long int t=1;t<=n;t++)

{

x=x*2;

}

up=2*x-1;

for(long long int i=2;i<=2+up-2;i++)

{

cin>>arr[i];

}

long long int mix=-1;

long long int sum=0;

long long int num;

for(long long int i=up;i>=x;i--)

{

sum=0;

num=i;

while(num!=1)

{

sum+=arr[num];

num=num/2;

}

if(sum>mix)

mix=sum;

}

// cout<<mix<<endl;

long long  int ans=0;

 for(long long int i=2;i<=up;i++)

  {

  // cout<<i<<endl;

 

        ret=0;

        long long int back_sum=0;

       for(long long int j=i;j>1;)

        {

        back_sum+=arr[j];

        j/=2;

        }

       //  cout<<"i "<<i<<" back_sum "<<back_sum<<endl;

        

        long long int ma=max(all(2*i,0),all(2*i+1,0));

       long long  int lit=mix-back_sum-ret;

        arr[i]+=lit;

        ans+=lit;

     

     

  }

   cout<<ans<<endl;

   return 0;

}