TSHIRTS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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

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

24 Likes
2

The first link redirects to a user’s page on codechef please fix the link(The similar problems link)

1 Like
3

Can you please provide some corner test cases. I am getting WA.

1 Like
4

How will u have a number with 100 bits??
Are doing it using array, then you can’t perform bitwise operators directly??

1 Like
5

What if a person doesn’t have that TSHIRT ?

1 Like
6

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]

11 Likes
7

Shouldn’t the expression in line 4 be -

if mask==(2**N)-1:
5 Likes
8

The number just needs 10 bits for the number of people. The tee shirt numbers are not part of the bitmask.

1 Like
9

Then don’t recurse. The code isn’t present, but the idea is represented as a comment.

1 Like
10

Also, the dp[][] array should be -

const int K=101;
dp[1<<N][K];

because clearly, we need the TSHIRT no. as the second index, not the user no.

2 Likes
11

can any one tell me bottom up approach to this problem. it would be great help.

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.

13

good tutorial :smiley: … helped a lot

1 Like
14

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 !!

15

http://ideone.com/dTD9nL Can someone tell me where im going wrong ?

16

He is definately oing 2 have a shirt read the question carefully,it says each person has atleast 1 shirt

17

This site might be useful http://www.geeksforgeeks.org/bitmasking-and-dynamic-programming-set-1-count-ways-to-assign-unique-cap-to-every-person/

18

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