Kar98k's blog

By Kar98k, history, 4 weeks ago, In English,

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. ;)

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

»
4 weeks ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

Try to be dumber don't lose your time :)

https://noi.ph/training/weekly/week3.pdf
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup, I have figured out the dp approach. I just wanted to know whats wrong in my approach or which case was i missing.