SEASHUF - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

DIFFICULTY:

Challenge

PREREQUISITES:

Greedy, Heuristics

PROBLEM:

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).

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 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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

3 Likes
2

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. :slight_smile:

Btw, the code looks really bad, because I was trying to make improvements on the original clean one. Sorry for that.

1 Like
3

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