SRM 616 hard problem: ThreeLLogo

This editorial is http://apps.topcoder.com/wiki/display/tc/SRM+616. Since Topcoder insist on restricting the wiki for non-registered users, I will post the explanation here.

Link to problem statement

The first part of the explanation explains what the problem asks us to count. Just notice that the constraints say there will be at most 30 columns and at most 30 rows:

---

A change in format

This explanation will interpret the question slightly different from the statement. The purpose is that I find it easier to make explanation graphics under the following interpretation: We have a grid, some cells (white) which allow us to put shapes on them and some cells (black) that don't the "L" shapes occupy multiple cells, at least three.

Fill the grid

There are different approaches to this problem. The one intended by the problem setter is to see it as a dynamic programming problem. Instead of focusing on there being a need for just 3 L shapes and trying ad hoc counting, perhaps it is more straightforward to see this problem as a grid/bitmask dynamic programming one. Much like FourBlocks or FloorBoards

The idea is to fill the grid in row-major order. In each cell, we can leave it empty, or choose to start a L shape or perhaps continue an already started L shape. So given a row `x` and a column `y`, assume that all the previous cells (in row-major order) have already been filled.

In this example, the current cell we are deciding is green and the remaining undecided cells are red. Because there is an unfinished vertical arm of an L shape above this cell, we have two options:

• Use cell `(x,y)` to continue the vertical arm of the L shape. We move to the next cell:
  
  
• Use cell `(x,y)` to finish it. Then we also move to the next cell:
  
  

Assume we did the latter, now we need to decide what to do with the new cell `(x,y)`, this time the cell has a horizontally-adjacent L shape which must be finished. We have two options:

• Continue this horizontal shape, we will need to add more of this shape in later steps:

  
  
  
  

  If we make this decision, the next step will have a blocked cell as `(x,y)`, we cannot put any shape on this cell, but due to the decision we are forced to place something, so the number of ways to fill the remaining cells correctly is 0.

• Finish this horizontal shape:

  
  
  

  Let's pick this decision

After doing this, the new `(x,y)` position is a blocked cell, our only choice is to do nothing and leave this cell empty. Move to process the next cell, you will find a situation similar to the first example, we can choose to continue the above L shape or finish it, this time we'll pick to continue it.

This is another interesting situation, `(x,y)` is an empty cell, there is no vertical or horizontal L-shape that we must continue. We can leave this cell empty:

Or, because there are currently only two L shapes, we can start a whole new one:

Dynamic programming

Once we understand how is it possible to fill the grid in row-major order, we can see that, in order to count the number of valid ways, there are few things to consider:

• `(x,y)` : The current position in the row-major order. There are `O(nm)` such pairs. We assume that all earlier cells have already been chosen.
• `k` : The number of L shapes we still haven't created.
• `V` : A set of the columns currently containing vertical arms of (currently) incomplete L-shapes. This is a subset of the `m` columns, but it can contain at most 3 elements, thus there are `O(m^3)` such sets. More specifically, you shouldn create L shapes at the right-most column, so `V` is only a subset of the first `m-1` columns and with some calculation you can find that there are 4090 such sets in total for `m = 30`.
• The state of the cell to the left of `(x,y)`, does it contain an unfinished horizontal L arm? We can use the variable `"horz"` for this, if `"horz"` is 1, we must continue the horizontal shape else it is 0.

In other words, the number of ways to fill the cells painted red in the following two examples ( `(x,y)` and the later cells in row-major order ) should be exactly the same:

This allows an `O(nm^4)` approach through memoization of a recursive implementation of the idea to count the ways to fill the grid. But that is not the whole story. We need to be careful: In practice, there are 4 values for `k`, 2 values for `"horz"`, 4090 values for the `V` set and 31*31 values for the `(x,y)` (we need the base case `x = n` and the special case `y = m` to keep the code simple). Also, the result needs to be a 64 bits integer. Thus the memory usage is 4*2*4090*31*31 * 8 bytes ~= 239 MB, quite close to the 256 MB limit and thus we should avoid overhead. Also notice that slight modifications to the logic we used could have made us require more states. There is a 3 seconds limit but we should also avoid having too much of a constant factor. A key aspect of the implementation is how to deal with the `V` set. As is usual, we can use bitmasks, but of course we cannot downright use 30 bit bitmasks to store results in memory, a workaround is to index the bit masks.

Code

    
vector<string> grid;
int n, m;

long mem[31][31][4][MAX_MASKS][2];
map<int,int> getMaskId;
int validMasks[MAX_MASKS];

long f(int x, int y, int need, int maskid, int horz) {
    long & res = mem[x][y][need][maskid][horz];
    if (res != -1) {
        return res;
    }
    int mask = validMasks[maskid];
    if (x == n) {
        // base case
        res = ( ( (mask == 0) && (need == 0) ) ? 1: 0 );
    } else if (y == m) {
        res = ( (horz == 1) ? 0 : f(x + 1,0, need, maskid, 0) );
    } else if ( (1<<y) & mask ) {
        if ( (horz == 1) || (grid[x][y] == '#') ) {
            // if (horz == 1) must continue the left "L" shape,
            //  but also must continue the above one
            res = 0;
        } else {
            //1) Finish the L shape above.
            int nmask = mask ^ (1 << y);
            res  = f(x,y+1, need, getMaskId[nmask], 1);
            //2) Continue the L shape vertically
            res += f(x,y+1, need, maskid, 0);
        }
    } else if (horz == 1) {
        if (grid[x][y] == '#') {
            res = 0;
        } else {
            res = f(x,y+1, need, maskid, 1) + f(x,y+1, need, maskid, 0);
        }
    } else {
        //1) Do nothing
        res = f(x,y+1, need, maskid, 0);
        //2) Create a new L shape
        if ((grid[x][y] == '.') && (need > 0) && (y + 1 < m) ) {
            //2.1) Create a new L shape
            int nmask = mask | (1 << y);
            res += f(x,y+1, need - 1, getMaskId[nmask], 0);
        }
    }
    return res;
}
 

long countWays(vector<string> grid)
{
    this->grid = grid;
    n = grid.size(), m = grid[0].size();
    
    // generate all bitmasks with <= 3 turned on bits:
    int t = 0;
    auto addMask = [&](int mask) {  // don't mind the lambda syntax, it
        getMaskId[mask] = t;       // simplifies having to repeat this code
        validMasks[t++] = mask;    // for each number of 1 bits.
    };
    addMask(0);
    for (int i = 0; i + 1 < m; i++) {
        addMask( 1 << i );
        for (int j = i + 1; j + 1 < m; j++) {
            addMask( (1 << i) | (1 << j) );
            for (int k = j + 1; k + 1 < m; k++) {
                addMask( (1 << i) | (1 << j) | (1 << k) );
            }
        }
    }
    cout << t << " masks found for " << m << endl; 
    
    // run the recursive solution:
    memset(mem, -1, sizeof(mem));
    return f(0,0, 3, 0, 0);
}