enoone's blog

By enoone, history, 3 years ago,

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.

• +21

 » 3 years ago, # |   +37 Hint1Binary seach Hint2Let's prefi = a1 + a2 + ... + ai. Then should be prefi > prefi - m and prefi > prefi - n. Hint3Topological sort. Hint4Length of the sequence is n + m - gcd(n, m) - 1.
•  » » 4 months ago, # ^ |   +9 can u prove that Length of the sequence is n + m - gcd(n, m) - 1 ?
•  » » » 4 months ago, # ^ |   +10 It's similar to Periodicity Lemma. The difference is the edges turn from undirected to directed.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +5 The previos is fake proof.. I can only prove $n+m-1$ now.
•  » » » 4 months ago, # ^ |   +16 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..
 » 4 months ago, # |   0 yeah pretty nice