COCI '11 Contest 4 #4 Ograda
In this problem, we are given 2 sets of N planks. We need to order the second set of planks such that they are "similar" to the first set the the sum of the differences between adjacent planks is maximized. The planks are similar if, for example, in the first set, plank i is smaller than plank i+1, then in the second set, plank i is also smaller than plank i+1. Likewise, if plank i is greater than plank i+1 or are equal, the same must happen in the second set.
Let's take an example. Let's say the first set of planks is as follows:
4 2 6 9 8
The sum of differences would be
a[1] - a[2] + a[3] - a[2] + a[4] - a[3] + a[4] - a[5]
or
a[1] - 2 * a[2] + 0 * a[3] + 2 * a[4] - a[5]
The only possible coefficients for each element are
-2, -1, 0, 1, 2
An element with a coefficient of +2 is going to increase our answer the most, so we should allocate the largest numbers to the positions with this coefficient. Likewise, elements with a coefficient of -2 is going to decrease our answer the most, so we should allocate the smallest number to these positions. We can follow a similar logic for the +1 and -1 elements.
Whatever numbers planks are left must be allocated the positions with a coefficient of 0, however we need to pay closer attention to where we allocate each number
Notice that a number can only have a coefficient of 0 if it is in the middle of an increasing or decreasing sequence. If the number is in the middle of an increasing sequences then we need to ensure that the number we allocate is greater than the previous number but smaller than the next, and likewise in the case where the number is in the middle of a decreasing sequence.
Comments