Thoughts after SRM 507

I had a lot of pressure during this match, it was a long time ago since I had rating >= 2000. I really had to avoid losing it and go back to 1900+ (Which is a horrible place). Also, I knew that If I did well I would be able to surpass 2100. Unfortunately, that could not happen.

Div1 500 CubePacking
The second I opened this one, I knew I was not going to have a good match. It is that kind of problem that for me doesn't work too well. I spent a lot of time trying to do a solution that first picked dimensions of a prism in which to put all the LxLxL cubes and then to grow it to fit the 1x1x1. It seems that solution was completely wrong and clueless. Seeing at how things went, it seems this problem was way easier than that, but I just cannot think of something yet.

When I noticed that there were less than 30 minutes left, I decided to switch to 250.

Div1 250 CubeStickers
Link to problem statement
This one was painful. The first thing I did was to notice that you can sometimes use the same color in two faces. And in fact, that is the most times you can use the same color - Because if two faces are not on opposite sides of the cube, they will always be adjacent. Yet for some reason I couldn't think very fast of a way of actually verifying it.

That is right. In a cube, there are three pairs of faces that are opposites of each other. The only way to place two stickers of the same color is to place them in opposite faces. So, for each unique color in the list: If there are two or more instances of the color, "consume" two faces of the cube. If there is only one instance of the color, consume 1 face. If all 6 faces are 'consumed' everything is right and the result is "YES". If after using all colors, there are still faces that you cannot use , return "NO".

This is where the STL and thinking well of things works best. A good STL solution uses map<string, int> to first save the number of times each color appears. Then you can iterate through the elements of the map, and for each color that appears twice or more, use exactly 2 faces. And 1 face otherwise. Another way to see it is that you can use each unique color at most twice.

#include <vector>
#include <map>

using namespace std;

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct CubeStickers
{
    string isPossible(vector <string> sticker)
    {
        map<string, int> colorTimes;
        // Fill the map with the counts of each sticker color
        for(int i=0; i<sticker.size(); i++) {
            colorTimes[sticker[i]] ++;
        }
        int available = 0;
        for_each(q, colorTimes) {
            // We can use at most 2 stickers of each color.
            available += std::min(2, q->second);
        }
       
        return (available >= 6) ? "YES": "NO";
    }
};

I wanted to use for_each at some second during the match then I noticed that I had to type it all, so I gave up and did some incredibly dumb stuff with a vector for absolutely no reason. This is the moment I decided to add for_each to KawigiEdit's snippets

Div1 900 CubeBuilding
Link to problem statement
There were only 20 minutes left, but I knew two things: a) I was clueless about 500. and b) The hard one was worth 900 points, which is quite a suggestion that it is easier than 500. In a way this problem was easier than 500 , at least for me.

The first impression I had about the problem is that it was a dynamic programming problem in which you had to remove dimensions as much as possible. This impression turned out to be true. However, I made plenty of mistakes while thinking of the logic for the problem and when coding the memoization. Of course 20 minutes was too little time for me to debug and rethink things. I solved this problem only after the match.

The initial idea was as follows:
a) You can split the main problem into three variations: a) All the visible cubes must be red. b) Visible cubes must be green. and c) Visible cubes must be blue.

When we want to count the number of ways to make all visible cubes red. Then we have R cubes of the correct color and G+B cubes of the wrong color. When counting cases in which all visible cubes are blue, there are B correct cubes and G+R wrong cubes. Same happens with the other case. So, what I did is generalize. F( good , bad, N) returns the number of ways to place good+bad cubes in a NxN board such that only the good ones are visible.

That division was mostly correct, but I eventually noticed that there was a vital mistake. The bad cubes actually may have two different colors. However, solving F(good,bad1,bad2, N ) may be too heavy so we need the optimization. The fix is to, once you have F( good , bad1 + bad2, N), then you can get Combinations( bad1 + bad2, bad1) as the total number of ways to to pick the colors of the bad cubes. And just multiplying F( good , bad1 + bad2, N) with Combinations(, bad1 + bad2, bad1) will give the total number of ways to do it for each color.

On to solve F(good, bad, N), we can split the board in N rows. For each row, we will place some cubes (good and bad) in a way that only the good ones are visible. Then we can proceed to the following row but the number of good and bad cubes may have been reduced. So, what if you could have a function G(good, bad) that would return the total number of ways to put good correct-color and bad wrong-color cubes in a single row? Since this function has a limited number of argument combinations, we could calculate the results for funtion G() before calculating F() which will remove some complexity from F().

