Editorial of MindCoding 2016 Final 1

The problem reduces to finding two values A and B such that:

• A % MOD1 = B % MOD1
• A % MOD2 = B % MOD2

Any such pair constitutes a collision for the hash function. An appropriate testcase can then be generated as follows:

2
1 A
3 B

Choosing A and B is not that difficult. A very simple solution is A = 0 and B = any common multiple of MOD1 and MOD2. Any positive constant can be added to these values without losing the collision property.

Consider the array of partial sums s_i = (a₁ + a₂ + … + a_i) % N, (1 ≤ i ≤ N). Clearly, this array contains exactly N values between 0 and N-1.

If there exists an index i such that s_i = 0, then we can construct our subset by choosing all elements a_j (1 ≤ j ≤ i). Otherwise, it follows from Dirichlet's principle that at least one value occurs multiple times. Denote by i and j two indices such that i < j, s_i = s_j. Then we can construct our subset by choosing all elements a_k (i < k ≤ j).

Note that this solution proves another property of the problem: besides the fact that any array of size N contains at least one subset whose sum is divisible by N, it also contains at least one such subset that is also a continuous subsequence of the array.