PROBLEM LINK:Author: Sergey Nagin DIFFICULTY:Challenge PREREQUISITES:Greedy, Heuristics PROBLEM:Sereja have an array A = [A_{1}, A_{2}, ..., A_{N}], where N is an even integer. Let the function f(A) be defined by f(A) = (A_{1} + A_{2} + ... + A_{N/2}) − (A_{N/2+1} + A_{N/2+2} + ... + A_{N}). Sereja want to decrease the value f(A) by the unusual way. Let A[l..r] denote the subarray [A_{l}, A_{l+1}, ..., A_{r}] of A. Sereja can shift some subarray A[l..r], where 1 ≤ l ≤ r ≤ N, then the array A will become [A_{1}, A_{2}, ..., A_{l1}, A_{l+1}, A_{l+2}, ..., A_{r}, A_{l}, A_{r+1}, A_{r+2}, ..., A_{N}]. 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). EXPLANATION: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 A_{i} and A_{j} by repeatedly perfoming the operation [L,R] on the array. One approach could be: 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 :). AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 Aug '14, 16:29

http://www.codechef.com/viewsolution/4541336 I used a genetic algorithm which parses through only the left half of array. The array is broken in pieces of 8 elements each, and I try to find which elements to swap. I figured the maximum possibilities lie towards the middle of the array, as 2*N was pretty tight for swaps. For small n, brute forced my way through. During the contest, the solution was doing very well...it had a score of 1.000. But then after all test cases were added, I realized that other solutions had something more concrete. (0.924 Felt a little sad frankly. :P) But it was a really nice question...and I learned how to tweak parameters to optimize scores. Thanks. :) Btw, the code looks really bad, because I was trying to make improvements on the original clean one. Sorry for that. answered 14 Aug '14, 20:30

Please provide some tricky test cases for this problem with their optimum solution.