You are not logged in. Please login at www.codechef.com to post your questions!

×

TSHIRTS - Editorial

25
14

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

This question is marked "community wiki".

asked 11 Aug '14, 15:13

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 29 Oct '14, 10:11

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) mohdwaseem0074★

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]

link

answered 11 Aug '14, 18:58

b_khan's gravatar image

3★b_khan
171112
accept rate: 0%

Shouldn't the expression in line 4 be -

if mask==(2**N)-1:
link

answered 11 Aug '14, 19:09

akash_goel23's gravatar image

2★akash_goel23
12613
accept rate: 20%

edited 15 Aug '14, 16:15

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.

link

answered 15 Aug '14, 16:16

akash_goel23's gravatar image

2★akash_goel23
12613
accept rate: 20%

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

(19 Aug '14, 22:34) mohdwaseem0074★

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

link

answered 11 Aug '14, 15:29

thechamp103's gravatar image

3★thechamp103
597411
accept rate: 16%

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

link

answered 11 Aug '14, 17:20

akhil_kumar's gravatar image

2★akhil_kumar
1623
accept rate: 0%

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

link

answered 11 Aug '14, 17:36

saurabhsuniljain's gravatar image

2★saurabhsuniljain
8115
accept rate: 0%

edited 11 Aug '14, 17:38

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) ingridmorstrad3★

What if a person doesn't have that TSHIRT ?

link

answered 11 Aug '14, 18:09

bkarthikeyan28's gravatar image

4★bkarthikeyan28
26114
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) ingridmorstrad3★

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★

good tutorial :D .. helped a lot

link

answered 04 Jun '15, 04:04

snehil92's gravatar image

1★snehil92
9522
accept rate: 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 !!

link

answered 23 Jul '15, 02:14

xlee's gravatar image

2★xlee
131
accept rate: 0%

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

link

answered 02 Oct '15, 10:14

darkmorning's gravatar image

5★darkmorning
1
accept rate: 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

link

answered 26 Aug '17, 14:23

sonu_628's gravatar image

4★sonu_628
3458
accept rate: 8%

edited 26 Aug '17, 15:52

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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