spookywooky's blog

https://atcoder.jp/contests/abc226

By spookywooky, history, 3 years ago, In English

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

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

Comments Comments (23)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

I would expect that it is the max loop length.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Consider $$$P = (2, 3, 1, 5, 4)$$$. 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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      Consider counting the number of permutations of such $$$(1, \ldots, N)$$$ that it consist of $$$k_1, \ldots, k_m$$$ cyclic permutations. These consist of two factors:

      What "cyclic permutation group" does each element belong?

      This is equivalent to determining such sequence $$$a_1, a_2, \ldots, a_n$$$ such that:

      • Each element $$$a_i$$$ is an integer between $$$0$$$ and $$$m$$$;
      • For each $$$j = 1, \ldots, m$$$, there are exactly $$$k_j$$$ elements such that $$$a_i = j$$$.

      So this means that element $$$i$$$ belongs a cyclic permutation group $$$a_i$$$, or does not belong to any cyclic permutation if $$$a_i = 0$$$.

      How many such sequences are there? Consider a sequence B = (($$$N - \sum k_j$$$ copies of $$$0$$$), ($$$k_1$$$ copies of $$$1$$$), ($$$k_2$$$ copies of $$$2$$$), $$$\ldots$$$, ($$$k_m$$$ copies of $$$m$$$)). This is an $$$n$$$-element sequence, and each permutation of $$$B$$$ correspond to the aforementioned $$$(a_i)$$$ one-to-one. Therefore, the number can be found as:

      $$$\displaystyle \frac{N!}{\prod_j k_j!}.$$$

      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 $$$\lbrace 1, 2, \ldots, Q \rbrace$$$, of length $$$Q$$$.

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

      Therefore, there are $$$(Q-1)!$$$ options.

      But wait, there's more!

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

      $$$\displaystyle \frac{N!}{\prod_j k_j!} \cdot \prod_j (k_j - 1)!.$$$

      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 $$$k_1, \ldots, k_m$$$ into the sequence of occurrences: $$$F_1$$$ elements of $$$k_1, \ldots, k_m$$$ are equal to $$$K_1$$$, $$$F_2$$$ elements are equal to $$$K_2$$$, and so on. Using this notation, the last expression can be re-written as follows:

      $$$\displaystyle \frac{N!}{\prod_{F_a, K_a} (K_a!)^{F_a}} \cdot \prod_{F_a, K_a} ((K_a - 1)!)^{F_a}.$$$

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

      $$$\displaystyle \frac{N!}{\prod_{F_a, K_a} (K_a!)^{F_a}} \cdot \prod_{F_a, K_a} \frac{((K_a - 1)!)^{F_a}}{F_a!}.$$$

      This is equivalent to the expression in the editorial.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Great.Someone explain me the reason of the solution in the editorial of problem E.Why same number of edges and nodes guarantee that there are exactly two possible ways of directing a particular connected component?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    The editorial seems to be updated.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

    A Connected graph with 'n' nodes and 'n' edges will definitely have a simple cycle. You can think of it as a ring graph.

    Since it is a directed graph, their are 2 ways — clockwise and counter-clockwise.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      Not a simple cycle, but a simple cycle with paths attached to it.

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    The last sample is what helped things click for me. It showed a disconnected case, but 2 different arrangements that worked... started with asking if the connected parts had to have a cycle (yes), and then testing what happened with variations based on the part that had a 3-cycle with a vert-and-edge pointing into it. Not a proof, and still had to whip up the brute force sim, but was enough to convince myself... edit: also helped to narrow down range of ok e vs. v relationships, testing out (eliminating) various other graphs like hourglass, 7-segment digital display, flow thingies (start, n mids, end), etc...

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      I used a different approach instead of e == v relationship. I started from leaf nodes and removed all the leaf nodes sequentially. After this, all the remaining nodes in the graph must have a degree of 2.

      Somewhat inspired from this of a recent Div 3 contest.

      → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone help me with [D].I can't understand how for case-> 3 (5,2),(7,2),(10,2) the answer is coming as 2 (https://atcoder.jp/contests/abc226/tasks/abc226_d)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In B I made a vector of strings,sorted them and calculated the answer.It gave WA and TLE on some tc.But when I made a vector of vectors, sorted them and then calculated the answer, it gave AC. Can someone plz explain this?

WA->(https://atcoder.jp/contests/abc226/submissions/27120194)

AC->(https://atcoder.jp/contests/abc226/submissions/27119995)

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    You basically make two mistakes:

    Step 1: try this
    Step 2: try this
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks for the reply ,understood my mistake! char wont take complete no ‘︿’

      → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

An "User Editorial" has been provided for problem F. Can someone explain how we are able to iterate through all possible LCMs without TLE?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Let's fix N = 50, and we want to estimate what the maximum LCM could be. This is equivalent to, if we partition N to be $$$N = a_{1} + a_{2} + ... + a_{m}$$$，the LCM would be $$$LCM = lcm(a_{1}, a_{2}, ..., a_{m})$$$. Apparently we should make every $$$a_{i}$$$ to be coprime with others, to avoid loss of LCM. So an optimal solution to this would be: $$$a_{1} = 1, a_{2} = 4, a_{3} = 5, a_{4} = 7, a_{5} = 9, a_{6} = 11, a_{7} = 13, LCM = 180180$$$. 180180 is a loose upper bound, considered that some numbers in [1, 180180] won't be a valid LCM(some large prime, etc.). Actually for N=50, there are only 1056 valid LCM. So enumerating all possible LCMs would be easily fit in the time limit.

    → Reply