I participated in a TopCoder practice session yesterday with Oleg and a new student in our research group, Nick. It turned out to be my best SRM in quite some time. I think I submitted all three problems before Oleg and Nick had submitted their second solution. I was a little worried that I had messed something up since I finished so quickly.
I started looking at my 500 and 1000 point solutions to see if I missed something in the problem. I was pretty sure my 500 solution was correct. The problem involved string matching. You were given a string along with a potentially short-hand version of that string. For example, the string “capture” can be shortened as “cptr”. You had to return the letters that could be removed from the first string such that the remaining letters matched the shortened version. In the previous example, the answer would be “aue”. If no match is possible, return “UNMATCHED”. I scored 481.63 points on this problem, which is probably my best score on a 500 point problem.
The solution is pretty straight-forward. The max length of the string is 50 characters, so you can use an N^2 string matching algorithm. I looped through the shortened version of the string, and had an inner loop that looked for matches on the larger string. On the first match, I break from the inner loop and add all the characters before the match to the string I will return. If I didn’t find a match then I know I can’t make this string.
// typed is the shorter string, phrase is the original
string probableMatch(string typed, string phrase) {
string s = "";
int last = 0;
for(int i = 0; i < typed.size(); i++) {
int j = last;
for(; j < phrase.size(); j++) if(typed[i] == phrase[j]) break;
// we found a match, so add the suffix to s
if(j != phrase.size()) {
s += phrase.substr(last, j - last);
last = j+1;
}
else return "UNMATCHED";
}
s += phrase.substr(last, phrase.size() - last);
return s;
}
The 1000 point problem was a really fun problem. You were given a description about how pigs choose a trough to eat from. The piglets attempt to choose a trough that will delay the time when they become sandwiched in by two piglets. After reading the problem, I realized based on the description that you could solve it using a greedy strategy. Each choice made by a piglet is a locally optimal decision, so you just need to process the choices in the correct order and return the first one that is available. Although I got quite a few points for the problem, I could have done it much faster by using C++’s built in string find rather than writing loops to do all the look ups. Both Nick and Oleg used dynamic programming for the problem, not realizing that greedy works.
It turned out that I was right about missing something in the problems, but it wasn’t on the 500 and 1000 point problems, it was with the 250. I actually failed the system tests on the 250 problem. It’s only the second time I’ve had that happen. I made a pretty silly mistake and didn’t make use of a formula given in the problem. Instead I tried to figure it out with my own formula.
Despite this error, I still would have been second overall in the SRM and I beat both Oleg and Nick during the practice. Tonight Nick and I are participating in the 3rd qualification round for the Top Coder Open. Hopefully we’ll qualify. Oleg has already qualified. The first official round is this Saturday.
