Challenging "Butts"

Problem D - Challenging "Butts"

Despite the interesting name, and somewhat tedious flavourtext, the actual underlying question was, to me, the best of the set (close to problem C).

So, ignoring the darts stuff, we're given a circular track which is split radially into N >= 3 sectors, and also halved along the centre of the track, giving us 2N zones in total. We then are given numbers, and have to place them one per zone, such that the sum of differences across all zones sharing a border is a maximum.

It turns out that one greedy assignment will work - start in one sector, place the highest on the outside and the lowest on the inside, move to the next sector, place the next highest on the inside and the next lowest on the outside, etc...

However, why this works is not immediately obvious. From what I've heard many groups submitted this without proof of correctness - while it's an ok strategy if the proof would take some time, doing this could be costly, and extremely so if you're doing a contest where you don't get immediate feedback (like the IOI or TopCoder).

The proof itself is quite nice, and has the added benefit of making the code very short. It comes in two parts.
1) If the number of sectors is even:

Because it's even, you can add a checkerboard pattern to the zones as seen above, and always you will get a purple next to a pink at each border. Now, say we assign the highest values to the pink sections and the lowest to the purple, all of our border differences will look like |high_i - low_j| - i.e. adding the absolute difference will always result in a high number being added, and a low number subtracted. Because each zone is adjacent to 3 more, the overall affect is that each high number is added 3 times, and each lower is subtracted 3 times.
Two things about this configuration:

• Maybe surprisingly, it doesn't matter at all where you place the high or low numbers, so long as you alternate them! this means that most greedy solutions will work for these boards.
• This is THE best solution - anything else will result in at least one high - high and low - low border, which would be worse than that solution above. If there are 3N absolute differences, then 3N numbers must be added, and 3N must be subtracted, so you can do no better than adding the highest and subtracting the lowest.
  

This solves the even case optimally, we can use the observations to now solve it if:
2) The number of sectors is odd:

The interesting part happens now in the hilighted zones, where we are forced to have high-high and low-low. If you think how this changes our original answer, it means that the lower of the two highs has changed from being added, to being subtracted from the total, and the higher of the two lows is now being added.
That is, we've gone from (higha - lowa) + (highb - lowb) to (higha - highb) + (lowa - lowb), in other words, previousAnswer - 2 * highb + 2 * lowA. As this is the only difference, it's clear that the high value to 'demote' (i.e. highb) should be the lowest high value, and the low value being 'promoted' (i.e. lowa) is the highest low value.

Implementing this small fiddle then completes the formula for both even and odd sectors, and using some inbuilt C++ functions, we get an implementation that looks like this. If this question had a moral, it would be that it often pays to think more, allowing you to code less [which is why I liked it]