### 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 extreme…

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 extreme…