I got through the qualification round with ease as it contained two problems which could be solved without knowing any advanced problem solving technique. But for the next round, it clearly appeared like knowing only to solve number theory, brute-forcing/backtracking and ad-hoc problems wouldn't help. So I Googled a bit to find what to learn.......and found several problem type classifications which were based on different programming competitions. Here's Hal Burch's classification based on ICPC which is somewhat applicable to Code Jam too:
- Dynamic Programming
- Greedy
- Complete Search
- Flood Fill
- Shortest Path
- Recursive Search Techniques
- Minimum Spanning Tree
- Knapsack
- Computational Geometry
- Network Flow
- Eulerian Path
- Two-Dimensional Convex Hull
- BigNums
- Heuristic Search
- Approximate Search
- Ad Hoc Problems
Of course, many of these types can be solved using simple brute-force algorithms, but they will end up taking a few million years to give you an answer for some of the inputs..... so definitely you need to learn some efficient and easy to implement techniques to tackle such problems. The best resource I found for this is TopCoder's algorithm tutorials, which contain no-nonsense and easy to understand tutorials on most of these areas.
Having said that, I should now come to the point.......that is, some of the smart tricks used by the competitors in this Code Jam competition. One is that, since the solutions are executed in competitor's mahine itself, it gives competitors the ability to generate all solutions to a problem using brute-force which might take a couple of hours (before downloading the input, coz once you download inputs you'll have only 8 minutes to solve them), save it, then download the actual input and then just lookup the already generated results to directly find answers to the input. No DP, no efficient algorithms, but still perfectly legal and effective! (if your computer has enough processing power). I actually found a few guys who had advanced to round 2 using this technique.
Second one is writing multi-threaded programs. It feels like a crazy idea trying to implement a multi-threaded algorithm.....but think about it.....you might have a Core 2 Duo processor, if you write a normal inefficient algorithm, it will execute on only one core.....and your program might take 8 minutes plus a couple more seconds to execute and you'll be out of the competiton. What a waste.....you might have implemented the same program to have multiple threads and execute over both cores and could have solved it within 8 minutes! (this is a rare case, but actually happened in Round 1A - Problem A) Now some of the competitors are interested in writing toolkits to provide concurrent execution over all cores they have on all computers at home, be it a desktop computer, a laptop or a netbook. What a fantastic idea!....they've turned this competition into a concurrent programming competition too. By the way, I have only one single-core machine at home, so I'm trying to find an online supercomputer service which can offer some computing time for me to execute my horrible brute-force programs to advance to the next round :) Just another different idea ;)
Anyway, the competition is getting fierce....so there's a very little chance (most probably no chance at all) to advance through round 2 (which takes only top 500 contestants). But if you too give it a try, you'll certainly discover some fantastic techniques to tackle problems.
