PROBLEM LINK:
Author: Vamsi Kavala
Tester: Hiroto Sekido
Editorialist: Anton Lunyov
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Greedy algorithm, Sorting algorithms
PROBLEM:
You are given an array W[1], W[2], …, W[N]. Choose K numbers among them such that the absolute difference between the sum of chosen numbers and the sum of remaining numbers is as large as possible.
QUICK EXPLANATION:
There are two possibilities to try - K largest numbers and K smallest numbers (see below why). So the solution could be like this:
- Sort all numbers.
- Find the sum of all numbers. Let it be S.
- Find the sum of first K numbers. Let it be S1.
- Find the sum of last K numbers. Let it be S2.
- Output max(abs(S1 − (S − S1)), abs(S2 − (S − S2))) as an answer.
EXPLANATION:
Consider the following sub-problem: choose K numbers with largest possible sum. Then the solution obviously is K largest numbers. So that here greedy algorithm works - at each step we choose the largest possible number until we get all K numbers.
In our problem we should divide the set of N numbers into two groups of K and N − K numbers respectively. Consider two cases:
-
The group with largest sum, among these two groups, is group of K numbers. Then we want to maximize the sum in it, since the sum in the second group will only decrease if the sum in the first group will increase. So we are now in sub-problem considered above and should choose K largest numbers.
-
The group with largest sum, among these two groups, is group of N − K numbers. Similarly to the previous case we then have to choose N − K largest numbers among all numbers.
This reasoning justify the solution in the QUICK EXPLANATION.
Regarding implementation details. Since N and T are small, then every simple O(N2) sorting algorithm from here will work. Other steps of the solution seems trivial to implement.
ALTERNATIVE SOLUTION:
Let’s go further and ask our self which of two above cases actually gives the answer. After short thinking it became clear that larger difference would be when more numbers are included to the group of largest numbers. Hence we could set M = max(K, N − K), find the sum of M largest numbers (let it be S1) and then the answer is S1 − (S − S1), where S is the sum of all numbers.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be provided soon.
Tester’s solution can be found here.
RELATED PROBLEMS:
Will be provided soon. All readers are welcomed to provide related problems in comments.