apnakaamkar's blog

O — Matching (Educational DP Contest,Atcoder)
By apnakaamkar, history, 6 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?
»
6 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
6 years ago, hide # |
 
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