The second task from day 1 of CEOI 2016 is a task with a solution that confuses me, not because it is hard to understand, but because of the fact that I cannot understand how someone could come up with it. When I read the official solution, it just looks like they shuffled some formulas around until they got an expression with an invariant with no real motivation for the process. Is there any, more intuitive approach for solving this problem? Thanks in advance.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jun/03/2024 05:23:45 (k2).
Desktop version, switch to mobile version.
Supported by
Auto comment: topic has been updated by dino_merlin (previous revision, new revision, compare).
Yes, there is a more intuitive solution. It uses a technique sometimes called "Connected Component DP". There is also comment under this blog explaining how to apply it to Kangaroo.