SRM 439 Div 2

I competed on TopCoder last week. I submitted solutions to all three problems, but due to some pretty silly mistakes, only my 500 solution passed the test cases. Pretty shameful :-(.

The problem set was actually quite do-able. The first problem was, given a rectangular grid of integers, find the largest square that contains the same digit in all four corners. My solution was to loop through each element (i,j) in the grid, then through all elements to the right of the given element. If any element to the right matched the given cell (i,j), then I would check to see if the cell located in the bottom left and bottom right hand corners of the square also have the same number. If so, store the size of the square if it is larger than my current best.

int getMax(vector  data) {
 int ans = 1;
 for(int i = 0; i < data.size(); i++) {
  for(int j = 0; j < data[i].size(); j++) {
     int v = data[i][j]-'0';
     for(int k = j+1; k < data[i].size(); k++) {
       if(data[i][k]-'0' == v) {
         // length of square
         int d = k - j;
         if(i + d < data.size() && data[i+d][j]-'0' == v
            && data[i+d][k]-'0' == v)
           ans = max(ans, (d+1)*(d+1));
       }
     }
   }
 }
 return ans;
}

Unfortunately, I made a really silly mistake with my indices during the contest by accidentally checking if data[i+d][k] matched v twice rather than data[i+d][j].

In the second problem, you have N bottles, each with unlimited capacity, initially all containing 1 liter of water. You can pour one bottle into another provided the amount of water currently in the two containers is equal. You need to reduce the number of bottles to at most K. If it’s not possible to do that with exactly N bottles, you can buy additional bottles. You have to return the minimum number of additional bottles that you must purchase.

This can be solved quite easily once you make a simple observation. First, given a number M, you want to determine how many bottles will be left over after you reduce the number of bottles as much as possible (that is, all possible pourings). Taking an example of M = 13, then initially you have:

1 1 1 1 1 1 1 1 1 1 1 1 1
After one round of pourings, you get:
2 2 2 2 2 2 1
Another round:
4 4 4 1
Last round:
8 4 1

So, you are left with 3 bottles after all possible pourings. This process of reducing bottles to the minimum number is very similar to the process of converting a decimal number into binary. To see this, let’s take the same example again but convert M=13 into binary.

13 = 6 * 2 + 1
6 = 3 * 2 + 0
3 = 1 * 2 + 1
1 = 0 * 2 + 1
13 in binary is 1011.

Notice how the multiplier equals the number of bottles that perfectly pour into each other each round and the remainder is the bottle left over. Also, interestingly, the number of 1s in the binary representation is equal to the number of bottles after all possible pourings! Thus, to solve the problem, we can start at N, keep adding bottles and count the number of 1s in the binary representation and see if that number is less than or equal to K.

int getMinBottles(int N, int K) {
int cur = N;
while(__builtin_popcount(cur) > K) cur++;
return cur - N;
}

In the last problem, you are given a string s, and you must determine the minimum number of insertions, deletions, and changes you would need to do in order to convert s into a palindrome. There was also one other twist, you were also allowed to perform one swap operation.

The problem is actually pretty easy to solve if you are familiar with the standard edit distance dynamic programming solution. With edit distance, you want to know the minimum number of insertions, deletions, and changes to convert string s1 into string s2.

Ignoring the swap operation, we can intepret this problem the same way by thinking of our string s in two halves. Since we want s to be a palindrome, that means the substring for the first half of s needs to eventually equal the substring of the second half of s. Thus, still ignoring the swap operation, we can easily compute the minimum number of operations to convert the first half into the second using the standard DP solution for edit distance.

Ok, so we’re almost there. Now, we need to figure out what to do with the swap operation. Well, the solution is actually pretty simple. Since we can only do the swap once, we can just try performing all possible swap operations. After each swap, check the edit distance calculation and store the minimum number of operations plus an additional one for the swap. The algorithm would be similar to the following:

int getEditDistance(string initial) {
 // compute distance from the two halves
 int ans = editDistance(initial);
 // try all swaps and recalculate distance
 for(int i = 0; i < initial.size); i++) { 
   for(int j = i+1; j < initial.size(); j++) {   
      swap(initial[i], initial[j]);   
      ans = min(ans, 1+editDistance(initial));   
      swap(initial[i], initial[j]); 
   }
 }
 return ans;
}