1159 - Batman

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

Batman is in deep trouble. You know that superheroes are there to help you when you are in trouble. But in Gotham city there is no trouble. So, 'no trouble' is actually the trouble for our Batman.

So, Batman is trying to solve ACM problems because he wants to be a good programmer like you :). But alas! He is not that smart. But still he is trying. He found 3 strings of characters. Now he wants to find the maximum string which is contained in all the three strings as a sub sequence. He wants to find the maximum length, not the sequence.

Now, Batman claims that he is a better programmer than you. So, you are solving the same problem. Can you solve faster? You are guaranteed that Batman will need 3 hours to solve the problem. So, you have to be faster than him.

Input

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

Each case will contain a blank line and three strings in three lines. None of the string lengths will be greater than 50 and less than 1. And the string will contain alphanumeric characters only.

Output

For each case, print one line containing the case number and the length of the largest subsequence.

Sample Input	Output for Sample Input
3 abcdef cdef dcdef aaaa bbbb ccca aaaa aaaa aaa	Case 1: 4 Case 2: 0 Case 3: 3

        

This is a standard lca question extended to 3d state 

after visualising it we shall observe that  

if(a[i]==b[j]==c[k])

dp[i][j][k]=1+dp[i-1][j-1][k-1]

else the normal recurrence is

 dp[i][j][k]=max(max(dp[i-1][j][k],dp[i][j-1][k]),dp[i][j][k-1]);

               ******************The code goes here *******************************

#include<bits/stdc++.h>

using namespace std;

int dp[56][56][56];

int main()

{

  int t;

  cin>>t;

  int tt=1;

  while(t--)

  {

   string a,b,c;

   cin>>a>>b>>c;

   int n=a.length();

   int m=b.length();

   int l=c.length();

   memset(dp,0,sizeof(dp));

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

   {

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

 {

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

{

if(a[i-1]==b[j-1] && a[i-1]==c[k-1])

{

          dp[i][j][k]=1+dp[i-1][j-1][k-1];

}

else 

{

      /* if(a[i-1]==b[j-1])

       {

           dp[i][j][k]=1+dp[i-1][j-1][k];

}

if(a[i-1]==c[k-1])

{

   dp[i][j][k]=1+dp[i-1][j][k-1];

}

if(b[j-1]==c[k-1])

{

 dp[i][j][k]=1+dp[i][j-1][k-1];

}*/

// if((a[i-1]!=b[j-1]) &&(a[i-1]!=c[k-1]) &&(b[j-1]!=c[k-1]))

{

 dp[i][j][k]=max(max(dp[i-1][j][k],dp[i][j-1][k]),dp[i][j][k-1]);

}

}

}

}

}

cout<<"Case "<<tt<<": "<<dp[n][m][l]<<endl;

                tt++;

}

return 0;

}

F. Ant colony

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength si.

