Too many HACKS for Problem-D(1618-D) of Codeforces Round #760 (Div. 3)

#	User	Rating
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3442
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
2	atcoder_official	162
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

I was going through the hacks list of Codeforces Round #760 (Div. 3) during the end of the 12 hours Hacking phase. Interestingly, I noticed that a lot of hacks for Problem-D were successful. After going through many of the submissions which were hacked, I noticed a flaw in the logic with which they approached this problem. I will try to describe the mistake and try to give a proper logic for this problem.

Let me first describe the fault in those hacked submissions:-

*Sort the array/vector

*Run a loop for k times and divide elements from the beginning of the array by the elements from the end of the array. Similarly move on to second element from beginning and divide by second last element from the end. Do this for k elements and store their sum in a variable say s1.

*Again run another loop for k times. Now, in this loop we start by taking elements from the (n-2*k+1)th term and divide it by the last element of the array(which has already been sorted). Similarly divide (n-2*k+2)th term by 2nd last term from the end and so on. Essentially we take one pointer at n-2*k+1 and the other at n and then move towards each other. Store their sums in a variable say s2.

*Now take the minimum of s1 and s2 and add it to the sum of undivided elements(if any) and print the answer.

The error in this logic can be understood by a simple test case:

6 3

5 5 4 4 2 1

here both s1 and s2 will be equal to 1. s1=s2= (1/5)+(2/5)+(4/4) = 0+0+1 = 1

However, the most minimum possible answer here can be 0. Let's take a look at the correct logic:

*Sort the array/vector.

*Divide the (n-k)th element by last element of the array. Then divide the (n-k-1)th element by the (n-1)th element and so on. Repeat this division process for k times and store the sum in a variable say s. Now add the remaining undivided elements (if any) to s and output the answer.

using this logic for the above mentioned test case, we get: s=(4/5)+(2/5)+(1/4) = 0+0+0 = 0.

Here, the main point to be understood is that if we choose the smallest possible element and divide it by the largest possible element in each turn, we may encounter situations in which we have to divide two equal elements which by the correct logic can be avoided. Our aim is to choose as many optimal pairs for division (of a smaller element by strictly bigger value) as possible.