It is the time of year for programing contests. Google Code Jam has its qualifying round on May 6th and the TopCoder Open starts the qualifiers for their algorithm contest on May 14th. Assuming nothing unexpected comes up, I intend to participate in both of these contests again. If I am to have any hope of doing well in either of the contests I will have to prepare.
There are 3 main skills you need to have to able to do well in these type of contests.
Problem Solving
These contests are not software development contests. You don't need to be able to build an application better than other people, or even at all. What you need to do is be able to solve puzzles. Sometimes this is just a simple matter of following the instructions in the problem statement. More often it is a matter of realizing that if you look at the problem the right way, you can map it to another problem (e.g. graph traversal, binary search, etc.) that you already know how to solve. And occasionally you'll have to come up with a completely novel solution on the spot.
There are a few things you can do to get better at this. The first is to learn the known solutions to common computer science problems. It doesn't do you any good to recognize that a problem requires finding the shortest path between two nodes in a graph, if you don't know an algorithm that accomplishes that. The second is to practice recognizing places where these algorithms apply. Practice solving problems helps with this. Seeing how other people solved the same problem can also help.
The more knowledge you have of existing algorithms and the more experience you have at recognizing the use of these algorithms, the less often you'll come across a truly novel problem. And even when you do, you'll be better prepared to find a solution.
Programming
The problems posed in these contests don't require a lot of software engineering. It is rare for a solution to run as long as 100 lines, even in a relatively verbose language like Java. However, it is still a key skill. If you can't convert an algorithm into code accurately and quickly, you won't last long in a contest. When learning algorithms, don't just read about them in a book or online, code them up. And then code them again a different way. That experience will be helpful when coding under the gun.
Besides being able to code algorithms, you need to know your language. Do you know how to format strings, parse strings, and round numbers? Do you know the collection libraries provided and can you use them without having to look up API documentation? Do you know the performance characteristics of various features like autoboxing or string manipulation? How long will it take you to execute an n4 algorithm when n = 50? Does it matter what calculations you perform in the inner loop? Can you create an array of length one million? Ten million? One hundred million? How big of a value can you store in an integer? a long? What happens on overflow? Are you familiar with the precision issues that can crop up when using floating point numbers?
If you don't know the answers to the above questions, learn them. Not just from a book, but by writing programs. Knowing what is feasible and what isn't can help you find a workable algorithm for solving a problem.
Speed
These contests are timed. It doesn't do you any good if you can solve a problem, but it takes 6 hours. The only way that I know to improve speed is to practice, practice, practice. There are a couple of hints I can give you, though.
The first is that bugs are the enemy. Nothing kills your time more than having to debug a program. There are things you can do to reduce bugs. One is to be consistant. Be consistant with how you name variables and types, where and when you use curly braces and how you write algorithms. Another is to use as much structure as you need. Even though it is quicker to type one letter variable names and to create one long function, if meaningful variable names and separate functions and/or classes helps structure your code in a way that you can understand it, the time lost in typing will be more than made up in debugging.
Take your time.The last, but most important piece of advice in being quick is to take your time. Plan your solution. If it is complicated, sketch out your solution on paper and pencil before coding. Spend a couple minutes analyzing the performance characteristics of your solution. A couple minutes of thinking can save 20 wasted minutes of programming a flawed solution. Taking a couple extra minutes coding up a solution carefully and cleanly can save hours of debugging time. (and the contests don't last hours, so that is critical).
Out Coding
Well, I guess I should stop procrastinating and get to practicing so that I have a hope of advancing in these contests.
No comments:
Post a Comment