×

# TSHIRTS - Editorial

Author: Lalit Kundu
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

EASY-MEDIUM

# 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[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
if tid==101:    // all tshirts finished
return 0
if dp[mask][tid]!=-1:   // it has already been calculated, we won't calculate it again
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



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

# FURTHER LINKS AND SIMILAR PROBLEMS

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

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

(19 Aug '14, 22:35)

 13 The pseudo code accesses dp[mask][tid]. dp has size dp[1<
 5 Shouldn't the expression in line 4 be - if mask==(2**N)-1:  answered 11 Aug '14, 19:09 126●1●3 accept rate: 20%
 3 Also, the dp[][] array should be - const int K=101; dp[1<
 2 Can you please provide some corner test cases. I am getting WA. answered 11 Aug '14, 17:20 16●2●3 accept rate: 0%
 2 How will u have a number with 100 bits?? Are doing it using array, then you can't perform bitwise operators directly?? answered 11 Aug '14, 17:36 81●1●5 accept rate: 0% 1 The number just needs 10 bits for the number of people. The tee shirt numbers are not part of the bitmask. (11 Aug '14, 21:50)
 2 What if a person doesn't have that TSHIRT ? answered 11 Aug '14, 18:09 26●1●1●4 accept rate: 0% 1 Then don't recurse. The code isn't present, but the idea is represented as a comment. (11 Aug '14, 21:52) He is definately oing 2 have a shirt read the question carefully,it says each person has atleast 1 shirt (12 Dec '16, 19:56) vchhabra2★
 1 good tutorial :D .. helped a lot answered 04 Jun '15, 04:04 1★snehil92 95●2●2 accept rate: 0%
 0 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 2★xlee 13●1 accept rate: 0%
 0 http://ideone.com/dTD9nL Can someone tell me where im going wrong ? answered 02 Oct '15, 10:14 1 accept rate: 0%
 0 answered 28 Jun '17, 16:57 1 accept rate: 0%
 0 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 4★sonu_628 345●8 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,682
×2,172
×1,672
×281
×33
×21

question asked: 11 Aug '14, 15:13

question was seen: 14,114 times

last updated: 26 Aug '17, 15:52