Saturday, March 05, 2005

Google India Code Jam

I made it into the first round of 500 qualifiers in the Google India Code Jam. That kept me busy for a while. The round to select the top 50 was held today. The results aren't officially out yet, but I'm at number 52 now, missing the top 50 by the narrowest of margins. What makes it really hurt is that I did pretty good today and could have been placed 15th but for a case I hadn't considered in one problem.

There were three programs to be submitted within the alloted time of 1 hour and 15 minutes. The points allotted to any solution depended on how quickly you submitted the solution.

The first problem for 250 points was very simple. There's a mechanical display that displays binary number numbers up to 32767 from a counter. The display gears that wear out for each binary digit flip. Given any two numbers, you had to calculate the wear in the display when counting between them. Pretty simple. Got a pretty good score on this one.

The second problem for 700 points had a 11x11 chessboard. You are given the position of rooks and bishops on the board in a format like "2 5 Rook", "4 8 Bishop". Up to 50 pieces can be given. You have to return the number of squares on the board that are controlled by the pieces. If a bishop or rook come in path of each other, the number of squares controlled comes down since the line of attack is blocked. Scored well on this one too. Doesn't require much thinking to code up a solution to this one.

In the last problem for 900 points you are given a sequence of integers. You need to determine the minimum number of changes required in the series to make the it an arithmetic progression. For example if you are given a sequence like
"100 -90 130 175 800 225 -10 275 30", the sequence you can make with minimum changes is "100 125 150 175 200 225 250 275 300" changing numbers at positions 2, 3, 5, 7 and 9. So the result is 5 changes. This was my waterloo. I coded up a solution that would work fine with series like this one. When I submitted the solution, I had totalled 1386 points with 30 minutes to spare (45 minutes for three programs).

At the end of the coding round, I was placed 15th, making it comfortably in the top 50. Next it was the challenge round for another 15 minutes. In this phase you can view the source code of the nine other contestants in your room and challenge them. If you provide a test case that fails, you gain 50 points, else you lose 25. I did find a valid challenge but couldn't get the 50 points since another guy challeged the same code successfully just before I did.

The system tests began next and went on for an hour. My solution for the third problem failed for a case like this "999 2 998 4 997 6 996 7 -999 9 10". This could be made into a series like "1 2 3 4 5 6 7 8 9 10 11" with 8 changes which is the minimum required. My solution however considered a transformation to "999 998.5 998 997.5 997 996.5 996 995.5 995 994.5 994" and returned 7 instead. If only I had ignored progressions with non integer increments I would be beaming right now. The thing with the code jam is that even if your solution fails one case, you lose all points for the submission. This mistake cost me 650 points and I slipped to the 52nd position. I missed the top 50 by 6 points. Could have made it with the 50 points from the challenge. The only hope now is if at least two contestants from the top 50 cannot confirm their participation in the final round in Bangalore.

Shit happens.

No comments: