| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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.
Binary seach
Let's prefi = a1 + a2 + ... + ai. Then should be prefi > prefi - m and prefi > prefi - n.
Topological sort.
Length 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