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

Ball Stacking - ICPC Latin America 2011

This time I solved the problem Ball Stacking from ICPC Latin America 2011, the statement for this problem is available here.

This problem is solved with dynamic programming. The first thing that should be done to make things easier is changing the organization of the balls, so that each ball depends on the balls to its left and above it. So, this way one ball can only be taken if all the balls from the rectangle with it and the first ball as extremes have also been taken.

Following this, each cell is initialized with the sum of all the balls that must be taken for the current ball to also be taken. Later, the maximum sum is the maximum of the total sum of the current cell plus the value of the cell on its top and to its left, which has already been processed.

The last part is to update the value of the cell. It is the maximum of: {the column going from the top till the current ball, this column plus the value to its top and right, this column plus the value to its right, the value right on top of the current ball}. The column is taken because these balls are required to take the current ball and the balls to the left have still to be processed, they shall take care of taking the balls on top of them. Then the column must be taken together with both the value to the right and to the right and top because these balls to the right require that the ones to the left also be taken. There is still the possibility of taking no extra balls and using the value of the ball above.

I know the explanation was not very good, so any questions you may ask.


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

Garden Fence - ICPC Latin America 2011

The problem statement for Garden Fence is available here.

This currently is the problem with the second lowest number of total users who got it accepted and the one with least submissions of all among those from ICPC Latin America 2011 available at the Live Archive.

One important thing to notice before we start trying to place the fence is that we can make its line get as close to a tree (point) as we can without really crossing it, so there is no need to worry about cutting trees which get in the fence's way.

Now, the problem asks us to draw a line to separate the points into two disjoint sets in such a way to minimize a given sum. So, testing every line created by each pair of distinct points should give us the answer, there are N^2 such lines and for each of them we need to see to which side each point belongs, this takes O(N) with the naïve approach, what gives an overall complexity of O(N^3), which is too slow for this problem.

Still thinking about the naïve approach, what could be improved to reduce its complexity? Calculating the whole sum for each pair is making it become too slow, could that be changed so that the current sum could be used to calculate the sum for the next pair of points? Yes, that is possible and is exactly what I did to solve this problem. I just needed a good ordering for the points.

So the idea for my solution is:

For each point:

• Sort other points according to their angles with current point
• Calculate for the first point in the ordered set the sum of each side of the line comprised by it and the current point
• For each point in the ordered set:
• Rotate the line, in such a way that the current point of the ordered set changes sides
• Update the sums and check to see if there is a new minimum 

Special care must be taken with collinear points which line cross the current point, they must all be processed at once. Four different sums exist that need to be kept track of, the sums on each side of the line of each kind of point, the composition of them gives the final answer.

The complexity of sorting the points is O(NlgN) and the complexity of rotating the line is O(N) for each point, as this is done once for each point, that gives us O(N^2 + N^2lgN) = O(N^2lgN), and this is fast enough for this problem.

My code is available at codepad