SRM 554 div1 hard: TheBrickTowerHardDivOne

Link to problem statement

We got infinitely many bricks of dimensions 1x1x1 and C different colors. Count the number of towers of size 2x2xX such that X is between 1 and H, inclusive such that there are at most K pairs of adjacent bricks (bricks whose faces touch) that share the same color. K is at most 7. In division 2 was H<=47 and division 1 has H<= 474747474747474747. In division 2, C is at most 4 whilst in division 1, C is at most 4747.

First solve the division 2 version

There are multiple explanations for the easy version already available. In the TCO blog I already explained my variation. I also posted my code for this problem. There are other explanations in this topcoder thread.

It is necessary to understand the div2 solution. The div1 solution is basically the same idea but very optimized. It is a dynamic programming solution. Let us make a recurrence f(c0,c1,c2,c3,k, h). c0,c1,c2 and c3 represent the colors of the bricks we placed before (In the initial case, let us say these colors are "imaginary", to represent an empty tower). It is also very convenient to imagine that c0,c1,c2,c3 are ordered in clock-wise order. k is the number of remaining opportunities for new pairs of adjacent bricks that share the same color and h is the maximum height of the towers we can place on top of the c0,c1,c2,c3 bricks.

If c0,c1,c2,c3 are not imaginary, then we can choose the "empty" tower to place on top of the bricks. Else, there are not really any bricks and the empty tower does not count.

We can then just pick some new colors (c0',c1',c2',c3') after choosing these colors, there may be new pairs of adjacent bricks with the same color (for example: c0 with c0'). The new bricks may also share colors with each other. This is where imagining the indexes 0,1,2 and 3 to be in clockwise order is very useful.

So, 0 is adjacent with 1, 1 with 2, 2 with 3, 3 with 0, x is adjacent with (x+1) % 4. Once you count the number of new pairs that are adjacent, subtract them from k and you find a new k'. The recursion step is clear now, move and call f(c0',c1',c2',c3', k', h-1). Of course, the base case is when h=0, then only the empty tower is possible. You have to add up all results for each tuple (c0',c1',c2',c3') we can generate. The initial case is f(-1,-1,-1,-1, K, H).

When H is very large

In the division 1 version, H is very large. C is also quite not small. So large that we probably want to have a O(log(H)) factor into the total complexity. To be honest, I think most coders of the lower-than-medium div1 level can tell right away that this is going to be a Linear recurrence with matrix exponentiation problem. I know I did.

The trick is that when you have a linear recurrence in your dynamic programming, you can sometimes get rid of a factor and turn it logarithmic. So when one of the input variables can be very large, maybe we are going to need logarithmic time.

But to be honest, I am lately starting to think that instead of seeing these problems as a linear recurrence thing it might be better to see them as a "count paths of a certain size in a graph" thing. This time I will start by explaining the trick to make it logarithmic.

H is the one input variable that is extremely large. So let us consider it separate from c0,c1,c2,c3 and k. Let us call each tuple (c0,c1,c2,c3,k) a state. There are many states in a instance of this problem. There is a special one (-1,-1,-1,-1, K) which is the starting state (we have not placed any tower yet). There are others... You can tell that the number of total states will be very large: 4747*4747*4747*4747*8, but we will for now imagine this is not the case (In a later section, we will try to think of ways to optimize this, many states can be classified as really the same state). So, let us assume that the number of states is going to be quite small...

Let us now turn the problem into a counting paths problem... The starting state will be state 0 (which represents (-1,-1,-1,-1,K) ). From it we will move to many other states like (0,0,1,2, K-1). There is an edge connecting the starting state and those states. Now here is the deal, each of these states may represent a valid tower (height 1). What we need is a [final] state so that the problem is about counting the number of ways to reach the final state starting at state 0. So we will make every valid tower have an edge connecting them to the final state.

If we count all the paths of size 2 between state 0 and the final one, we will have the number of towers of height 1.

Each of the states other than 0, also have many other states they can spawn from (0,0,1,2, K-1) we could move to (0,1,0,1, K-2), this is another edge. Now let us consider the path that goes through 0 -> (0,0,1,2, K-1) -> (0,1,0,1, K-2) -> final. This path has size 3, but it represents a tower of height 2. (In the bottom of the tower, place colors 0,0,1,2, then on top of them, place 0,1,0,1.).

Now, there might be cycles. For example (0,1,2,3, K) can be connected with (1,2,3,0, K) as no adjacent bricks will touch colors ( (1,2,3,0) on top of (0,1,2,3) ). Then (1,2,3,0, K) might be connected to (0,1,2,3, K) and so and so.

