Answers to: SEASHUF - Editorialhttps://discuss.codechef.com/questions/49501/seashuf-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SEASHUF">Practice</a> <br>
<a href="http://www.codechef.com/AUG14/problems/SEASHUF">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sereja">Sergey Nagin</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/dpraveen">Praveen Dhinwa</a> and <a href="http://www.codechef.com/users/laycurse">Hiroto Sekido</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a> </p>
<h1>DIFFICULTY:</h1>
<p>Challenge</p>
<h1>PREREQUISITES:</h1>
<p>Greedy, Heuristics</p>
<h1>PROBLEM:</h1>
<p></p><p>Sereja have an array <b>A = [A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>N</sub>]</b>, where <b>N</b> is an even integer. Let the function <b>f(A)</b> be defined by <b>f(A) = |(A<sub>1</sub> + A<sub>2</sub> + ... + A<sub>N/2</sub>) − (A<sub>N/2+1</sub> + A<sub>N/2+2</sub> + ... + A<sub>N</sub>)|</b>. Sereja want to decrease the value <b>f(A)</b> by the unusual way.</p>
<p>Let <b>A[l..r]</b> denote the sub-array <b>[A<sub>l</sub>, A<sub>l+1</sub>, ..., A<sub>r</sub>]</b> of <b>A</b>. Sereja can shift some sub-array <b>A[l..r]</b>, where <b>1 ≤ l ≤ r ≤ N</b>, then the array <b>A</b> will become <b>[A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>l-1</sub>, A<sub>l+1</sub>, A<sub>l+2</sub>, ..., A<sub>r</sub>, A<sub>l</sub>, A<sub>r+1</sub>, A<sub>r+2</sub>, ..., A<sub>N</sub>]</b>. For example we have the array <b>A = [1, 2, 3, 4, 5]</b> and we choose <b> l = 2, r = 4</b>, then after shifting we have the following array: <b>A = [1, 3, 4, 2, 5]</b>.</p>
<p>Sereja can shift multiple times, however it's burdensome to shift many elements. Thus the sum of <b>r − l + 1</b> should not exceed <b>2 × N</b>.</p>
<p>You have to minimise the final value of F(A).</p><p></p>
<h1>EXPLANATION:</h1>
<p>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. </p>
<p>Note that we can swap elements A<sub>i</sub> and A<sub>j</sub> by repeatedly perfoming the operation [L,R] on the array. <br>
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]. <br>
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. <br>
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. </p>
<p>One approach could be: <br>
Sort lowerHalf of array using a heuristics which gives elements nearer to center(N/2) and elements smaller in magnitude more priority. <br>
Sort UpperHalf of array using a heuristic which gives elements nearer to center and elements higher in magnitude more priority. </p>
<p>Now For each element in lowerHalf (starting from center to left end) find the element in righthalf which has more value and swap them. </p>
<p>This is a challenge problem and people always come with great ideas :). <br>
I welcome everybody to explain their approach on this thread.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/2014/August/Setter/SEASHUF.cpp">Author's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/2014/August/Tester/SEASHUF.cpp">Tester's solution</a> </p>enThu, 14 Aug 2014 20:30:35 +0530Answer by gkcshttps://discuss.codechef.com/questions/49501/seashuf-editorial/49636<p><a href="http://www.codechef.com/viewsolution/4541336">http://www.codechef.com/viewsolution/4541336</a></p>
<p>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. </p>
<p>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)</p>
<p>But it was a really nice question...and I learned how to tweak parameters to optimize scores. Thanks. :-)</p>
<p>Btw, the code looks really bad, because I was trying to make improvements on the original clean one. Sorry for that. </p>gkcsThu, 14 Aug 2014 20:30:35 +0530https://discuss.codechef.com/questions/49501/seashuf-editorial/49636