TC SRM444 D1 500 (FourBlocks)

The problem statement can be accessed via: http://www.topcoder.com/stat?c=problem_statement&pm=10487&rd=13898

To summarise the problem, it asks us to find the maximum number of 4 blocks we can place within a grid layout. It is always optimal to use as much 4 blocks as we can as their value per unit area is better than 1 blocks.

This problem lends itself to a dynamic programming algorithm due to the fact that there are significant amounts of overlapping subproblems. To see this, we isolate one column and see that the possible configurations of inserting in new 4 blocks are only dependent on this column and the previous one (as the maximum block sizes we are allowed are 2x2). Looking at the constraints we see that we can bitmask based on the grid height (i.e. number of elements) as this only has a maximum of 10 entries and hence 2^10 = 1024 combinations.

Let's start by defining the DP state:
F(idx, mask) = the maximum number of points using idx columns and with the previous column having a bitmask of "mask"

Naturally, we next consider base cases and the recurrence relation. If the current index of the recurrence is equal to the number of columns (i.e. the size of each grid element) then we need to check whether or not the last column made any new 4 blocks. Why? This is because if the algorithm inserted a 4 block in the last column it's going to "overflow" into the last non-existent column on the board. Implementation wise there are several ways to do this, one is to not let new 4 blocks be made in the last column - another way is to let it overflow and make a condition which checks for this to prevent it from such an occurrence being used as an optimal figure (i.e. by setting the final result of this configuration to a negative value).

We define x as a possible 4 block configuration candidate.
F(idx, mask) = foreach x max { F(idx+1, x) + numBlocksInserted(x) * 16 + (numRows - numBlocksNotUsed(mask | x)) }

Next thing is implementing the actual algorithm which is fairly straightforward given the recurrence relations. We just need to make sure that we don't insert blocks to which:

1. Already has an associated 4 block inserted in the last column (use the bits in the mask parameter to determine this)
2. Conflicts with any 1 blocks initially present with the board configuration (this is calculated and kept before the dynamic programming begins)
3. Does not create a 4 block in two consecutive rows (i.e. row x and row x+1 for a column y)

An easy and quick way to implement these are to use bit operations. Here is my practice room implementation which uses the ideas discussed above:

#define INF 9999999

int memo[26][1<<11];
vector<int> cols;
int sz;

int numBits(int n) {
 int k = 0;
 while (n > 0) { if (n & 1) k++; n >>= 1; }
 return k;
}

int func(int idx, int mask) {
 if (idx == cols.size()) {
  if (mask == 0) return 0;
  return -INF;
 }
 if (mask & cols[idx]) return -INF;
 if (memo[idx][mask] != -1) return memo[idx][mask];
 int res = 0;
 for (int i = 0; i < (1 << (sz-1)); i++) {
  if ((i & (i << 1)) || (mask & (i | (i << 1))) || (cols[idx] & 
       (i | (i << 1)))) continue;
  res >?= (numBits(i) * 16) + (sz - numBits(mask | i | (i << 1))) 
       + (func(idx+1, i | (i << 1))); 
 }
 return memo[idx][mask] = res;
}

int FourBlocks::maxScore(vector <string> grid) {
 int res = 0;
 memset(memo,-1,sizeof(memo));
 cols = vector<int>(grid[0].size(),0);
 for (int i = 0; i < grid.size(); i++) {
  for (int j = 0; j < grid[0].size(); j++) {
   if (grid[i][j] == '1') cols[j] += (1 << i);
  }
 }
 sz = grid.size();
 return res = func(0, 0);
}