Sereja have an array A = [A1, A2, …, AN], where N is an even integer. Let the function f(A) be defined by f(A) = |(A1 + A2 + … + AN/2) − (AN/2+1 + AN/2+2 + … + AN)|. Sereja want to decrease the value f(A) by the unusual way.
Let A[l…r] denote the sub-array [Al, Al+1, …, Ar] of A. Sereja can shift some sub-array A[l…r], where 1 ≤ l ≤ r ≤ N, then the array A will become [A1, A2, …, Al-1, Al+1, Al+2, …, Ar, Al, Ar+1, Ar+2, …, AN]. For example we have the array A = [1, 2, 3, 4, 5] and we choose l = 2, r = 4, then after shifting we have the following array: A = [1, 3, 4, 2, 5].
Sereja can shift multiple times, however it’s burdensome to shift many elements. Thus the sum of r − l + 1 should not exceed 2 × N.
You have to minimise the final value of F(A).
There are two halves in the array say lowerhalf(1 to N/2) and upperhalf(N/2+1 to N). Suppose upperhalf has more weight(sum of elements) than lowerhalf. We’ll try to swap elements between upperhalf and lowerhalf such that difference of their weight is as small as possible.
Note that we can swap elements Ai and Aj by repeatedly perfoming the operation [L,R] on the array.
For example, in array 1,2,3,4,5,6 we need to swap element 2 and element 5: applying operations [2,5], [2,4], [2,4].
So, swapping two elements has a cost equal to sum of (R-L+1) of each operation we apply. We can have total of all swaps not more than 2*N.
So swapping costs us some points out of 2*N, but it also decreases F(A). So, we can greedily make swaps or we can make heuristics based on the cost and the profit we get.
One approach could be:
Sort lowerHalf of array using a heuristics which gives elements nearer to center(N/2) and elements smaller in magnitude more priority.
Sort UpperHalf of array using a heuristic which gives elements nearer to center and elements higher in magnitude more priority.
Now For each element in lowerHalf (starting from center to left end) find the element in righthalf which has more value and swap them.
This is a challenge problem and people always come with great ideas :).
I welcome everybody to explain their approach on this thread.