SRM 552: Greed kills

What a match. I think the problem setters exagerated with the div1 250's difficulty. I would have kept the constraints of R,G and B small so dp was possible.

Div1 250

As far as I recall, there was only one problem in this match. 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. What is the maximum number of valid triangles we can make?

A triangle of N=3:

  o
 o o
o o o

A valid triangle:

  G
 R B 
B G R

Forced moves

This was the nice part of the problem, to figure out that once you pick a ball for the top-left corner, the remaining moves are basically forced.

Let us name the color of that first ball 1, then 2 and 3 are the remaining colors. After drawing balls a lot and failing to do it in paper, I started representing a triangle by a table-like structure:

    2
   13
  321
 2132 ...
13213

Once you pick the color for the top-left corner, the rest is basically forced, the relative positions of color 2 and 3 can change, but otherwise. The counts will be a forced thing.

Then we just need to find the formula, given N, how many balls of color 1 will there be, and how many balls of colors 2 and 3 (Note that those counts are the same).

I needed to draw and draw until the pattern is evident. Let us first consider only the rows. x denotes the number of balls of color 1 and y the balls of colors 2 and 3.

N	x	y
1	1	0
2	0	1
3	1	1
4	2	1
5	1	2
6	2	2

...

This pattern goes on. Now note that every 3 rows, the totals become equal. Eventually you can find an easy way to calculate the total x and y for all the rows. Only based on N%3.

Further analysis will reveal that the numbers of balls of each color are evenly distributed most of the time. The only exception is when N%3 = 1, in which case x will always be equal to y+1.

    //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); 
        } 
 
        // 
 

What now?

This was the hard and evil part. (Even though the first part was already quite cool and interesting, this is why I think the problem would have been better if we were able to solve this with dp).

We now have to decide how many times use red, green and blue as color 1. The constraints are large so we will need some sort of greedy. This is one of the first way in which greed killed me. This greedy was very tricky to think of.

When x=y (which happens when N%3 != 1), this decision does not really matter. When N=1, then the result is R+G+B. Those are the simple cases.

The first tempting idea is to just sort the number of available balls. And always use the most available color as color 1. This fails examples. When R=G=B=100, you will notice it is better to alternate the colors.

Always alternating the colors is tempting but does not always work.

If the constraints were lower, the following simulation would work: While there are enough balls to make one triangle, pick the color with the most balls available, use it as color 1, subtract x from it and y from the other colors. Always repeat. This greedy algorithm will work, but it is not possible to implement it in its current form.

I hesitated a lot before trying to implement that logic in a way that would work in time (Find the number of times to drop maximum color until it becomes equal to another one. The problem is that then when there are three or two equal color you have to drop them in unison.) At the end I was running out of time, and decided to do it, after writing long and awful code that was most likely wrong, I tested the code and with 20 seconds left it passed examples. Sure, why not? I submitted it. Then I noticed a couple of obvious bugs in the code. Just now I learned that even after fixing those bug, there was still another big bug and then even after that big bug, there is still an error somewhere.

That is right, I am still not sure how to solve this. Well, I do know of a formula that seems to pass system tests, but right now I can't prove it.

Challenge phase

I knew I had 0 points, but I also knew that it was simply not possible for many people to solve this problem correctly. I already knew the examples were weak. I sort of imagined that people would try variations of alternating the colors, even when it is not the best idea.

I thought of a case, R = 10¹⁸, G = 5*10¹⁷, B = 25*10¹⁶, N=4. N=4 ensures that the choices matter.

After two successful challenges of two attempts, I felt greedy, and tried again. Third attempt was not that good. Fourth was not either. I actually dropped back to 0 points!. But I did not give up and challenged another one. Luckily this one failed. Then I got greedy again and stuck with 25 points. I really regret not stopping once I had 100 points. It would have been a decent score.