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

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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.