In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l andr (1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if si divides sj (also, ant j gets one battle point only if sj divides si).

After all fights have been finished, Mole makes the ranking. An ant i, with vi battle points obtained, is going to be freed only if vi = r - l, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.

In order to choose the best sequence, Mole gives you t segments [li, ri] and asks for each of them how many ants is he going to eat if those ants fight.

Input

The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony.

The second line contains n integers s1, s2, ..., sn (1 ≤ si ≤ 109), the strengths of the ants.

The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases.

Each of the next t lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing one query.

Output

Print to the standard output t lines. The i-th line contains number of ants that Mole eats from the segment [li, ri].

Examples

input

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

output

4
4
1
1

Note

In the first test battle points for each ant are v = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.

In the second test case battle points are v = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.

In the third test case battle points are v = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.

In the fourth test case battle points are v = [0, 1], so ant number 5 is freed. Mole eats the ant 4.

Explanation

Let us begin with few observations.

(1) A mole cannot kill an ant if that ant divides every number in the range left to right

(2) Now infact the ant having the value equal to gcd of a[left...right] cannot be killed by the mole

Now we need to maintain a segment tree for gcd queries between left to right. And query the tree for gcd from left to right. Now all that is left is knowing how many such values lie between left to right.

This is cleverly done using a sorted pair of vector which stores values and indices. Now we do a lower bound query on the vector pair   using pair(value,right+1) and pair(value,left)  ,the difference of this indices gives us the number of values lying between left and right.

************ Code goes here*****************

#include<bits/stdc++.h>

using namespace std;

int a[200010];

int tree[600010];

#define ff first

#define ss second

#define mp make_pair

#define pb push_back

vector<pair<int,int> > v;

void build(int node,int s,int e)

{

  if(s>e)

  return ;

  if(s==e)

  {

      tree[node]=a[s];

      return ;

  }

  int mid=(s+e)/2;

  build(2*node,s,mid);

  build(2*node+1,mid+1,e);

  tree[node]=__gcd(tree[2*node],tree[2*node+1]);

  

}

int query(int node,int s,int e,int l,int r)

{

       if(s>e || s>r || e<l)

       return 0;

       if(s>=l && e<=r )

       return tree[node];

       int mid=(s+e)/2;

       int gc1=query(2*node,s,mid,l,r);

       int gc2=query(2*node+1,mid+1,e,l,r);

       return __gcd(gc1,gc2);

}

int get(int val,int idx)

{

       pair<int,int> mm;

       mm=make_pair(val,idx);

       int r=lower_bound(v.begin(),v.end(),mm)-v.begin();

       return r;

}

int main()

{

 int n;

 cin>>n;

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

 {

 

 cin>>a[i];

  v.pb(mp(a[i],i));

       }

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

 build(1,0,n-1);

 int q;

 cin>>q;

 while(q--)

 {

    int l,r;

    scanf("%d %d",&l,&r);

    l--;

    r--;

    int gc=query(1,0,n-1,l,r);

    int hig=get(gc,r+1);

    int low=get(gc,l);

    int ans=(r-l+1)-(hig-low);

    printf("%d\n",ans);

    

 }

 return 0;

}

                                          BITMASKING DP

Little Elephant and T-Shirts  Problem code: TSHIRTS

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian.

Little Elephant and his friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts of the same ID.

They want to know how many arrangements are there in which no two persons wear same T-Shirt. One arrangement is considered different from another arrangement if there is at least one person wearing a different kind of T-Shirt in another arrangement.

Input

First line of the input contains a single integer T denoting number of test cases. Then T test cases follow.

For each test case, first line contains an integer N, denoting the total number of persons. Each of the next Nlines contains at least 1 and at most 100 space separated distinct integers, denoting the ID's of the T-Shirtsi^th person has.

Output

For each test case, print in single line the required number of ways modulo 1000000007 = 10⁹+7.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10

Example

Input:
2
2
3 5
8 100
3
5 100 1
2
5 100

Output:
4
4

Explanation

For the first case, 4 possible ways are (3,8), (3,100), (5,8) and (5,100).For the second case, 4 possible ways are (5,2,100), (100,2,5), (1,2,100), and (1,2,5).

editorial

First of all we must be certain of few things the memoisation can only be done on the number of students. Now 

in order to be sure there are no repitions we assign tshirts in order of increasing id. Not students in increasing id. 

Here lies the crisp of the question. We need to first assign all the students who have tshirt with number 1 then 

all student with tshirst number 2 and so on.

It is a very standard kind of Dynamic Programming with bitmasking. So the idea here is to keep a 2-D array DP[2N][K], where DP[i][j] will store the answer only if tshirts from id 1 to j have been used. Also, let's say i when denoted in binary be b1,b2...bn. If bp(1 ≤ p ≤ n) is 1, it means that person with id==p has been alloted a tshirt and all persons with bits 1 are assigned distinct tshirts. 

So, we'll write a recursive DP, which is obviously easier to write. 

We keep a function rec(mask, tid) which means that tshirts till id tid have been processed and mask denotes which persons have been given tshirts. At each step we assign tshirts to each possible person and recursively calculate the number of ways.a 

Following pseudo code will make it more clear.

dp[1<<N][K]={}

memset dp to -1    // dp[i][j]=-1 means it hasn't been calculated yet

def rec(mask, tid):  // tid denotes the tshirt id

    if mask==2**(N)-1:  // all bits are set, all persons have been alloted tshirts

    return dp[mask][tid]=1

    if tid==101:    // all tshirts finished

    return 0

    if dp[mask][tid]!=-1:   // it has already been calculated, we won't calculate it again

    return dp[mask][tid]

    ans=0

    ans += rec(mask,tid+1)  // the case when we don't assign tshirt with id=tid to anyone

    // the case when we assign tshirt with id=tid to someone

    // we will assign the tshirt with id=tid to all possible persons we can, and add to answer the respective number of ways

    // note that we are assigning distinct tshirts only, since tshirt with id=tid has never been assigned before to anyone.

    for persons p(0<=p<=N-1) which have tshirt with id=tid:

    if mask&(1<<p): // person p + 1 has already been alloted a tshirt

        continue    // do nothing

    ans += rec(mask|(1<<p),tid+1)   // assign tshirt tid to person p and add to answer next cases

    return dp[mask][tid]=ans;

Our answer will be rec(0,1) ie. starting with mask=0(no one has been assigned any tshirt) and tid=1. Complexity will be in worst case O(K*2N).

 ******************************************CODE GOES HERE ************************************************

#include<bits/stdc++.h>

using namespace std;

int h[12][105];

int dp[103][(1<<10)+7];

int n;

int mx;

#define mod 1000000007

int solve(int id,int bm)

{

   if(bm==mx)

   return 1;

   if(id>100)

   return 0;

   if(dp[id][bm]!=-1)

   return dp[id][bm];

   int ret=0;

   ret=solve(id+1,bm);

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

   {

        if((bm>>i&1)==0 && h[i][id]==1)

        {

         ret+=solve(id+1,bm|1<<i);

         if(ret>=mod)

         ret%=mod;

}

}

dp[id][bm]=ret;

return ret;

}

int main()

{   

         int t;

      //   freopen("abc.txt","r",stdin);

         cin>>t;

        // cout<<"test cases "<<t<<endl;

         while(t--)

         {

             memset(h,0,sizeof(h));

             memset(dp,-1,sizeof(dp));

            // int n;

             cin>>n;

             char ch;

             ch=getchar();

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

{

int pre=0;

   while((ch=getchar())!='\n')

  {

if(ch==' ')

{

// cout<<i<<" pre "<<pre<<endl;

h[i][pre]=1;

pre=0;

}

else

pre=(pre*10)+(ch-'0');

   }

//    cout<<"oer "<<pre<<endl;

h[i][pre]=1;

   }

//  cout<<"taken "<<endl;

mx=(1<<n)-1;

int res=solve(1,0);

 printf("%d\n",res);

}

return 0;

 

}