wadhwasahil's blog

Need help to solve this problem
By wadhwasahil, history, 11 years ago, In English

I am quite weak in DP and Bitmasking concept. I need help to solve this problem https://www.codechef.com/problems/TSHIRTS

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wadhwasahil (previous revision, new revision, compare).

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Look at the editorial it is quiet good. You may want to look at problem : http://www.spoj.com/problems/ASSIGN/

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I couldn't submit my solution in Codechef because when I click on "Submit", it sends me back to the problem statement like nothing happened.

Well... anyway, what I did was, first make a list of all people that can wear each shirt, then iterate on shirts and try to assign them to unassigned people. So let's have DP[i][m] which means ways to reach a state where I processed the first i shirts and the people in mask m have been assigned a shirt already. The answer will be DP[100][2N - 1].

→ Reply