So, for each row, pick a pair u, v of good and bad color cubes to place in the row , then proceed to the next row with a possibly-reduced number of good and bad cubes. Then the number of ways to have good correct cubes and bad wrong cubes in a NxN board by using (u,v ) cubes in the first row is: F(good,bad, N) = G(u, v) * F(good - u, bad - v, N-1).

This allows a simple recursion that can also be memoized.

We just need to solve G. Note that after we add some good cubes in the front cell of the row, then the rows behind the good cubes can have any color. The idea in here is to have a variable front which will be the number of cubes on the front of the current cell. For the first cell, there are no cubes on the front of it. If there are front cells on the front, then we can place bad cubes as long as their height positions are less than or equal to front. We can also place good cubes in a height position less than or equal to front AND also add new ones which will increase the front value for the next cells. This was something I have overlooked during the match. Also , for the cubes that are covered by the stacks from the previous cells, we can pick any order, which is important when there are good and bad cubes bellow the front margin.

From the last paragraph: If the previous cells on front of the current one have a stack of size front and we decided to pick v bad cubes and u good cubes to place in the current cell. Then v cannot exceed front, else a bad cube would be visible. The number of ways to place the cubes in this cell is Combinations( min(front, u + v ), v ) , because you can only pick locations smaller than or equal to front for the bad cubes. Then the number of good and bad cubes decreases whilst front may increase to u + v if it is larger (a new size of the stack). All of this is helpful when making a second recursion which is also memoization-friendly.

The total complexity is around O(A⁵*N) where A is the sum of R+G+B. It barely gets 1.8 seconds in c++, so I am not sure if there is a better solution.

typedef long long int64;
const int MOD = 1000000007;
struct CubeBuilding
{
    int N;
    int64 mem[26][51][26];
    int64 mem2[26][51][107][26];
    
    int64 C[101][101];
                                
    int64 G(int a, int b, int front, int n) {
    // Returns the number of ways to place a+b cubes in
    // n cells if the largest stack in a cell on front of
    // them has size front. Such that only the a cubes
    // are visible.
    //

        int64 & res = mem2[a][b][front][n];
        if ( res == -1) {
            res = 0;
            if (n==0) {
                if ( a==0 && b==0) {
                    res = 1;
                }
            } else {
                for (int v = 0; v <= front && v <= b; v++)  {
                    for (int u = 0; u <= a ; u++)  {
                        int64 y = C[std::min(front,u+v)][v];
                        res += (y *G(a - u, b - v, std::max(front, v+u), n-1 ) ) % MOD;
                    }
                }
                res %= MOD;
            }
        }
        return res;
    }
    
    
    int64 F(int good, int bad, int p)  {
    // Returns the number of ways to place good+bad cubes in
    // all rows >= p of a NxN board such that only the good
    // cubes are visible
    //
        int64 & res = mem[good][bad][p];
        if ( res == -1) {
            res = 0;

            if(p == N) {
                if ( good == 0 && bad == 0) {
                    res = 1;
                } else {
                    res = 0;
                }
            } else {
                res = 0;
                // place cubes..
                for (int u = 0; u<=good; u++) {
                    for (int v = 0; v<=bad; v++) {
                        int64 tot = G(u,v ,0,N) * F(good - u, bad - v, p+1);
                        res = (res + tot ) % MOD;
                    }
                }
                res %= MOD;
            }
        }
        return res;

    }
    int getCount(int R, int G, int B, int N)
    {
        // Prepare combinations table using Pascal's triangle
         memset(C, 0, sizeof(C));
         for (int n = 0; n<=100; n++) {
             C[n][0] = 1;
             for (int k=1; k<=n; k++) {
                 C[n][k] = C[n-1][k-1] +  C[n-1][k];
                 while(C[n][k] >= MOD) {
                     C [n][k] -= MOD;
                 }
             }
         }

         memset(mem, -1, sizeof(mem));
         memset(mem2, -1, sizeof(mem2));

         this->N = N;
         int64 res = 0 ;
         
         //Red on front:
         res  += F(R, G+B, 0) * C[G+B][G];
         //Blue on front:
         res  += F(B, G+R, 0) * C[G+R][G];
         //Green on front:
         res  += F(G, R+B, 0) * C[R+B][R];
         
         return (int)(res % MOD); 
    }
};

Challenge phase
What saved me was a lucky challenge. I found a person that in his 250 solution had something like: if ( number of unique colors >= 4 ) return "YES". At first I thought it was all right, but then I noticed a case with 3 repetitions of the same color and other 3 different colors. There are 4 distinct colors in total, but it is still impossible to do it.

The end result was a increment of 11 rating points, which is fine. But I need to return back to getting steady increases in the next match , if I want to defeat my maximum rating.