-
Currently Reading
How To Do Well in Programming Competitions
Posted on November 8, 2007
Filed Under Computer Science, Misc |
Contests don’t measure real-world programming skills
You’re not judged on the best refactoring of your solution, and you’re not judged on indentation and neatness. If your result is very maintainable, there’s a good chance you put too much effort in the wrong place. You just need to get the solution correct, and fast! Whenever you make a decision about how you will modify your style, keep in mind the following formula for short-term programming:
Total coding time = Total writing time + Total debugging time
You do yourself absolutely no good if you write one-letter variable names for 20 different variables, and you can’t understand the code 20 minutes later when you try finding a bug. You also don’t do yourself any good by writing a convert_from_imperial_to_metric() function and calling it 15 times, as well as fully commenting the preconditions and postconditions of the function. Use common sense!
I personally found the following helpful, as far as affecting the speed of finding solutions:
Standardize names: What’s your input variable going to be? If you’re programming in Java, what will you name your source files? If you’re programming in C++, can you write a macro your team will use that will cut down on typing for “for” loops? Do you want to? The less you have to think about names, the more you can think about logic. When you find yourself implementing a type of function over and over again, decide once and for all what you will call it, to make debugging easier.
Refactor Judiciously: It can help to pay attention to refactoring. Calling print_board(); is clearer than iterating through a two-dimensional array, even if only slightly. Some teams even find it helpful to go all-out with refactoring, and they make function calls for every detail.
Another added bonus is that it’s easier to debug the output of a function than it is to debug part of a function.
Comments: In the course of the competition, you’ll run the gamut of distractions. You’ll start helping a debugging effort, or you’ll find unfortunately placed pizza. You then look back at your code, and … dammit, what was I doing? Help yourself out by commenting complex sections of code before you start writing them. It’ll help you get a clearer notion of what you need to do, and when you come back and see that it’s only 3/4 of the way done, you’ll be able to jump back into the problem quicker.
Surely, some of these ideas are debatabe. I’m sure superhuman coders have no need for comments, or even variable names that are more than 1 letters long. Hell, they could probably write an entire LISP compiler without ever hitting the <Enter> key, and allowing themselves 15 presses of the <Backspace> key. However, the regular human beings among us need a little help. Experiment, and do what you feel most comfortable with.
Knowing more than 1 programming language is helpful
If your team consists of more than 1 person, it is preferable to have at least 2 different languages mastered between your team. In a recent ACM Collegiate competition, coaches for other teams called our choice of coding in multiple languages “unique”. And we all know what that means. Our team made sure that we were comfortable with both Java and C++, and we had 1 primary C++ coder and 2 primary Java coders. We got 4th, and finished all problems, and looking at our competition, that’s about as good as we could have done. Know the advantages of the problems:
Java has an exceptionally diverse standard library. It has built-in regular expressions, it has built-in arbitrary precision integers, and it has a very complete Math library. Also, debugging time matters, and receiving line numbers and error types with your runtime errors is a tremendous help.
C++ is, in some regards, far more elegant than Java for small problems. Parsing, input, and output is very easy, and can be typed very quickly. String manipulation is also much easier and MUCH less verbose. Macros are definable that cut down on common tasks. For the C++ ninjas among us, the STL has very nice tricks squirreled away in random libraries.
Materials to bring with you (should you be allowed to use them):
ACM Programming Challenges book: If the contest is open-book, this is the single best resource you can use. The book was written specifically for ACM Regional Collegiate contests, and it does not disappoint. It is actually considered the “official” book of these contests, and the judges will expect that you’ll have it as a reference. It has formulas and explanations for everything from 2D geometry to number theory to backtracking. Not only is this book a great reference, it also has a good number of practice problems, ranging from easy to seemingly mind-bending. They’re very carefully chosen so that they have an obvious, slow solution, and a non-obvious, fast solution.
Encyclopedia of Integer Sequences: This is the second best resource that you can possibly bring. Why spend 10 minutes figuring out a recurrence when you can look up the sequence along with the function that generates it? Don’t get me wrong, knowing the way recurrences are generated are a very important part of Computer Science, and not all of the sequences you encounter in the contest show up in the book. However, there’s nothing wrong with looking up the solution to a problem in 1 minute that would have taken you 15 minutes to derive from the problem description. That’s just efficiency, baby!
Pencils: Lots of pencils. If you’re not filling paper with algorithms before you write the harder programs, you’re either doing something wrong, or you’re smarter than I am, and are scoffing at the idea that I would even think of using a pencil to track information at a level of abstraction any higher than machine code level.
Practice the problems!
You’d be shocked about how many people just go to the contest without ever trying to write a practice program. Sure, spending a day with your friends is fun and all, but spending a day with your friends and doing well in the contest is better. I’ve done both, and the second is ABSOLUTELY more satisfying. If you can’t answer whether or not the contest usually gives you stdin or file input, you’re going to spend too much time thinking about how to parse the input, and not enough time thinking about how to solve the problem.
Avoid being “that guy”, and look at the problems beforehand.
Practice the hard problems
Nobody cares if you can break n cents into quarters, dimes, nickels, and pennies. However, if you can figure out how to make a fast solution for the triangular n-queens problem [pdf alert] for board sizes of 1000, then you can probably do a good number of the medium-difficulty problems. The best part is, if you only practice the hardest problems, eventually they start to look like they’re not so bad. Instead of being intimidated by them, you pull out your pencil and immediately start probing the problem’s depth. And sometimes, you find a quick and easy workaround.
Practice a variety of problems
It doesn’t just cut it if you are awesome at number theory problems, and you can’t even begin to find a solution for any kind of a recursive problem. You should be able to quickly get yourself in the ballpark of an answer for any kind of problem that can be thrown at you. There’s nothing wrong with having a team member that can specialize in certain areas, and in fact, it simplifies strategy: If we see a parsing problem, throw it to Bob, Dan gets maze searches and walk problems, Tim gets all math problems, etc.
Practice a full contest with your team
If you’re going to a contest that is fairly long (more than 4 hours), it pays to do a practice problems from a previous year of the contest, giving yourself the closest possible conditions to what the actual contest will present. The best lessons to gain from this deal with how you work with your teammates, and how to manage workload. Most contests are designed so that it’s damn hard to finish all of the problems in the given time limit, and you’ll be much better off if you have a baseline from which to develop a strategy.
When unsure, submit!
Some contests are structured so that you don’t get points taken off for wrong submissions until you have a correct submission. In environments like this, it is far better to submit a program you’re unsure of than to never submit it at all. You’re primarily scored on how many you get right, so the chance you get it right weighs heavier than the chance that you get it wrong.
Note, however, that you should also make sure that your solution should work. Don’t take this as a carte blanch invitation to not think about the edge cases of your algorithm, or whether or not your solution is going to work at the maximum allowed input size. These are very important concerns, and should be worked out before you even start coding. However, if you find out that your program threw an exception when it shouldn’t have, there’s nothing wrong with getting another submission wrong to try to narrow down the cause of the problem.
Be a font of knowledge
You should know a few classic problems, as well as their solutions. You should know what the knapsack problem is, as well as its solution, and why the solution is referred to as “pseudo-polynomial”. You should be able to program the “N-Queens” problem in your sleep. You should be able to easily write a Tower of Hanoi solver, and you should be able to solve a maze. These are easy problems, and being able to reduce a new problem into one you’ve solved once before can drastically reduce your coding time.
Have a good time
The reason you are doing this is to gather with a group of nerds, eat a bunch of food, drink a gallon of coffee, and to chat up people who share a common interest with you. If you’re not having a good time with your friends and fellow nerds, you’re missing the point entirely!
Popularity: 67% [?]
Comments
2 Responses to “How To Do Well in Programming Competitions”
Leave a Reply
When i get better at C++ I would love to enter some competitions.
Nice Read
I actually competed in an ACM contest, and the best info I can give is program in C if possible. Also the best practice is actually setting a time limit to do the problems in.