Editorial for COCI '11 Contest 4 #4 Ograda
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's mark the smallest board that Mirko has with , and board in the final arrangement with . The niceness of Mirko's fence is equal to the sum of absolute differences between adjacent boards:
Since we know the orderings of each two adjacent boards, this sum can be rewritten without absolute values.
If we proceed to reduce this expression to canonical form, every will appear next to an integer coefficient from the interval .
If we put board next to the smallest of these coefficients, next to the second smallest and so on, we would surely end up with the fence as nice as possible.
Now we must arrange boards in this way, but also in a way that assures that Mirko's fence is similar to Slavko's.
We use this algorithm:
Coefficients and . Boards with these coefficients are larger (smaller) than both boards adjacent to them. There are no adjacent positions with (or ) coefficient, so we can go and place largest boards next to 's, and smallest boards next to 's. It's easy to see that we won't violate any constraint by doing this.
Coefficients and . Only the first and the last board can have or , so we put the largest board that's left from the first step next to and the smallest one next to .
Coefficient . These boards are smaller than one neighbour and larger than the other. By placing any of these boards next to boards already positioned in steps 1 and 2, we won't violate anything. So we only must be careful when placing them next to one another. Consecutive sequences of boards with coefficient will be either strictly increasing or strictly decreasing, depending on adjacent boards at the beginning and at the end of the sequence. We place them in any way that satisfies this condition and we are done.
Comments