Consider the path 0 -> (0,1,2,3,K) -> (1,2,3,0,K) -> (0,1,2,3,K) -> (1,2,3,0,K) -> (0,1,2,3,K) -> (1,2,3,0,K) -> (0,1,2,3,K) -> (1,2,3,0,K) ... > final. This is a tower of very large height. But we can count it.

In order to count the towers of height h count the number of paths of length (X = h+1) connecting state 0 and the final state (let us assume the index of this final state is 1). Note that we need logarithmic time, height can be very large. This is a known problem. Let us assign indexes to each state, state 0 is inicial, state 1 is final, then all the remaining ones have some index... Let us make an Adjacency Matrix. Effectively the adjacency matrix already tells us the number of paths of length 1 between each pair of indexes. Raise the matrix to the X-th power... and voila! The resulting matrix will give you the number of paths of length X. It is like magic. Well, it is just an application of the linear recurrence with matrix exponentiation I mentioned up there.

With Repeated squaring, we can raise a matrix of t x t elements to H+1 power in O(t³ log(H)) time. We already assumed t (the number of states) will be quite small.

But we wanted AT MOST H

Yeah, that is a problem. We are currently the number of towers with exactly a given height, but the problem wants the towers of height at most H. I have recently dealt with this in the editorial for srm 550. Simply do this other magic trick:

The final state is where all paths of the wanted height end. But what if we added a loop to the final state. So that there was an edge connecting the final state with itself? Imagine a path 0 -> 2 -> 1 of size 2, there will be a new path 0 -> 2 -> 1 -> 1 of size 3. Now the size 3 paths will include all towers of size 2, AND all towers of size 1. The paths of size (H+1) will now include all towers of size (1<=X<H). Just add that loop to the final state and raise the adjacency matrix to H+1 power.

Optimize the states

We now know that, as long as we can reduce the number of states to something small enough so that O(t³ log(H)) is reasonable complexity, we can solve the problem

You only need to remember four colors.

The first obstacle is that C can be quite large. But is that really that much of a problem? Our states contain four colors. What is important to notice is that we do not really need to specify the actual colors we picked. We just need to specify the kind of pattern. Consider the following 3 color combinations:

Instead of representing each of those states by the specific colors (e.g: (0,0,0,0), (1,1,1,1), (2,2,2,2)...) represent them by the pattern. We can find that (0,0,0,0) is as good to represent each of those.

Let us define a format to represent a pattern. Let us index the colors not by their real values from 0 to C-1 but by the order at which they appear in c0,c1,c2,c3. For example a combination of four real colors is (4, 6, 4, 6), we can assign index 0 to color 4 (it is the first to appear) and index 1 to color 6. Then the state can be represented by (0,1,0,1). How about (102, 56, 1, 0), by using the same logic it becomes (0,1,2,3). As you can see colors (5,1,5,1) and (4,5,6,7) will also be turned into (0,1,0,1) and (0,1,2,3), respectively.

This will add complications when building the graph of states. (We need to build the graph of states. I bet the whole matrix stuff sounded easy, but we need to build it). From a pattern of colors (c0,c1,c2,c3) we need to generate each pattern of colors (c0',c1',c2',c3') that can be reached. The patterns must always follow the format we specified. We also need to find the new value of k after picking the new pattern. Note that this allows loops between the normal states in the graph. (0,1,2,3,K) is now connected with (0,1,2,3,K). Imagine placing a group of four different colors on top of other four different colors, K does not change, but the patterns are the same. There are also now multiple ways to reach the same state starting from another. For example from (-1,-1,-1,-1, K) there are C ways to reach (0,0,0,0, K-3) just pick any of the available colors and repeat it 4 times. Those changes still allow our matrix product to work, just make it so instead of an adjacency matrix we just have then umber of edges between each pair of states. This number is still the same as the number of paths of length 1.

We still got to solve the problem of generating (c0',c1',c2',c3', k') from (c0,c1,c2,c3, k). Let us say we want find the edges that can be reached from (-1,-1,-1,-1, K) (We should not represent the initial state as (0,0,0,0, K) four imaginary blocks (an empty tower) are not the same as four blocks of the same color.). Instead of iterating through each possible combination of 4 colors, we need to find the reachable patterns. And remember that the indexes are assigned by the order at which the colors appear.

I would recommend backtracking. To generate the patterns. It needs some modification. At each of the four color slots, you can either reuse a color we have already used (it has an index already) or introduce a new color. Let us say that m is the number of colors currently in use. When introducing a new color there will be C-m choices of colors to make. So we need to multiply the final number of choices by this (C-m) number. But the actual index of the new color will be m in the pattern. We picked one of (C-m) but we represent the choice by index m

When generated the states that can be reached from a state that is not the initial one. There is new a problem. The past four colors are still there and we still need to consider them. When picking the colors of the new set of 4 colors, we might have to reuse the past colors (and take it into account when finding the new value of k). So we start with some available colors. (In order to find the number of colors used in the previous state, just get the maximum of the indexes and add 1). We can still use the same backtracking, but now at the end we might have indexes greater than 3. For example, if the past state was (0,1,2,3) we could generate (4,5,6,7) as new state (use completely different colors) ). What we need is to, after generating this pattern through backtracking, fix it again. e.g: (4,5,6,7) becomes (0,1,2,3) after fixing it.

You only need to remember three colors

The first color to appear is color 0. Therefore c0 will always be 0. Great. We now only need c1,c2,c3 and k to represent a state because c0 is always 0.

Let us try to estimate the number of states. k can be from 0 to 7. c1,c2 and c3 from 0 to 3. We got 8*4*4*4=512. That is much smaller than what we had before, but still quite large for cubic complexity.

That estimation is not very good. For example, state (2,0,0, K) cannot appear, because 2 cannot be the second color index we place. So we would have to count the number of ways to have c1,c2,c3 such that:

c1 <= 1 c2 <= c1 + 1 c3 <= max(c1,c2) + 1

The value of K is also not completely independent from the colors you pick. (0,0,0,0, k=K-1) is not reachable, for example, because the maximum value of k is K, and in order to have four repeated colors the original k must have dropped by 3...

It is not trivial to do it, but I recommend just making the program that generates the states and their transitions/edges. And then printing the value t that was found for the maximum case. You will find that the real value of t is 102 (Including starting and final state). Significantly lower than 512. So small that it is possible to solve the problem with it (But it is not very easy, you will need VERY optimized matrix exponentiation).

Rotations

If you do not want to depend on low level optimization, we can compress the number of states even more. Let us consider the two following combinations of colors: (0,1,1) and (1,1,0) (We are now using the (c1,c2,c3) notation, c0 is always 0).

These two combinations added to the same value of k, are really the same thing. They represent the same state, just rotated. What we could do is, before fixing the color indexes values to follow the pattern rules, we can try each of the 4 rotations of the combination of colors. After fixing the rotation, pick the fixed combination of colors that is lexicographically smallest (this is an arbitrary rule to make sure we always pick the same kind of state for two different states that are equal after rotating them).

This will reduce the number of states from 102 to 49. It is a very relevant optimization. Which allows the solution to run in 280ms in TC servers...

More?

I am not sure if 49 is the optimal number of states (including starting state and final state). There may be more optimizations. Do you know of any? I tried things like the reverse, but it seems that the combination of the pattern rule and the rotation rule already ensure that two patterns that are the reverse of each other are counted only once.

Code

It is quite an implementation task. You need to find all the states that are reachable from (-1,-1,-1,K). In order to do that, I used a search that is basically a Breadth-first-search. But in order to generate, for a given state, each reachable state, I used Backtracking. At the time you generate the adjacency matrix, remember to multiply the factors and you will need matrix exponentiation by using squaring... And of course, use long longs to avoid overflows when multiplying possibly large numbers and it is all done modulo 1234567891 so there is an implicit requirement for Modular arithmetic. Quite a problem...

const int MAX_IDS = 49; //useful constant I found by just running the code 
                       // and printing the total number of states I found in 
                        // the maximum case. 
const int MOD = 1234567891; 
 
const int MATRIXMAX = MAX_IDS;  
typedef long long int64; 
#define long int64 
 
// What is not included is my matrix class. 
// It is just a class that allows me to instantiate matrixes 
// that can be then multiplied or raised to an exponent. 
// 
// matrix M(n, v) makes a n x n matrix filled with v as values. 
// M.assignPower(X, n) raises matrix X to the n-th power and assigns it to M. 
 
struct TheBrickTowerHardDivOne 
{ 
    int K, C; 
    struct normalState 
    { 
        int k; int c1, c2, c3; 
    }; 
    normalState description[MAX_IDS]; 
    int t; 
    int savedId[8][4][4][4]; 
    long transitions[MAX_IDS][MAX_IDS]; 
     
