### PROBLEM LINK:

**Author:** Lalit Kundu

**Tester:** Praveen Dhinwa and Hiroto Sekido

**Editorialist:** Lalit Kundu

### DIFFICULTY:

EASY-MEDIUM

### 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 2-D 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.

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*2^{N}).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution

Tester’s solution

### FURTHER LINKS AND SIMILAR PROBLEMS

A little bit of classics: dynamic programming over subsets and paths in graphs

SOCOLA

Topcoder Problem

Dp with Bitmasking