Problem link : contest practice
Difficulty : Simple
Pre-requisites : Pigeonhole principle
Problem : Find a nonempty subset of the given multiset with the sum of elements divisible by the size of the original multiset or state that the required subset doesn’t exist.
Explanation :
Claim:
There is always such a subset. Moreover, there is always a consecutive subsegment of any sequence of numbers that corresponds to the multiset’s elements with the sum divisible by the multiset’s size.
Proof:
Let’s denote a_{1} + a_{2} + … + a_{k} by b_{k}. So, we obtain:
- b_{0} = 0
- b_{1} = a_{1}
- b_{2} = a_{1} + a_{2}
- …
- b_{N} = a_{1} + a_{2} + … + a_{N}
It is easy to see that a_{L} + a_{L+1} + … + a_{R} (L <= R) equals to b_{R} - b_{L-1}. Therefore, if there are two values with equal residues modulo N among b_{0}, b_{1}, …, b_{N} then we take the first one for L-1 and the second one for R and the required subsegment is found.
There are N+1 values of b_{i} and N possible residues for N. So, according to the pigeonhole principle the required subsegment will always exist.
Some implementation details:
While calculating the value of b_{i} you should use that b_{i} equals to b_{i-1} + a_{i}, that allows you to precompute all bs in O(N) time. Practically, only b_{i} modulo N are important. Then you can just sort the numbers along with their indices in order to find the duplicates among the residues.