PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Each candy can be thought of as having either a surplus of chocolate, or a deficit (which may also be thought of a negative surplus) of chocolate, defined as the amount of chocolate that would need to be removed (or added) in order for a particular candy to have the perfect ratio. If all candies have a positive surplus, or all candies have a negative, then no solution exists. Otherwise we wish to find some selection of candies whose total net surplus is zero. We first note that each candy’s surplus, when multiplied by desiredCaramel, will yield an integer. That is, if we denote si = Chocolatei * desiredCaramel - Carameli * desiredChocolate, then the surplus of candy i is si/desiredCaramel. Our task is to find integers pi such that sum(si * pi)=0, and not all pi are 0. Equivalently, consider a graph where nodes are labeled …-2, -1, 0, 1, 2… and there exists a directed edge from A to B if there is some candy i for which si=B-A. Our task is to find the shortest cycle in this graph.
The shortest cycle can be found using a breadth first search, but we need to keep the size of the graph small in order to make our search effective. If M is the maximum surplus, and m is the maximum deficit (that is, the negative value furthest from 0), then we need only consider nodes in the range [m * desiredCaramel, M * desiredCaramel]. To see this, suppose we have some collection of candies whose total net surplus is 0. We can add 1 candy at a time and form partial sums in such a way that the partial sum will always be in the range [m, M] as follows: whenever the partial sum is positive, choose a candy with negative surplus, otherwise choose a candy with positive surplus.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.