Participating Google Code Jam(the First Time)
Yep, 2018 code jam is still going on, but I failed badly last weekend in Round 2, so it’s time for me to write :)
(By the way, if you missed the contest, you can still practice the finished rounds on the platform).
My background:
I hadn’t participated any competitive programming contest before and often thought about having a try.
I was not familiar with lots of algorithms and data structures, so started focusing on improving them two months before the contest.
The rankings I got in each round:
- Qualification Round: 1407/24584: got one hidden case wrong(more about visible/hidden tests, read here).
- Round 1A: 3098/5172: got two visible tests correct.
- Round 1B: 763/4811: got three visible tests & one hidden test correct -> enter Round 2.
- Round 2: 3034/3680: got no case correct 😂
So, if you are are a seasoned contestant, this article is not for you 😛
The Learning
End of Feb — middle of Mar
Reading Algorithms Unlocked, an easy-to-understand and short(excluding the last chapter about NP problems, it’s less than 200 pages) book.
Its author is the “C” in CLRS(Introduction to Algorithms), Thomas H. Cormen, why he wrote the book? He thought CLRS is not beginner friendly.
Solving algorithm problems on hackerrank(codeforces is also a good choice), mostly 2 problems per day.
End of Feb — middle of May
Bought the CLRS and started learning a lot of stuff from it.
Also learned a bunch from some helpful MIT open courses.
Watched every video lectures(multiple times for some of them) and some recitation videos from the course Introduction to Algorithms.
Also watched a few(due to the limited time) videos from some harder ones.
Design and Analysis of Algorithms, which introduced lots of algorithms that not mention by 6.006 such as max/min flow and linear programming.
Advanced Data Structures, which introduced lots of data structures that not cover by 6.006 such as the trie(prefix tree).
Things I learned during this period, including but not limited to:
- BST and its implementation.
- Heap and its implementation.
- Dynamic Programming(here is my blog about it).
- Minimum spanning tree and its implementation.
- Dijkstra’s algorithm and its implementation.
- How to solve linear programming problems.
Also, during this period, I found myself can jump the easy level questions on hackerrank(although stuck on medium level problems a long time very often).
The contest
Not going to mention problem solutions here, since the official analysis does a good job.
As the timetable below shows, there are 4 rounds(practice session doesn’t count) before the Onsite Final.
Advance in any of the 1A/1B/1C will give the contestant a chance to joining round 2.
The qualification round is there mostly for letting us get familiar with how the contest works, it’s 24 hrs long and the contestants do not have to be advanced in the ranking list to win the ticket for round 1(have to solve at least some test cases though).
Round 1A, I was very stressed.
Didn’t managed to solve the hidden case for the first problem — Waffle Choppers.
The second problem — Bit Party, its hidden case is still tough for me when I writing this, which means a lot of stuff needs learning :)
The last one — Edgy Baking, I misread the problem description, which leads me solves none.
With only 20 points from two visible cases, it’s far away from the 50 points for entering R2, so I decided to compete in 1B(it started at 2 AM, that’s why I needed a decision, LOL)
Round 1B, I was very calm(and tired), decided to solve problems firmly one by one(turns out that’s a good strategy).
The first problem — Rounding Error, I observed it could be solved with a greedy solution, this observation helped me solved the full problem(two visible cases & one hidden).
The second problem — Mysterious Road Signs, I managed to solve the visible case with dynamic programming, and the time went out.
I was laughing at myself that I failed again while I open the scoreboard, ranked at 763, wow.
Round 2, 0 AM, not feeling well that day.
I was jumping between(I shouldn’t) problem Falling Balls and problem Graceful Chainsaw Juggler, and didn’t manage to solve any of them.
Again, it means a lot of stuff needs learning :)
A great contest, will participate again next year for sure!
