Heuristic, Greedy, Mixure of Methods, Test Generation Plans
Give an array A’ of N integers, when a permutatation P is applied on A’ we get A.
f(A,i) = S - A[i] - A[i +1] - … - A[j], where j is the maximum possible index, such that A[i] + A[i + 1] + … + A[j] <= S, if A[i] > S, f(A, i) = S.
Find permutation P such that (f(A, 1) + f(A, 2) + … f(A, k))/k will be as low as possible.
This is a challenge problem. The most important thing in solving challenge problem is to find some approximation/partial methods using the combination of search, greedy, dynamic programming, etc…, because this challenge problem is NP-hard. Also, it is important to write a local test system to help you find the best strategy (almost all top ranked guys wrote their own test codes).
Since, there were only 20 files, you can by making assertions etc. find out the exact values of N and K and write specialised approached for different K. That’s what both top 2 did.
The most obvious two greedy approaches were to sort the array and other was to greedily assign integers to new array such that the f(A,i) is minimised for that i.
Also, another approach that was used by the 4th best solution by @manish05 was to use simulated annealing over greedy approach, which is a general local search approach and can be applied to almost all challenge problems.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon.