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
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
If we put board
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