Little Elephant and T-Shirts | CodeChef Solution

Leave a Comment / CodeChef / By

Hello coders, today we are going to solve Little Elephant and T-Shirts CodeChef Solution whose Problem Code is TSHIRTS.

Little Elephant and T-Shirts

Task

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 Format

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 N lines contains at least 1 and at most 100 space separated distinct integers, denoting the ID’s of the T-Shirts ith person has.

Output Format

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

Sample Input

2
2
3 5
8 100
3
5 100 1
2
5 100

Sample 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).

Solution – Little Elephant and T-Shirts

C++

#include <bits/stdc++.h>
#define GREEN "\033[32m"
#define MAGENTA "\033[35m"
#define RESET "\033[0m"
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
#ifdef BCDBG
#define tcT template<typename T
tcT,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p) {return os<<"("<<p.first<<", "<<p.second<<")";}
tcT,typename U=typename enable_if<!is_same<T,string>::value,typename T::value_type>::type> ostream& operator<<(ostream &os,const T &v)
{os<<"\n{";string sep;for(const U &x:v)os<<sep<<x,sep=", ";return os<<'}';}
void debug_help() {cout<<RESET<<endl;}
tcT,typename... U> void debug_help(T t,U... u) {cout<<t;if(sizeof...(u))cout<<", ";debug_help(u...);}
int debug_dms[10],debug_md;
void debug_fill() {}
tcT,typename... U> void debug_fill(T t,U... u) {debug_dms[debug_md++]=t;debug_fill(u...);}
tcT> void debug_arr(T x,int d) {cout<<x;}
tcT> void debug_arr(T* arr,int d)
{cout<<"\n{";string sep;for(int i=0;i<debug_dms[d];i++)cout<<sep,sep=", ",debug_arr(arr[i],d+1);cout<<'}';if(d==0)cout<<RESET<<endl;}
#define dbg(...) cout<<MAGENTA<<__LINE__<<" ["<<#__VA_ARGS__<<"]: "<<GREEN,debug_help(__VA_ARGS__)
#define dba(arr,...) cout<<MAGENTA<<__LINE__<<" ["<<#arr<<"]: "<<GREEN,debug_md=0,debug_fill(__VA_ARGS__),debug_arr(arr,0)
#else
#define dbg(...)
#define dba(arr,...)
#endif
typedef long long ll;
typedef unsigned long long ull;
const char df = '\n';

vector<string> split(const string& s) {
  int a = 0, b = 0, n = s.size();
  vector<string> r;
  while (b < n) {
    while (b < n && !isspace(s[b])) b++;
    r.push_back(s.substr(a, b - a));
    while (b < n && isspace(s[b])) b++;
    a = b;
  }
  return r;
}

const int mod = 1e9+7;

int add(int a, int b) {
  int c = (a + b) % mod;
  if (c < 0) c += mod;
  return c;
}

int n;
string line;
int has[10][101];
int dp[101][1 << 10];

void solve() {
  memset(has, 0, sizeof(has));
  getline(cin, line);
  n = stoi(line);
  for (int i = 0; i < n; i++) {
    getline(cin, line);
    auto r = split(line);
    for (auto& x:r) {
      has[i][stoi(x)] = 1;
    }
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i < 101; i++) {
    for (int mk = 0; mk < (1 << n); mk++) {
      dp[i][mk] = add(dp[i - 1][mk], dp[i][mk]);
      for (int j = 0; j < n; j++) {
        if ((mk >> j & 1) == 0 && has[j][i]) {
          dp[i][mk | 1 << j] = add(dp[i][mk | 1 << j], dp[i - 1][mk]);
        }
      }
    }
  }
  int total = 0;
  for (int mk = 0; mk < (1 << n); mk++) {
    if (__builtin_popcount(mk) == n) {
      total = add(total, dp[100][mk]);
    }
  }
  cout << total << df;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  getline(cin, line);
  int tt = stoi(line);
  for (int i = 1; i <= tt; i++) {
    solve();
  }
  return 0;
}

Python

mod = 1e9+7
import numpy as np 

