SEAPERM - Editorial

april14
challenge
editorial
seaperm

#1

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu

DIFFICULTY:

CHALLENGE

PREREQUISITES:

Heuristic, Greedy, Mixure of Methods, Test Generation Plans

PROBLEM:

Give an array A’ of N integers, when a permutatation P is applied on A’ we get A.
f(A,i) = S - A* - A[i +1] - … - A[j], where j is the maximum possible index, such that A* + A[i + 1] + … + A[j] <= S, if A* > 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.

EXPLANATION:

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.

Since, I was not able to understand the top rankers code, I would like to invite @kutengine and @aawisong as well as others to explain their approach.

AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon.


#5

Here:

http://discuss.codechef.com/questions/49471/what-should-be-the-approach-for-challenge-problems