    void backtrack4(int id, int k, int *c, int *nc, int m, int p, int multiplier) 
    { 
        if (k < 0) { 
            return; 
        } else if (p == 4) { 
            // all chosen 
             
            // Count the number of adjacent pairs. 
            // The indexes are presented in a circular way: 
            // [0][1] 
            // [3][2].   This allows using (i+1)%4 for adjacency 
            // 
            for (int i=0; i<4; i++) { 
                if (nc[i] == nc[ (i+1) % 4]) { 
                    k--; 
                } 
            } 
            if (k >= 0) { 
                // It is a valid transition! 
                // But let's normalize the list of colors.... 
                vector<int> fnc(4, 5); 
                // Try each value of r, the starting index for the rotation 
                // for each r, "fix" the color indexes so that they follow the pattern 
                // rules. Then remember the lexicographically-smallest of the fixed 
                // results of all rotations. 
                //                 
                for (int r=0; r<4; r++) { 
                    // This rotation stuff reduces the number of states from 102 to 49 
                    // Which in turn reduces the worst execution time from 
                    // almost 2 seconds to 279 ms.... 
                    vector<int> rot(4); 
                    vector<int> colorId(8, -1); 
                    int s = 0; 
                    for (int i=0; i<4; i++) { 
                        int x = nc[(i + r) % 4]; 
                        if (colorId[x] == -1) { 
                             colorId[x] = s++; 
                        } 
                        rot[i] = colorId[x]; 
                    } 
                    fnc = std::min(fnc, rot); 
                } 
                 
                // Did we catch this state before? Reuse the id. 
                // If this is the first time, save important daya... 
                int & sid = savedId[k][fnc[1]][fnc[2]][fnc[3]]; 
 
                if ( sid == -1) { 
                    sid = t++; 
                    normalState & ns = description[sid]; 
                    ns.k = k; 
                    ns.c1 = fnc[1]; 
                    ns.c2 = fnc[2]; 
                    ns.c3 = fnc[3]; 
                } 
                // The multiplier contains the number of cases that 
                // end in this transition... 
                transitions[id][sid] += multiplier; 
            } 
        } else { 
            // Just pick a color for the current position. 
            for (int i=0; (i <= m) && (i < C); i++) { 
                // We can either re-use a color we've seen before 
                // or, if (i==m) use a new color (There are C - m more  
                //  colors available) (i < C) because we cannot use more than C colors. 
                nc[p] = i; 
                int nm = multiplier; 
                if ( i == m ) { //new color, C-m choices (multiply) 
                    nm = (int)( ( (C - m ) * (long)(nm) ) % MOD ); 
                } 
                // Keep backtracking... 
                backtrack4(id, k - (nc[p] == c[p]), c, nc, max(m,i+1), p+1, nm); 
            } 
        } 
    } 
     
    void bfs(int id) 
    { 
        // A BFS through the states (tuples (k, c1,c2,c3)). 
        int k; 
        int c[4]; 
        int m = 0; 
        if (id==0) { 
            k = K; 
            c[0] = c[1] = c[2] = c[3] = -1; 
            m = 0; 
        } else { 
            normalState & d = description[id]; 
            k = d.k; 
            c[0] = 0; 
            c[1] = d.c1; c[2] = d.c2; c[3] = d.c3; 
            m = max( max(c[0], c[1]), max(c[2], c[3])) + 1; 
        } 
        int nc[4]; 
        // backtracking works great. Let us pick the colors of the 4 
        // positions... 
        backtrack4(id, k, c, nc, m, 0, 1); 
        if (id != 0) { 
            // can finish... 
            transitions[id][1] = 1; 
        } 
    } 
 
    int find(int C, int K, long H) 
    { 
        this->K = K; 
        this->C = C; 
        t = 2; 
        // There are two special states: 
        // id 0 : start 
        // id 1 : end. 
        memset(savedId, -1, sizeof(savedId)); 
        memset(transitions, 0, sizeof(transitions)); 
        int i = 0; 
        while( i < t ) { 
            if (i != 1) { 
                bfs(i); 
            } 
            i++; 
        } 
        transitions[1][1] = 1; 
        cout << t << endl; 
         
        //Build that cute matrix. 
        matrix A(t, 0); 
        for (int i=0; i<t; i++) { 
            for (int j=0; j<t; j++) { 
                A[i][j] = transitions[i][j] % MOD; 
            } 
        } 
        matrix B; 
        B.assignPower(A, H+1); 
        return (int)( B[0][1] ); 
    } 
}; 
#undef long 

Comments / complaints / questions

If you got any doubt, or have corrections to make do not hesitate to post a comment.

Rant

Thanks to blogger being a mountain of fail, I could not submit this for almost an hour after I finished it. Because it kept giving me an error with no description at all of what is the issue. I slowly tracked the error as caused by my syntax highlighted code. It is generated automatically by jEdit as usual, but it seems that blogger just did not like to cooperate today. For now, I will embed the code using pastebin.com (Which does not add scrollbars, lame).

Update: fixed.