enoone's blog

IZHO18 nice sequence
By enoone, history, 5 years ago, In English

I am now trying to solve problems from IZHO 2018. I have already done 3 problems, but now I am stuck on problem 2 from the second day called "nice sequence". I don't have any idea and can't find the solution anywhere. Can you help me?

P.S. You can find the problem here.

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

»
5 years ago, # |
  Vote: I like it +37 Vote: I do not like it
Hint1
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    can u prove that Length of the sequence is n + m - gcd(n, m) - 1 ?

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

      It's similar to Periodicity Lemma. The difference is the edges turn from undirected to directed.

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

      The previos is fake proof.. I can only prove $$$n+m-1$$$ now.

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

      I have completed the proof. Maybe better to say learning the proof from arc127f. Orz maroonrk!

      Assume $$$A,B$$$ are coprime. If we can transition from $$$x$$$ to $$$x+A$$$ by $$$+A,-B$$$, add an edge $$$(x,x+A)\bmod B$$$. If $$$n>=A+B$$$, it forms a single loop. We only need to prove the case when $$$n=A+B-1$$$, that there must exists a valid solution.

      We can find that all nodes except $$$A$$$ has in-degree, and all except $$$B$$$ has out-degree. So the graph looks like a chain. We can easily construct a topological sequence by the chain.

      In fact we have proved the Periodicity Lemma..

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

yeah pretty nice

→ Reply