Next in the choice problem list in Practice and Learn is Code Jam 2008, Round 1A: Minimum Scalar Product, that we skip since the problem itself is a bit too easy and the whole round is a bit too hard for now. So let's go to Google Code Jam 2009, Qualification Round.
First off, in this qualification round you only need to "score at least 33 points to advance to round 1" as you can read above the scoreboard. This means that all you need is to solve small and large inputs of just one problem. Now start the timer and go practice. Hopefully it'll take less than the 24 hour allowed for the round!
As this is a qualification round the problems are relatively simple, but they are a good opportunity to learn a few useful think and code patterns.
As this is a qualification round the problems are relatively simple, but they are a good opportunity to learn a few useful think and code patterns.
Alien Language
Alien Language is a pretty straightforward pattern matching problem. The brute force is clearly out of questions as it scales with 26 ^ D and the limit for D is 5000. There are a number of clever data structures and algorithms that good programmers could employ to reduce the complexity, but one of the advantage of using a high level language in a coding competition is that you have tons of high level libraries and you can happily cheat in cases like this one. Let's harness the power of the python re module.
Read full article from Alien Language, Watersheds and Welcome to Code Jam - Qualification Round 2009 solutions | Code Jam Daemon
No comments:
Post a Comment