Google Code Jam Qualification Round 2010
May 7, 2010 in Uncategorized
Google Code Jam has begun and there is still time to compete, so register and start coding now if you have not!
For now, I would like to give some overview on the qualification round.
Problem A: Snapper Chain is solved by most people (3597 people so far), with the number of correct being 79% so far. Problem B: Fair Warning is the most difficult, being solved by only 847 people so far, correct rate being 76%. Problem C: Theme Park is solved by a total of 2370 people so far, with correct rate being 92%.
I would say Problem C is the easiest problem among the three, but only for the small input. The large input is quite tricky and you have to be careful of some traps. (Hint: Do your big(O) analysis before you attempt the large input!). I predict that Problem C: large input is gonna have the lowest correct rate among all.
Although Problem A is the most solved problem, it is a bit tricky as well, as you can see from the correct rate being only 79% (Compared to Problem C: small input – 92%). The problem description is also unnecessary complicated. This problem is easy after you discovered the pattern. Then generalizing it is straight forward from there.
Problem B is the hardest among all. So far I am still stucked on this problem. First of all, the question does take some time to digest. It seems like a Math problem to me, but so far I do not have any idea how to approach this problem. The large input for this problem contains integer up to 10^50, which is quite intimidating.
I would update this blog with tips and solutions to the problems once the qualification round has ended, so stay tune!
Qualification round has just ended! I hope everybody has a great time solving the problems!
If you scored at least 33 points, congratulations because you are qualified to the next round! The next round starts on May 22, and you’ve got 3 chances to qualify (called Round1A, 1B and 1C). Each round is limited to 2 and a half hours and your rank need to be within the top 1000 in order to qualify for Round 2.
Google is also nice to provide a detailed contest analysis, and solutions for each problems. According to them, this year’s questions are tougher than usual. Problem B: Fair Warning is indeed the toughest question. Besides, it is the first question in Code Jam that uses Big Integer, so be prepared for a good Big Integer library (some language provides it) in the future!
As predicted, Problem C: large input has the lowest correct rate of all (only 40% of the attempts passed the large input). This is why complexity analysis is very important in this situation.