PROBLEM LINK:Author: Lalit Kundu DIFFICULTY:EASYMEDIUM PREREQUISITES:Dynamic Programming, Bitmasking, Recursion PROBLEM:There are N(<11) persons. Each person has his collection of distinct tshirts. What are the total number of different such arrangements such in which no two people wear same kind of tshirt. A person can have atmost 100 distinct tshirts. EXPLANATION:It is a very standard kind of Dynamic Programming with bitmasking. So the idea here is to keep a 2D array DP[2^{N}][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 b_{1},b_{2}...b_{n}. If b_{p}(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.
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*2^{N}). AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution FURTHER LINKS AND SIMILAR PROBLEMSA little bit of classics: dynamic programming over subsets and paths in graphs
This question is marked "community wiki".
asked 11 Aug '14, 15:13

The pseudo code accesses dp[mask][tid]. dp has size dp[1<<N][N] where N<11 but tid < 101. Here tid can clearly go outside the limit of the array. In the actual code you have created array dp[1025][109] answered 11 Aug '14, 18:58

Shouldn't the expression in line 4 be 
answered 11 Aug '14, 19:09

Also, the dp[][] array should be 
because clearly, we need the TSHIRT no. as the second index, not the user no. answered 15 Aug '14, 16:16

The first link redirects to a user's page on codechef please fix the link(The similar problems link) answered 11 Aug '14, 15:29

Can you please provide some corner test cases. I am getting WA. answered 11 Aug '14, 17:20

I think the complexity will be O( 2^N * K * N ) . Morover, if someone wants to see a backward implementation of this problem, can check my submission . Also, One can check a very similar problem ASSIGN on spoj. This problem + ASSIGN on spoj gives you two or more ways of solving this problem. In general when we need a set we can have options !! That is a very beautiful thing! One should learn that rather learn should feel that !! answered 23 Jul '15, 02:14

http://ideone.com/dTD9nL Can someone tell me where im going wrong ? answered 02 Oct '15, 10:14

This site might be useful http://www.geeksforgeeks.org/bitmaskinganddynamicprogrammingset1countwaystoassignuniquecaptoeveryperson/ answered 28 Jun '17, 16:57

in the solution if (mask == p) then 111 is returned and if not 011 is returned where p is all set mask . Can somebody tell me why? Because there no mention about it in the pseudo code answered 26 Aug '17, 14:23

can anyone tell me bottom up approach to this problem. i m not able to figure out how to define state in this problem.