Hacker Cup 2014 Round 1

I was both disappointed and happy with my Round 1 results in the Facebook Hacker Cup (scoreboard and problems). I was disappointed that I got two of the four problems wrong, but happy I did well enough to advance to round 2 (and came close on the two I missed). The round lasted 24 hours, so I should have taken the time to study and test the problems more that I did.

Problem 1 was essentially about representing a number in a given base with a given digit alphabet. The only trick not covered in the test set was the case where the “base” was 1. Fortunately, I caught that before submission.

Problem 2 involved finding the optimal strategy for a coin game. Not much programming involved, but I was off in my analysis of what the optimal strategy was and missed this one.

Problem 3 required a search for the longest path through a grid with a couple constraints, including being limited to one “backward” string of moves. I used a dynamic programming solution with a 4D array to represent the longest path from a given position (2D), backward-usage (1D) and incoming direction (1D).

Problem 4 required the most analysis, which I mostly got right, but overlooked one detail. The problem boiled down to adjusting a set of up to 20 numbers so that the sum is minimal and every pair has the same greatest common divisor (GCD). My optimized search of the problem space seemed to be good enough, but the detail I missed was in handling of GCD when one of the numbers was 0.

The moral (at least for such lengthly rounds) is to augment the test cases before declaring victory and submitting. Doing so saved me for problem 1 and could have saved me for problem 2. However, the next round lasts only 3 hours, so there is more cost to doing more testing.

Round 2 Update: I completed one problem and thought I completed a second, but had a problem submitting the solution. I accidentally ran my code twice and then got an “invalid character” error after trying to clean up the outputs. However, I had no time for the others and wouldn’t have advanced anyway.