I was trying this problem SFLIP but I am not able to come up with a solution. Is the intended solution requires a segment tree approach ? I would be happy if somebody helps me in solving this problem ? Thank you in advance.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/05/2024 03:20:58 (l1).
Desktop version, switch to mobile version.
Supported by
It seems like it's possible to use a segment tree, but it's not necessary. A key insight that admits a priority queue based approach is that if you've flipped some segment, then later on find out that you can do better by not flipping it, you can "fix" the end result and pretend you never flipped that segment at all.
Say you flip 3-7 here:
becomes
But you later find out that you actually want to flip 1-3 and 7-9:
It's possible to quickly find and effect this "fix" operation using a priority queue.
Actually, if you consider that you can just treat all contiguous runs of numbers of the same sign as single numbers, you can see that this is equivalent to finding a shortest augmenting path in a weighted bipartite graph.
See http://mirror.codeforces.com/problemset/problem/280/D and the APIO task "Backup" for more.