TopCoder Practice – SRM 308

I did a practice SRM on TopCoder this morning with my friend Oleg. It was SRM 308 Div 2. It went reasonably well, we both got 2 out of 3 accepted. Oleg submitted the 1000 point problem but made a simple mistake by calling the min function rather than max function in one place. I didn’t end up submitting the 1000. Oleg beat me by about 20 points as he finished the second problem faster than me.

The first problem was probably one of the easiest 250 point problems I’ve done on TC and I got it submitted faster than any problem I’ve done before (249.30 points). The problem was given a vector of integers, return the median or -1 if no median exists. I simply sorted the vector, if the size of the vector was odd, return v[v.size()/2], otherwise return -1.

The second problem was with decoding strings that were encoded using Huffman codes. In Huffman codes, characters in a string are replaced by bit strings. A Huffman code has the property that no bit string representation of a character is a prefix of another bit string. So, for example, the following are valid codes: A=”00″, B=”10″, C=”01″, and D=”111″, but A=”00″, B=”0010″, C=”01″, and D=”111″ is not because the encoding for A is a prefix to B.

Using the valid codes above we can encode the string ABACD as “00100001111”. In the problem, you’re given the codes plus the encoded string and you have to decode it.

This is pretty straightforward. You can loop through your encoded string, loop through your dictionary and try to match the dictionary word with the corresponding substring in your encoded string. If they match, then that’s the letter you want. Save that letter and move your current index in your encoded string ahead by the length of the dictionary word. Continue this until your current index is greater than the length of your encoded string.

The third problem, which I didn’t have time to complete, required a combination of dynamic programming (DP) with greedy. You have a bunch of treasure items, which have a cost value and weight value. You want to maximize the total cost of collecting items but not collect more than W amount of weight. This is a pretty classic DP problem. The catch is that in this problem, some treasure items can be divided into smaller pieces. For example, you could take 10% of an item or 30% or whatever.

I didn’t read the problem as carefully as I should have so I immediately coded the DP part. Then I tried to retrofit this to accommodate the case of using only partial amounts. That didn’t go all that well :-). I was getting some of the sample solutions, but not all. I eventually realized I needed to consider the full and partial items separately, but it was too late to finish that.

The solution is to use DP with all items that can’t be divided. You do this by making a cost array, where the indices represent the weights. You store in each index the maximum cost you can get for the given weight.

This is calculated as follows:

Assume we have an array of non-divisible item weights called w and costs called c.

for i = 0 to size(w) 
  for j = 0 to W
     cost[j + w[i]] = max(cost[j + w[i]], cost[j] + c[i]);

The second part is the greedy section. You sort all divisible items by their weight to cost ratio. Loop over your cost array and for each weight you’ve succeeded in making previously, loop over all divisible items. For each divisible item, calculate the cost of adding that item to your current weight provided the combined weight is less than W. After this inner loop, update your best cost if the cost you just made is better than any you’ve seen previously.

It should look something like this:

Assume we have an array of divisible items weights called wd and costs called cd, which have been sorted by their ratios.

bestCost = 0;
for i = 0 to size(cost)
  if cost[i] != 0
     currentCost = cost[i] 
     weight = i;
     for j = 0 to size(wd) 
         weightDiff = min(W - weight, wd[j])
         currentCost = cd[j] * weightDiff / wd[j]         weight += weightDiff;
         if(weight >= W) break

     bestCost = max(bestCost, currentCost)

Despite not getting the third problem, Oleg and I both would have been in the top 30 for this SRM.