Please help me how to solve this question https://www.codechef.com/problems/TSHIRTS
Subset DP. Consider the T-shirts in increasing order of numbers and remember how many ways there have been so far to pick T-shirts (with lower numbers) for each subset of people. You can pick this new shirt for anyone who still hasn’t got it in any subset, which gives you some new ways for some new subsets. The final answer is the number of ways for the subset of all people.
Btw it’s the problem of counting perfect bipartite matchings.
2 Likes
can you provide the dp formula for the problem?
dp[k+1][s] +=dp[k][s]; dp[k+1][{s,i}] +=dp[k][s] if person i has a T-shirt with type k and isn’t present in subset s