Saturday, 12 March 2016

                                          BITMASKING DP



Little Elephant and T-Shirts 
Solved

Problem code: TSHIRTS

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 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-Shirtsith person has.

Output

For each test case, print in single line the required number of ways modulo 1000000007 = 109+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;
 
}




No comments:

Post a Comment