Candy's Candy - ICPC Latin America 2011

The problem I've just solved is Candy's Candy from ICPC Latin America 2011, the problem statement is available at ICPC Live Archive.

This problem is solved with just a little of mathematical insight. Once you start thinking about it the solution comes easily.

First of all, we will define C as the number of candies each package has and P as the number of packages, also S is the sum of all the candies. So it is not hard to see that P*C=S, so the number of candies C in each package must be a divisor of T.

It can also be noted that C must be a multiple of F (the number of flavors) because each variety package must have at least one candy of each type and at least one variety package must exist in each valid configuration. So we write C = K*F

Now, for a given C, each flavor can be written as: v[i] = C*n_i + R_i, R_i < C, this means R_i is the remainder of the division of v[i] (the number of candies of the i-th flavor) by C. This remainder makes for the initial amount of candies available and so if any R_i is different from the others no valid configuration can be done with C. If all R_i's are equal we must then test if R is a multiple of K. This necessity comes from the fact that the amount of candies which don't belong to a one-flavor package must be a multiple of C, so F*R is the amount remaining candies. We reach then: F*R % C = F*R % K*F = R % K = 0.

Ok, so now all restrictions have been verified and we just need to calculate the number of valid configurations. To do so we take m = min{v[i]} and add the floor of (m - R - 1) / C to our answer.

My code is available at: http://codepad.org/MErwgxGa