marcose18's blog

Help in An interesting problem
By marcose18, 10 years ago, In English

I have been solving this problem http://codeforces.com/problemset/problem/26/D .I was unable to solve this on my own and looked for editorials here http://codeforces.com/blog/entry/610 but one thing i am unable to figure out is If suppose we have a favourable order i.e. order which will smoothly run so we can also permute the people having 10 euros and 20 euros amongst themselves in n! and m! ways.This will account for a different pattern .I am unable to guess why is that not taken into account and only different combinations are considered.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Well, whether is sequence "good" or "bad" depends only on placement of people who have 10 euros and 20 euros. So we can divide all permutations of people in n!·m! classes. In each class all permutations are either "bad" or "good". So we can replace permutations with classes, because it doesn't affect freuqency of "bad" cases:

(first is amount of "bad" permutations, divided by amount of all permutations, second is value calculated in editorial).

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

yeah got it. Thank you Kaban-5

→ Reply