PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Essentially, we’re asked to find a subset S of the given N numbers containing exactly M numbers such that their sum is the smallest possible sum divisible by K. An easy O(NMK) dynamic programming solution, where the state is (how many numbers have been processed, how many numbers have been chosen, what is the current sum of chosen numbers modulo K) obviously exceeds the time limit.
Of course, we need some observations to proceed further. The first useful observation can be the following. Suppose the given numbers are separated into K bunches based on their value modulo K. Then, if we are going to include X numbers from a particular bunch into S, it’s easy to see that we should include the smallest X of them.
The second useful observation is trivial. Let’s include the smallest M numbers of the given N into S, and say their sum is Q. If Q is divisible by K, the answer is found! This doesn’t seem to help much from the first sight, but actually it helps. Obviously, when Q is not divisible by K, we should remove several – say, R – numbers from S and include R other numbers into S. Intuition may tell that in the optimal solution the value of R is not very large since K is very small, and that’s correct. Let’s denote the largest possible value of R by W and show that W ≤ K(K-1). Suppose R > K(K-1). By pigeonhole principle, there will be at least one bunch (as described above) containing at least K removed numbers, and at least one bunch containing at least K added numbers. But if we hadn’t removed those K removed numbers and hadn’t added those K added numbers, the sum of numbers is S would have been smaller while still divisible by K, so a solution with R > K(K-1) can’t be optimal.
Now a DP solution is possible, but instead of processing numbers one by one, we will process whole bunches. Let’s assign each bunch a number called delta in [-W;+W] interval, with -C meaning that we remove C largest added numbers of this bunch from S, and +C meaning that we add C smallest unadded numbers of this bunch to S. Let’s also define a function H(bunch,delta) meaning by how much the total sum changes when we “apply” delta to this bunch (this value is negative when delta is negative). As we should add exactly as many numbers as remove, the sum of all deltas should be equal to 0. Another condition is that the initial sum of numbers in S plus all the values of H(bunch,delta) should be the smallest possible such sum divisible by K. Note that H(bunch,delta) may be undefined if there are not enough numbers in the bunch.
The only remaining question is an optimal assignment of deltas to the bunches, and we’ll use DP. The state of our DP will be (how many bunches have been processed, what is the current sum of all deltas, what is the current sum of chosen numbers modulo K), and the value of DP in this state is the smallest possible current sum of chosen numbers under these conditions. So, from state (i, j, p) we can move to (i+1, j+C, (p+H(i,C)) mod K) adding H(i,C) for every C between -W and +W. The initial state is (0, 0, the initial sum mod K), and the final state is (K, 0, 0). The complexity of this solution is O(N+K2W2), which is O(N+K6) when W = K(K-1).
In fact, it can be proved that W ≤ 2K-2. It comes from the proof that you can always choose K integers from any 2K-1 integers so that their sum is divisible by K (so, in context of our problem it means that we can find K such numbers among the removed ones, K such numbers among the added ones, and replace the added numbers with the removed numbers decreasing the sum and leaving the modulo value untouched). I’m not posting this proof here, but it does exist 
This was probably impossible to prove during the contest if you hadn’t known the fact before, but it was possible to believe your intuition and convince yourself that the value of K(K-1) is still too large for W – in fact, even 2K-2 is too large. The final complexity of the solution becomes O(N+K4).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.