Kar98k's blog

By Kar98k, history, 4 weeks ago, ,

https://codeforces.com/problemset/problem/118/D

In the above question, most of the people have solved it using dp but i am trying it using pnc.

My approach is that first i am calculating all possible ways of arranging n1 soldiers and n2 horses which is (n1+n2)C(n1) ways.

Then i am grouping (k1+1) soldiers and calculating all possible ways of arranging them. This value is equal to (n1-k1+n2)!/(n1-k1-1)!(n2)!. This value should be substracted from the total ways.

Then i am grouping (k2+1) soldiers and calculating all possible ways of arranging them. This value is equal to (n2-k2+n1)!/(n2-k2-1)!(n1)!. This value should be substracted from the total ways.

Then i am calculating the intersection of the above two cases as it has been substracted two times from the total cases. This value is equal to (n1-k1+n2-k2)!/(n1-k1-1)!(n2-k2-1)!. This value is added in total possible ways to eliminate double counting from the above two cases.

I have also taken care of the fact that we will group soldiers or horses only when it would be possible to group them i.e., (n1>k1) , (n2>k2) for respective cases.

I am getting WA. I cant figure out which case i am missing and need help.

https://codeforces.com/contest/118/submission/48761414

Thanks in advance for the time and help. ;)

•
• -13
•

 » 4 weeks ago, # | ← Rev. 4 →   +4 Try to be dumber don't lose your time :) https://noi.ph/training/weekly/week3.pdfA non-brute force solution would be to realize that all we are really choosing is where to put the n1 footmen among the n1 + n2 soliders. This is (n1+n2)C(n1). We could have also chosen where to put the n2 horsemen instead, giving us (n1+n2)C(n2), which happens to be equal to (n1+n2)C(n1). But this is too smart! It’s so smart, that it’s now quite difficult to add into our holy, pristine formula the constraints we initially decided to ignore. Remember, DP = bruteforce + memoization. So we need to think brute force. Let’s try to be dumber. Thinking about producing entire sequences at once is too hard. So, we will break down the choice for the entire sequence into a series of smaller choices or stages, and consider building sequences step-by-step. This naturally leads us into thinking about doing DP on prefixes. A first attempt at the state might be C(i), where i is the number of soldiers we have yet to pick, 0 ≤ i ≤ n1 + n2. 
•  » » 4 weeks ago, # ^ |   0 Yup, I have figured out the dp approach. I just wanted to know whats wrong in my approach or which case was i missing.