PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The time limits for this problem would seem very misguided in retrospect.
The expected complexity for the solution was O(N * S), where S was the largest sum that would be considered in the knapsack as described below.
First, needless to say, sort the numbers.
Now, iterate over each number, assuming it to be the Median, let this position be i. This forces us to select (K-1)/2 numbers towards the left of the median, and K/2 numbers towards the right of the median.
Perform a knapsack and pre-calculate the sums possible by selecting (K-1)/2 numbers in each segment from the beginning to any point within the array.
Perform a knapsack and pre-calculate the sums possible by selecting K/2 numbers in each segment from the end to any point within the array.
The optimization here, is on the fact that K/2 can be 30 at the most. So knapsack could be optimized to take only O(N * S) time, rather than O(N * K * S). This can be done by storing for each sum s the bit-mask of those values j for which s is representable as the sum of j numbers from the first i numbers of the array.
Now, we can treat the sums from the left and right of the median separately.
We can select each sum from the left, and a corresponding sum from the right; to find the sum, with which the mean is closest to the selected median. This determination step will be O(S) in complexity.
When a larger sum is selected on the left, we obviously select a smaller sum from the right. We can avoid doubles here by considering median * (K-1) and selecting the two sums, such that, their sum is closest to median * (K-1).
Most contestants were optimizing their O(N * K * S) solution. The test cases were such that such solutions were bound to fail the time limit. The time limits should not have been (but unfortunately were) tight for solutions with complexity O(N * S).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.