SRM 552: An end to FoxPaintingBalls

After the failure of yesterday, I decided to take a look back to this problem.

Given N make "ball triangles" using balls of only 3 colors in a way that no balls of the same color touch. There are R, G and B red, green and blue balls (These variables are each at most 10¹⁸. What is the maximum number of valid triangles we can make?

A triangle of N=3:

  o
 o o
o o o

A valid way to pick the colors for the triangle:

  G
 R B 
B G R

In the last post I explained that if you pick a certain color to be color #1 (The color of the bottom left ball in the triangle, then the counts of colors #1, and #2 and #3 are always the same for a given value of N and we also know how to calculate them.

We know that in case N % 3 = 1, then x, the number of balls you need for color #1 is equal to y+1, where y is the number of balls you need for colors #2 and #3. When N % 3 != 1, then x = y .

Then the problem is to find the correct number of times you have to pick red, green or blue as color #1.

The solution I tried to code during the match was also explained in that post. Basically you try to do the simulation until the number of remaining balls of more than one color are the same, etc, etc etc. This code was VERY complicated, and full of corner cases, no wonder I made a mistake in implementing it, but I also found many other mistakes in my code. Including a complete bug: When two colors are equal, and you can't drop them in a way that three become equal, you have to subtract one color individually.

But there are better ways.

Formalize

I feel lame now. This is something I tend to include in many of the editorials I write. It can help A LOT to first define a problem formally. this is what I did not try to do yesterday, and this is what turns out to be the key to a simple solution.

Let us forget about the case when N%3 != 1, that one is simple because we can pick any color as color #1 without changing anything. Let us also treat N=1 separately as just returning R+G+B. What is left is the case where x = y+1. Let us focus on y.

Let X1 be the number of triangles in which we pick red as color #1. X2 the number of triangles in which we pick yellow as color #1, and X3 the number of triangles with blue as color #1.

We want to maximize z = X1 + X2 + X3, the total number of triangles we make.

When we pick red as color #1, we use y+1 available balls of color red, and y balls of the other colors. Extend this logic to blue and green:

Max z = X1 + X2 + X3

X1 * (y + 1) + X2 * y       + X3 * y       <= R
X1 * y       + X2 * (y + 1) + X3 * y       <= G
X1 * y       + X2 * y       + X3 * (y + 1) <= B

This is where the +1 difference comes into play, just develop the algebra a little:

(X1 + X2 * X3) * y + X1 <= R
(X1 + X2 * X3) * y + X2 <= G
(X1 + X2 * X3) * y + X3 <= B
->
             z * y + X1 <= R
             z * y + X2 <= G
             z * y + X3 <= B

These last three inequations are the key to solve the problem. Every time you increase z by one, then we use y balls of each color. After we make z triangles, then the values of X1, X2 and X3:

X1 < R - z*y
X2 < G - z*y
X3 < B - z*y

e.g.: R - z*y is the maximum number of times you could have used red as color #1. But notice that X1 + X2 + X3 = z, thus :

R - z*y + G - z*y + B - z*y >= z

If that condition does not fulfill, then the value we chose for z is impossible. We have therefore designed a way to find out if a given value of z is possible or not. We can also tell that if z = t is not possible, then z = t+1 is not possible either. And if z = t is possible, then z = t -1 is possible. We can just do a Binary search on the value of z.

typedef long long int64; 
#define long int64 
 
struct FoxPaintingBalls 
{ 
    //adds the number of balls of color 1 in row N to x  
    //and the number of balls of colors 2 or 3 to y.  
    void row(int N, long & x, long & y)  
    {  
        long z = (N - 1) / 3 + 1;  
        if (N % 3 == 1) {  
            x += z;              
            y += z - 1;  
        } else if (N % 3 == 2) {  
            x += z - 1;  
            y += z;  
        } else if (N % 3 == 0) {  
            x += z;  
            y += z;  
        }  
    }  
    long theMax(long R, long G, long B, int N)  
    {  
        long x = 0, y = 0;  
        // For multiples of 3, the balls are evenly distributed  
        // fix N to the closest multiple of 3 (downwards)  
        long t = N - N%3;  
        // total number of balls (Gauss)  
        t = (t * (t + 1)) / 2;  
        // divide evenly  
        x += t / 3;  
        y += t / 3;  
        //... the remaining 1 or 2 rows:  
        if (N % 3 == 1)  {   
            row(N, x, y);  
        } else if (N % 3 == 2) {  
            row(N-1, x, y);  
            row(N, x, y);  
        }  
         
        if (N % 3 != 1) { 
            // x = y 
            // it does not matter how we choose the colors: 
            long res = R / x; 
            res = std::min(res, G / x); 
            res = std::min(res, B / x); 
            return res; 
        } else if (N == 1) { 
            // Each ball makes one triangle. 
            return R + G + B; 
        } else { 
            // Binary search for z. 
            long lo = 0, hi = 1LL<<62; 
            // possible(lo) && !possible(hi) 
            while (lo + 1 < hi) { 
                long ha = hi - (hi - lo) / 2; 
                // this first condition verifies that the boundaries 
                // are not negative (z*y <= R) 
                // 
                bool good = ( (ha <= R/y) && (ha <= G/y) && (ha <= B/y) ); 
                // Now the condition from the analysis: 
                good &=  (R + G + B - 3*ha*y >= ha ); 
 
                if (good) {  //possible 
                    lo = ha; 
                } else {    // not possible 
                    hi = ha; 
                } 
            } 
            return lo; 
        } 
         
         
    } 
}; 
#undef long 

There is more

Of course, further analysis will show you that there is no need for the binary search, we can find the max value of z through simple division. Just turn each of the conditions we used into a bound:

long z = R / y; 
z = std::min(z, G / y); 
z = std::min(z, B / y); 
z = std::min(z, (R + G + B) / (3 * y + 1) ); 
return z; 

In fact, note that until the last line, that is the solution for the case when N % 3 != 1 as well. So we can basically replace everything with this log.

// after finding x and y: 
if (N == 1) { 
    return R + G + B; 
} 
long z = R / y; 
z = std::min(z, G / y); 
z = std::min(z, B / y); 
if (N % 3 == 1) { 
    z = std::min(z, (R + G + B) / (3 * y + 1) ); 
} 
return z; 
 

The logic to find x and y can also be simplified a lot...