t = int(input())
for _ in range(t):
    n = int(input())
    ingr = [0]*101
    for i in range(n):
        for shirt in map(int, input().split(' ')):
            ingr[shirt] |= (1<<i)
    
    dp = [[0 for _ in range((1<<n) + 1)] for _ in range(101)]
    
    dp[0][0] = 1
    for i in range(1, 101):
        for mask in range(1<<n):
            dp[i][mask] += int(dp[i-1][mask])
            dp[i][mask] %= mod
            tmask = mask
            while tmask != 0:
                bit = tmask & (-tmask)
                if (bit & ingr[i]):
                    dp[i][mask] += int(dp[i-1][mask ^ bit])
                    dp[i][mask] %= mod
                tmask -= bit
    
    print(int(dp[100][(1<<n)-1]))

Java

import java.util.*;
import java.io.*;
import java.math.*;

public class Main

{ 
	 static FastReader sc=new FastReader(); 
	 static long dp[][];
	 static int mod=1000000007;
	 static int max;
	  public static void main(String[] args)
{
		   PrintWriter out=new PrintWriter(System.out);
		   //StringBuffer sb=new StringBuffer("");
		  int ttt=1;
		    ttt =i();
		     
	        outer :while (ttt-- > 0) 
			{
	        	int n=i();
	        	ArrayList<Integer> AA[]=new ArrayList[101];
	        	for(int i=0;i<101;i++)
	        		AA[i]=new ArrayList<Integer>();
	        	for(int i=0;i<n;i++) {
	        		String s=sc.nextLine().trim();
	        		String B[]=s.split(" ");
	        		for(String ss : B) {
	        			int y=Integer.parseInt(ss);
	        			AA[y].add(i);
	        		}
	        	}
	        	int A[][]=new int[101][];
	        	for(int i=1;i<101;i++) {
	        		A[i]=new int[AA[i].size()];
	        		for(int j=0;j<AA[i].size();j++) {
	        			A[i][j]=AA[i].get(j);
	        			//System.out.println(A[i][j]+" "+i+" "+j);
	        		}
	        	}
	        	dp=new long[101][1<<n];
	        	for(int i=0;i<101;i++) {
	        		Arrays.fill(dp[i],-1);
	        	}
	        	System.out.println(go(A, 1, (1<<n)-1, n));
	        	
	        }
	        	
		
		  
		  

	     //System.out.println(sb.toString());
		     out.close();
	     
	     
	    //CHECK FOR N=1                    //CHECK FOR M=0
        //CHECK FOR N=1                    //CHECK FOR M=0
       	//CHECK FOR N=1
       	//CHECK FOR N=1
       	//CHECK FOR N=1
		        
		     
    }
	  static long go(int A[][],int i,int mask,int n) {
		  if(mask==0)
			  return 1;
		  if(i==A.length)
			  return 0;
		  if(dp[i][mask]!=-1)
			  return dp[i][mask];
		  long ans=go(A, i+1, mask, n);
		  ans%=mod;
		  for(int j : A[i]) {
			  if((mask&(1<<j))>0) {
				  ans+=go(A, i+1, mask^(1<<j), n);
				  ans%=mod;
			  }
		  }
		  return dp[i][mask]= ans;
		  
	  }
	  
	  
	  
	  
	  
	  

static class Pair implements Comparable<Pair>
     {
    	 long x;
    	 long y;
    	 Pair(long x,long y){
    		 this.x=x;
    		 this.y=y;
    		 
    	 }
		@Override
		public int compareTo(Pair o) {
			if(this.x>o.x)
				return 1;
			else if(this.x<o.x)
				return -1;
			else {
				if(this.y>o.y)
					return 1;
				else if(this.y<o.y)
					return -1;
				else
					return 0;
			}
		}
		
		/* FOR TREE MAP PAIR USE */
		
//		public int compareTo(Pair o) {
// 			if (x > o.x) {
// 				return 1;
// 			}
// 			if (x < o.x) {
// 				return -1;
// 			}
// 			if (y > o.y) {
// 				return 1;
// 			}
// 			if (y < o.y) {
// 				return -1;
// 			}
// 			return 0;
// 		}
	
		
     }

static int[] input(int n) {
	int A[]=new int[n];
	   for(int i=0;i<n;i++) {
		   A[i]=sc.nextInt();
	   }
	   return A;
   }
static long[] inputL(int n) {
	long A[]=new long[n];
	   for(int i=0;i<n;i++) {
		   A[i]=sc.nextLong();
	   }
	   return A;
   }
static String[] inputS(int n) {
	String A[]=new String[n];
	   for(int i=0;i<n;i++) {
		   A[i]=sc.next();
	   }
	   return A;
   }
static long sum(int A[]) {
	long sum=0;
	for(int i : A) {
		sum+=i;
	}
	return sum;
}
static long sum(long A[]) {
	long sum=0;
	for(long i : A) {
		sum+=i;
	}
	return sum;
}
static void reverse(long A[]) {
	int n=A.length;
	long B[]=new long[n];
	for(int i=0;i<n;i++) {
		B[i]=A[n-i-1];
	}
	for(int i=0;i<n;i++)
		A[i]=B[i];
	
}
static void reverse(int A[]) {
	int n=A.length;
	int B[]=new int[n];
	for(int i=0;i<n;i++) {
		B[i]=A[n-i-1];
	}
	for(int i=0;i<n;i++)
		A[i]=B[i];
	
}
static void input(int A[],int B[]) {
	   for(int i=0;i<A.length;i++) {
		   A[i]=sc.nextInt();
		   B[i]=sc.nextInt();
	   }
}
static int[][] input(int n,int m){
	int A[][]=new int[n][m];
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			A[i][j]=i();
		}
	}
	return A;
}
static char[][] charinput(int n,int m){
	char A[][]=new char[n][m];
	for(int i=0;i<n;i++) {
		String s=s();
		for(int j=0;j<m;j++) {
			A[i][j]=s.charAt(j);
		}
	}
	return A;
}
static int find(int A[],int a) {
	  if(A[a]==a)
		  return a;
	  return A[a]=find(A, A[a]);
}
static int max(int A[]) {
	int max=Integer.MIN_VALUE;
	for(int i=0;i<A.length;i++) {
		max=Math.max(max, A[i]);
	}
	return max;
}
static int min(int A[]) {
	int min=Integer.MAX_VALUE;
	for(int i=0;i<A.length;i++) {
		min=Math.min(min, A[i]);
	}
	return min;
}
static long max(long A[]) {
	long max=Long.MIN_VALUE;
	for(int i=0;i<A.length;i++) {
		max=Math.max(max, A[i]);
	}
	return max;
}
static long min(long A[]) {
	long min=Long.MAX_VALUE;
	for(int i=0;i<A.length;i++) {
		min=Math.min(min, A[i]);
	}
	return min;
}
static long [] prefix(long A[]) {
	long p[]=new long[A.length];
	p[0]=A[0];
	for(int i=1;i<A.length;i++)
		p[i]=p[i-1]+A[i];
	return p;
}
static long [] prefix(int A[]) {
	long p[]=new long[A.length];
	p[0]=A[0];
	for(int i=1;i<A.length;i++)
		p[i]=p[i-1]+A[i];
	return p;
}
static long [] suffix(long A[]) {
	long p[]=new long[A.length];
	p[A.length-1]=A[A.length-1];
	for(int i=A.length-2;i>=0;i--)
		p[i]=p[i+1]+A[i];
	return p;
}
static long [] suffix(int A[]) {
	long p[]=new long[A.length];
	p[A.length-1]=A[A.length-1];
	for(int i=A.length-2;i>=0;i--)
		p[i]=p[i+1]+A[i];
	return p;
}
static int min(int a,int b) {
	return Math.min(a, b);
}
static int min(int a,int b,int c) {
	return Math.min(a, Math.min(b, c));
}
static int min(int a,int b,int c,int d) {
	return Math.min(a, Math.min(b, Math.min(c, d)));
}
static int max(int a,int b) {
	return Math.max(a, b);
}
static int max(int a,int b,int c) {
	return Math.max(a, Math.max(b, c));
}
static int max(int a,int b,int c,int d) {
	return Math.max(a, Math.max(b, Math.max(c, d)));
}
static long min(long a,long b) {
	return Math.min(a, b);
}
static long min(long a,long b,long c) {
	return Math.min(a, Math.min(b, c));
}
static long min(long a,long b,long c,long d) {
	return Math.min(a, Math.min(b, Math.min(c, d)));
}
static long max(long a,long b) {
	return Math.max(a, b);
}
static long max(long a,long b,long c) {
	return Math.max(a, Math.max(b, c));
}
static long max(long a,long b,long c,long d) {
	return Math.max(a, Math.max(b, Math.max(c, d)));
}

static long power(long x, long y, long p)
{

	if(y==0)
		return 1;
	if(x==0)
		return 0;
    long res = 1;
    x = x % p;

    while (y > 0) {

        if (y % 2 == 1)
            res = (res * x) % p;

        y = y >> 1; 
        x = (x * x) % p;
    }

    return res;
}
static void print(int A[]) {
	for(int i : A) {
		System.out.print(i+" ");
	}
	System.out.println();
}
static void print(long A[]) {
	for(long i : A) {
		System.out.print(i+" ");
	}
	System.out.println();
}
static long mod(long x) {
	  return ((x%mod + mod)%mod);
}
static String reverse(String s) {
	StringBuffer p=new StringBuffer(s);
	p.reverse();
	return p.toString();
}

     static int i() {
    	 return sc.nextInt();
     }
     static String s() {
    	 return sc.next();
     }
     static long l() {
    	 return sc.nextLong();
     }  
     static void sort(int[] A){
        int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            int tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
     }
     static void sort(long[] A){
	        int n = A.length;
	        Random rnd = new Random();
	        for(int i=0; i<n; ++i){
	            long tmp = A[i];
	            int randomPos = i + rnd.nextInt(n-i);
	            A[i] = A[randomPos];
	            A[randomPos] = tmp;
	        }
	        Arrays.sort(A);
	     }
  static String sort(String s) {
 	 Character ch[]=new Character[s.length()];
 	 for(int i=0;i<s.length();i++) {
 		 ch[i]=s.charAt(i);
 	 }
 	 Arrays.sort(ch);
 	 StringBuffer st=new StringBuffer("");
 	 for(int i=0;i<s.length();i++) {
 		 st.append(ch[i]);
 	 }
 	 return st.toString();
  }
  static HashMap<Integer,Integer> hash(int A[]){
	  HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
	  for(int i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
  }
  static TreeMap<Integer,Integer> tree(int A[]){
	  TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>();
	  for(int i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
  }
     static boolean prime(int n) 
	    { 
	        if (n <= 1) 
	            return false; 
	        if (n <= 3) 
	            return true; 
	        if (n % 2 == 0 || n % 3 == 0) 
	            return false; 
	        double sq=Math.sqrt(n);
	  
	        for (int i = 5; i <= sq; i = i + 6) 
	            if (n % i == 0 || n % (i + 2) == 0) 
	                return false; 
	        return true; 
	    } 
     static boolean prime(long n) 
	    { 
	        if (n <= 1) 
	            return false; 
	        if (n <= 3) 
	            return true; 
	        if (n % 2 == 0 || n % 3 == 0) 
	            return false; 
	        double sq=Math.sqrt(n);
	  
	        for (int i = 5; i <= sq; i = i + 6) 
	            if (n % i == 0 || n % (i + 2) == 0) 
	                return false; 
	        return true; 
	    } 
     static int gcd(int a, int b) 
     { 
         if (a == 0) 
             return b; 
         return gcd(b % a, a); 
     } 
     static long gcd(long a, long b) 
     { 
         if (a == 0) 
             return b; 
         return gcd(b % a, a); 
     } 
     
        
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}

Disclaimer: The above Problem (Little Elephant and T-Shirts) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *