TC SRM442 D2 1000 (EqualTowers)

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

In summary, we are given a set of blocks and are asked to construct two equal height towers from using a subset of the given blocks. This problem is similar to the subset sum problem, since that problem is NP-complete we can guess at the time complexity of this problem. The subset sum problem is the following: given a sequence of integers (both negative and non-negative) find a non-empty subset which sum totals exactly to 0. How does this problem relate to the one given? We can treat the negative numbers as one side of the tower and the positive numbers as the other side. As the absolute values are the same (since the sum totals 0) this fits our problem. However, there is a major difference: we must find the largest height.

However from this we are given a slight hint on how to approach the problem. The subset sum problem is solved using dynamic programming and hence it is likely we can approach this problem in the same way.

Deciding the state space is slightly more tricky, when looking for sub-problems we can take note that we can gradually consider a growing set of items (in a very similar manner to the 0-1 knapsack problem). However, this is not enough we also need to know the heights of both towers to make an optimal decision (and ultimately to decide whether or not the block configuration is a valid one - i.e. the heights are equal). A naive approach would be to take the heights of both buildings and put them in the state, yielding:

F(i, size1, size2) = the highest building size we can construct using a set of blocks from up to index i which the buildings have a size of size1 and size2 respectively.

Looking at the constraints, this is state space is simply too large to fit into the memory constraints. So we must optimise or compress our state space. If we look closely we can eliminate having two different building sizes by using the difference between the taller and shorter building. We can store the "base" of the building in the actual DP state value. For example, if the buildings we had so far were of height 5 and 8. We can store 5 as the DP state value and 3 as a building parameter which depicts the height of the taller one to be 5 + 3 = 8. We don't actually need to worry about which building is which, as our final goal is only to determine whether or not the buildings are equal. This allows us to also determine valid configurations to have an allowable difference of 0.

Trying to construct another DP state now:

F(i, size) = the height of the shorter building we can construct using a set of blocks from up to index i in which the difference between the shorter and taller building is size.

We calculate whether or not this will fit in the memory constraints (which is 64MB). The maximum number of blocks is 50 and the maximum size of a building is 250000 (as if it's over 250000 we can never match a second building to that height because the maximum sum of all the blocks is 500000). This yields a space complexity of O(n * s) which fits perfectly.

Constructing the recurrence is rather simple, we have 3 decisions for every state.
1. Do not add block i into either towers
2. Add block i to the shorter tower
3. Add block i to the taller tower

If we add block i to the shorter tower, we must be careful to note whether there will be a swap between the current shorter tower and the current taller tower. However, as mentioned above we don't actually care which tower is shorter or taller so we only need to calculate the new height of the shorter tower and the new difference. The new difference is simply the absolute difference between the current difference and the block to be added: abs(size - block[i]). The height of the new shorter tower is simply the minimum of (size, block[i]) added to F(i,size). The first and third condition are relatively simple - you just need to write an extra guard to prune any additions to the taller tower which exceeds 250000.

We now define the recurrence as:
F(i,size) = max(F(i+1,size), F(i+1,abs(size-block[i])) + min(size,block[i]), F(i+1,size+block[i]))

This can then be solved using either memoization or bottom-up dynamic programming. Further optimisations can be made by noting that the recurrence only takes into account the previous index. So we only need at most O(2 * s) space. We then alternate and over-write the previous rows using simple modulus calculations. We can also discard any block size which is greater than 250000. We can also calculate the sum of all the blocks and only iterate the size from 0 to sum/2 which will generate faster execution for smaller cases. My practice room solution is as follows:

int dp[2][250011];

int EqualTowers::height(vector <int> bricksPre) {
 vector<int> bricks;
 for (int i = 0; i < bricksPre.size(); i++) 
  if (bricksPre[i] <= 250000) bricks.push_back(bricksPre[i]);
 dp[bricks.size()&1][0] = 0;
 for (int i = 1; i <= 250001; i++) dp[bricks.size()&1][i] = -1;
 for (int i = bricks.size()-1; i >= 0; i--) {
  for (int j = 0; j <= 250001; j++) {
   dp[i&1][j] = dp[!(i&1)][j];
   if (j + bricks[i] <= 250001) dp[i&1][j] >?= dp[!(i&1)][j + bricks[i]];
   if (dp[!(i&1)][abs(j-bricks[i])] >= 0) dp[i&1][j] >?= dp[!(i&1)][abs(j-bricks[i])] + min(j, bricks[i]);
  }
 }
 return dp[0][0] ? dp[0][0] : -1;
}