4

https://atcoder.jp/contests/abc226

 2 years ago
source link: http://codeforces.com/blog/entry/96714
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
https://atcoder.jp/contests/abc226 - Codeforces

Apparently there is no official announcement, so I hijack this. Ask questions here.

17 hours ago, # |

← Rev. 2 →  

+8

F Editorial says S(p) is the LCM of the loop lengths. Why this?

I would expect that it is the max loop length.

  • 17 hours ago, # ^ |

    For something like 2 3 1 5 4 the max loop from the first 3 is 3, but if you simulate it through 3 iterations, the first 3 are ok but the last 2 are in the 'odd' phase of their 2-cycle.

  • 17 hours ago, # ^ |

    ← Rev. 2 →  

    +9

    Consider . The ball wills move like this:

    • 2, 3, 1, 5, 4
    • 3, 1, 2, 4, 5
    • 1, 2, 3, 5, 4

    After Snuke shouts three times, Person 4 has Ball 5, so 3 (the maximum loop length) is not an appropriate answer.

    • 15 hours ago, # ^ |

      Each time Snuke screams, every Person i such that gives their ball to Person simultaneously.

      Doesn't that mean, that after the first exchange, and men have to stop exchanging? That's misunderstanding in statement. I counted max loop lengthes.

      • 15 hours ago, # ^ |

        don't change after people pass balls. They are elements of a fixed permutation .

      • 14 hours ago, # ^ |

        I mixed that up, too. But I think the statement is clear. Especially allways all persons give their ball to p[i]. It is just that i!=p[i], because if i==p[i] that ball would never move at all.

  • 15 hours ago, # ^ |

    Can anyone please explain the formula given in the editorial for getting the count of each partitions ? It would be of great help.

    • 14 hours ago, # ^ |

      ← Rev. 3 →  

      +1

      Consider counting the number of permutations of such that it consist of cyclic permutations. These consist of two factors:

      What "cyclic permutation group" does each element belong?

      This is equivalent to determining such sequence such that:

      • Each element is an integer between and ;
      • For each , there are exactly elements such that .

      So this means that element belongs a cyclic permutation group , or does not belong to any cyclic permutation if .

      How many such sequences are there? Consider a sequence B = (( copies of ), ( copies of ), ( copies of ), , ( copies of )). This is an -element sequence, and each permutation of correspond to the aforementioned one-to-one. Therefore, the number can be found as:

      What does each cyclic permutation look like?

      Given a set of elements that forms a cyclic permutation, we have to determine the actual permutation. For simplicity, we consider a cyclic permutation of , of length .

      What should map to? It should not map to itself, since it will never result in a cyclic permutation of length . Therefore there are choices. Say maps to . What should map to? It should not map to , because it becomes a cyclic group of length ; nor should it map to itself. So there are choices. The next element has choices for its next mapping direction, the next has , ... and so on, before determine the destination of the last element, which should now go back to (no other option).

      Therefore, there are options.

      But wait, there's more!

      To sum up the last two sections, we obtain the following number:

      However, in the first chapter we distinguished the cyclic group with the same length. So we have to divide by an additional duplicate-remover.

      To do this, let's convert the sequence into the sequence of occurrences: elements of are equal to , elements are equal to , and so on. Using this notation, the last expression can be re-written as follows:

      Now we can divide by the freedom of permutation of same-length cycles:

      This is equivalent to the expression in the editorial.

  • 13 hours ago, # ^ |

    If you know some group theory, you will notice that is the "order" of the permutation. If you google this term, you'll probably find a proof for why is the LCM of the lengths of the disjoint cycles (what you call loop lengths).


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK