TSHIRTS - Editorial

editorial
, , , ,
3

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

2 Likes
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]

12 Likes
7

Shouldn’t the expression in line 4 be -

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

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
9

good tutorial :smiley: … helped a lot

1 Like
10

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

11

dTD9nL - Online C++ Compiler & Debugging Tool - Ideone.com Can someone tell me where im going wrong ?

12

This site might be useful Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique cap to every person) - GeeksforGeeks

1 Like
13

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

14

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

1 Like
15

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

1 Like
16

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

17

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

18

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

19

How to do it in a bottom-up fashion, anybody has any idea?
@l_returns @anon55659401 @ssjgz

20

I won’t be active on discuss for this week :slight_smile:
@l_returns and @ssjgz might surely help :wink:

2 Likes
21

Here is my attempt to explain the approach to an exactly similar problem
Tshirt Codechef

22

Can pls someone tell how to take the input.Like in the first case,how would we know if a person has 2 or 3 tshirts.How do i know that the next tshirt is for another guy.