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.

Hint1Binary seach

Hint2Let's

pref_{i}=a_{1}+a_{2}+ ... +a_{i}. Then should bepref_{i}>pref_{i - m}andpref_{i}>pref_{i - n}.Hint3Topological sort.

Hint4Length of the sequence is

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

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

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

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

yeah pretty nice