apnakaamkar's blog

O — Matching (Educational DP Contest,Atcoder)
By apnakaamkar, history, 5 years ago, In English

Could anyone please explain to me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_o Please help?

  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

dp[i][mask] = Number of ways to match first i men with the set of women indicated by the mask, 0 <= i <= n, 0 <= mask <= 2^n. Obviuosly, if i != popcount(mask), dp[i][mask] = 0.

Fill the dp table by iterating over i and mask. When you fill dp[i][mask], you iterate over all possible pairing of i-th man with a woman. So the transition is dp[i][mask] = (sum of dp[i-1][mask ^ 1 << j] where j-th woman appeared in the mask). Code

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oof I implemented the same method in recursive way and it got TLE

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

You can refer to explanation by FlowerOfSorrow(above comment) and this code — https://atcoder.jp/contests/dp/submissions/15835680

→ Reply