Dynamic Programming with profile - example 2

This is a problem from TopCoder SRM 444 DIV1 - 500 point.

Here is a link to the problem statement : http://community.topcoder.com/stat?c=problem_statement&pm=10487


Approach
Let
R = number of rows
C = number of Columns
Constraints tell us that 1 <= R <= 10, 1 <= C <= 25

We can go through each column, try all configurations for the current column, and choose the best outcome.
Runtime will be O(C * 2^R)  => Worst case : 25 * 2^10 = 25 * 1024 = 25600 . Small enough

You can also go through each row, try all configurations for the current row, and choose the best outcome.
Runtime will be O(R * 2^C) => Worst case : 10 * 2^25 = 10 * 33,554,432 = 335,544,320. Too big.

So let's go with iterating each column.


Algorithm

State
dp[idx][profile]
= maximum outcome for (idx)th column when its previous column has configuration of "profile"

recurrence
The validity of configuration of the current column depends on the configuration of the previous column.

Profile
A binary number representing configuration of the previous column.
(i)th bit of profile is set to 1 if (i)th row of the previous column is topleft corner of 2x2 '4' block.


Coding
I explained all the little details in comments in my source code.


Source Code

int INF = numeric_limits<int>::max();

int nINF = numeric_limits<int>::min();

typedef long long ll;

class FourBlocks {

public:

int maxScore(vector <string>);

};

int mem[25][1<<10];

int R;

int C;

vector<int> cols;

/*

 Count number of bits in "mask"

 */

int countTopLeftFour(int mask)

{

    int res = 0;

    while(mask > 0)

    {

        if(mask & 1) res++;

        mask = mask>>1;

    }

    return res;

}

/*

 rec(idx,mask) returns maximum outcome for (idx)th column

 when its previous column has configuration of "mask"

 (i)th bit of mask is set to 1 

 if ith row of the previous column is topleft corner of 2x2 '4' block.

 */

int rec(int idx, int mask)

{

    if(idx == C)

    {

        if(mask == 0) return 0;

        return nINF;

    }

    

    if(mask & cols[idx]) return nINF;

    

    int& res = mem[idx][mask];

    if(res != -1) return res;

    

    res = 0;

    /*

     Try every combination for current column.

     For each combination, check if it is valid by looking at "mask"

     and grid

     */

    for(int config = 0; config < (1<<(R-1)); config++)

    {

        /*

         "config" works the same way as "mask"

         We only check config to (1<<(R-1) - 1) instead of (1<<R - 1)

         because we cannot put the topleft corner of 2x2 '4' block

         at the last row.

         

         Let's call the current cell we are looking at

         cell[j][idx]  where idx stays the same for this column,

         and this information is strored at jth bith of config.

         

         We will check following conditions

         1. Is cell[j+1][idx] empty?

         

         2. Is cell[j][idx-1] or cell[j+1][idx-1] the beginning of

         4x4 block, thus making cell[j][idx] and cell[j+2][idx] unsuitable

         locations for the beginning of 4x4 block?

         

         3. Is either cell[j][idx] or cell[j+1][idx] supposed to be '1'?

         */

        

        if( (config & (config<<1)) || (mask & (config | (config<<1))) || (cols[idx] & (config | (config<<1))) )

            continue;

        

        //Pick the best outcome out of all valid configurations

        res = max(res, rec(idx+1, config | (config<<1)) + countTopLeftFour(config) * 16 + (R - countTopLeftFour(mask | config | (config<<1))));

    }

    

    return res;

    

}

int FourBlocks::maxScore(vector <string> grid) {

R = grid.size();

    C = grid[0].size();

    

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

    

    /*

     cols[i] 

     = jth bit of cols[i] is set to 1 

       if row j of column i contains '1' block in grid.

       0 otherwise.

     */

    for(int c = 0; c < C; c++)

    {

        int mask = 0;

        for(int r = 0; r < R; r++)

        {

            if(grid[r][c] == '1')

                mask = mask | (1<<r);

        }

        cols.push_back(mask);

    }

    

    return rec(0,0);

    

}