dumbhead's blog

SPOJ SFLIP
By dumbhead, 11 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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:

123456789
-+-+++-+-

becomes

123456789
-++---++-

But you later find out that you actually want to flip 1-3 and 7-9:

123456789
+-+++++-+

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://codeforces.net/problemset/problem/280/D and the APIO task "Backup" for more.

→ Reply