F: The Ninja Way
This problem turned out to be harder than we expected. We rated it a C/D, yet only 2 teams managed to solve it, the first coming about three and a half hours into the contest. It’s really not a difficult algorithm, but it’s off the beaten path, and requires some thinking and some care.
Check out the Judge Input, the Judge Output, the main Solving Program, another java solution, and one in C++.
Look in the spoiler for a description of a solution.
[spoiler]
Use a Greedy algorithm. First, assume that the trees are laid out right next to each other, as tightly as possible. Then, find the positions of the smallest and largest trees – let’s say s and t – and then try to stretch the gap between s and s+1 as far as possible, then the gap between s+1 and s+2, then s+2 and s+3, all the way up to t-1 and t. Look at all pairs of trees that are adjacent height-wise (that the Ninjas would jump between) that span each of those gaps, to see how far the gaps can be stretched.
The only way the Greedy algorithm can fail is if stretching an early gap limits your options of stretching a later gap. I’m not going to go through a convoluted argument, but it’s true. It’s left as an exercise to the reader to confirm!
[/spoiler]