Блог пользователя wadhwasahil

Автор wadhwasahil, история, 9 лет назад, По-английски

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

Thanks.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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