Блог пользователя marcose18

Help in An interesting problem
Автор marcose18, 10 лет назад, По-английски

I have been solving this problem http://mirror.codeforces.com/problemset/problem/26/D .I was unable to solve this on my own and looked for editorials here http://mirror.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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

yeah got it. Thank you Kaban-5

→ Ответить