How can I compete?

I sometimes get questions from people asking me about how to get into competition programming, how to practice, how to use the various problem archive websites and so forth, so I thought I’d write a blog explaining how it all works. Most of the practice and competition sites out there have very good guides for this very thing, so this post will mostly give a short description of your various options, what I think of them, and it will hopefully be useful to those that are currently in the dark about this kind of thing.

Before I get into describing the various online options, if you’re in university or high school there is two main competitions that you could potentially get involved in. For high school students this is the International Olympiad of Informatics (IOI). I’ve never been involved with this competition, so I don’t know a lot about it. I do know that it is a world-wide competition and up to four individuals from a country can compete. There’s typically a national round first in order to choose a country’s four members. If you’re in high school and have some programming skills it might be something to consider. I’d first try finding some information about previous competitors from your country and find out how to get involved.

University students can compete in the ACM Intercollegiate Programming Competitions (ICPC). This is the largest competition of its kind and the type of competition I’ve been primarily involved in as a competitor and coach. Participants compete on teams of three with a single computer for five hours. The teams that solve the most problems in the least amount of time win. Recently, the top 100 teams from around the world meet to compete against each other in the world finals.

To qualify for the world finals, you have to place high in a regional level competition. The world is divided into around 40 regions. In North America, usually you have to be one of the top two teams in the region to move onto the finals. If you’re in university, find your region and see if your school has a team. If they don’t, then I encourage you to get involved. You just need a faculty member to sponsor you and hopefully they can help you get whatever funding is necessary for travel.

Ok, great, you’re sold on the idea of competing, so how to practice? There’s several great websites out there that can help. Most of them follow a similar format; problem statement, with description of input and output formats, and several example test cases. You submit to an online judging system, usually through a form, and the online judge compiles your source and runs the executable against a hidden set of test cases. If you pass everything, you solved the problem. Be very careful when you start, you need to match the specified input and output formats exactly. Even if you are off by a period or whitespace, your answer will be wrong.

UVA Online Judge – This site contains thousands of problems and an online judging system. To use the site, simply register, then pick a problem, solve it offline on your own computer, and when you’re satisfied, submit it through the UVA online submission form. You’ll get an email indicating whether the problem was accepted (yay!) or if your code produced a wrong answer, time limit exceeded, runtime error, or compile error. The site also hosts online competitions, however, watch out for the timezone. One disadvantage of the site is that the problems are not really organized by problem type, so it’s hard to practice certain types of problems. However, if you search the message board for say “dynamic programming” you can often find someone listing problem numbers of this problem type. The site supports C, C++, Java and Pascal solutions.

ACM Live Archive – This site is similar to UVA and run by, I believe, some of the same people. It contains previous problems from many of the regional competitions and world finals. Like UVA, you can submit solutions directly through a web form. There’s also a message board for finding help, although it’s not nearly as populated as the UVA message board. One major issue with this site is they only support Java 1.0, which basically means, they don’t support Java.

Project Euler – I’ve known about this site for a while, but only recently started using it. There’s several nice things about the site. The first is that the problems are listed in increasing difficulty, so problem 1 is suppose to be the easiest and the latest posted problem (currently 266) is the hardest. The other really nice thing is that you only submit an answer to a problem, rather than source code. This allows you to solve the problem in any language that you are comfortable with. It’s a great way to experiment with learning a new language. The problems tend to often be math oriented. It’s a great resource, but since it is a different style than the ACM or IOI competitions, it may not be as good a representation of how it is to compete in those particular competitions.

CodeChef – I just discovered this site after a friend sent me a link. It’s a fairly new competition website, similar to the UVA online archive. They have a competition every month, where 6 problems are posted and competitors have 10 days to try to solve them. You earn 1 point for each solved problem. There’s also team competitions, but I am not sure how often they are organized.

Problems are organized by easy, medium and hard. There seems to be a great community contributing to the site. The social aspects of the site are tightly integrated with the problem sets and contests in comparison to the older websites that simply have message boards. One other nice thing is that it supports a wide range of languages. Finally, if you do well, there’s prize money :-).

TopCoder – This is one of the largest competition sites available. Anyone can compete, and there’s typically two or three algorithm competitions a month (SRM – single round matches). Once you sign up, you can run the competition applet and try problems from previous competitions. There’s several key differences in comparison to ACM style competitions.

First, there’s two divisions, Division I and II, based on your membership rating. You earn points by competing, people with ratings less than 1200 compete in Division II, everyone else is in Division I. So, when you first sign up, you’ll be in Division II. If you do poorly in a competition relative to other people with similar ranking to you, then your rating can actually drop.

Second, there’s always 3 problems, each with different point values. The faster you solve a problem, the more points you get. There’s an easy, medium, and hard problem, the more difficult the more points you can potentially get. Third, unlike ACM contests where after you submit you get a judgement about your problem, on TopCoder, submissions are not judged until after the competition. If you decide to re-submit, you lose 10% of your original point value. Unlike, ACM contests, you do not have to worry about writing input and output parses based on some described format. Typically, you are asked to write a specific class with a method that takes certain parameters and returns a certain parameter.

Finally, contests only last an hour and 15 minutes. After the coding part of a competition, there’s a 10 minute break, and then a challenge phase. During the challenge phase, you get to look at other people’s source code and challenge their solutions. If you make their code fail, you get extra points and they lose whatever points they would have potentially scored. Once this phase is complete, the judge’s hidden input cases are run against all submitted programs. If you fail any cases, you lose whatever points you accumulated for that problem.

There’s several great things about training on TopCoder. There’s lots of competitions, so it gets you use to competing. Because you really only get a single submission, it can help you improve your accuracy. You can see other people’s source code, so it can be a great way to learn how to solve a problem or learn a better way to solve a problem. There’s also editorials after each SRM describing how to solve the problems. The problem archive is nicely organized and searchable based on different criteria like difficulty and problem type (DP, greedy, search, etc). Also, if you are very talented, you can earn a substantial amount of money competing on TopCoder. Many contests and tournaments are organized by companies as a way to recruit potential employees.

This post is already quite long, so hopefully that’s enough to get any newbies out there pointed in the right direction. Next time, I’ll post about how to run your own competition and provide some suggestions for how to get things going at your own school.