Thursday, June 28, 2007

Programming Contests

One of my biggest interests is programming contests. The number these days is ever increasing and more importantly, so is the diversity. In this post I aim to identify and discuss some of the major contests and pick out the parts I enjoy most.

The first international contest I competed in (in 2004) was the International Olympiad in Informatics (IOI). While it is only for high school students, it has a very different structure to any other contest. It is an individual contest consisting of two rounds of three problems with five hours per round. Part marks are assigned based on correctness and efficiency and marks are only returned at the end of each round. I like the split over two rounds, which allows for one to have a bad day and come back on the other day. I also like the way it squeezes you on efficiency, which often contests with a single yes/no response cannot afford. The South African team is picked from the medalists of the South African Computer Olympiad (SACO).

By far the most prestigious contest is the ACM International Collegiate Programming Contest (ICPC), for which I competed in the 2004 and 2005 regionals and the 2005 and 2006 world finals. As the name suggests it is only open to university students. Teams of three compete against one another by solving as many of the ten problems in five hours, with a single PC per team. I like the teamwork that is forced upon teams with only one PC, which also requires very good planning/management skills. The problems are usually of the best quality and the types of problems vary, which allows for teams with mixed skills such as including mathematicians in the team. In this and many other contests, you get the result of a submission back immediately. I must say I am a little against this as it makes teams submit without testing much at all. You also get no part marks which results in very close results, often split by time penalties.

The Internet Problem Solving Contest (IPSC) is similar in structure to the ACM ICPC. The crucial difference is that it is an online event without any specific locations. The contest is open to anyone and everyone and not restricted to students. It also allows for any programming languages and hardware/software resources. These differences all allow for a much larger number of contestants. There are generally about 12 problems to solve in the five hours, each with an easy (1 point) and difficult (2 points) level. Teams of three are competing against one another. The problems are typically far more mathematically inclined than the ICPC, although the problems vary rather drastically between years. This year they even included a simple image processing problem. I really enjoy the problems in this contest and that is the major factor towards this being my second favourite contest.

Another contest which many compete in is the TopCoder. They run contests about once a week - online, as with the IPSC. I must confess that I dislike the format so much that I have only ever competed twice. The short duration of three problems in about 75 minutes really kills it for me. I don't like solving problems so quickly. I like having to think about them. That's why you'll see as you read on that I have a preference for the marathon-style contests. All the top competitors define their own macros to squeeze out an extra few minutes. I'm sorry, but as much as it might prove fun to some people, I just cannot pull myself take part in it again. The Google Code Jam follows a very similar structure and runs on the TopCoder platform.

In South Africa we have a national contest which started in 2005 called the Standard Bank IT Challenge. This is another one I dislike, but for different reasons. However, it has some interesting new ideas. The first round (heats) are four hours with five problems. However, two of the problems are related and you only receive the second part after solving the first part. This adds an interesting dynamic in that you have to be cautious not to leave the problem with two parts too late, although it's typically one of the more difficult problems which makes things very interesting. You are also in teams of four for this one, which adds more to the team aspect. The finals consist of six problems with six hours to solve them in. This time there are two problems with two parts. One of those is very different to all the others as it's an interactive problem. In the three years the contest has run the interactive problem has been the most interesting: foxes and hounds, maze game and suicide chess. The other problems are all mostly simulating some process, with very picky and vague problem descriptions. It's the problems and the poor judging that kills the contest for me. The only reason I compete is that it's a national contest and the prizes are very nice.

My favourite contest to date is the ICFP Programming Contest. It's a 72 hour marathon contest with almost no limits whatsoever. Anyone can participate, teams can be of any size and can even be spread across the world (as will our team be this year). There are no restrictions on programming languages, software or hardware used. There are in fact no restrictions I can think of other than the 72 hours you are given and that they asked us nicely last year not to reverse engineer the platform provided. I competed for the first time last year with a team of seven students. The 72 hour time frame is just perfect I think as it's long enough that you can concentrate on the problem for the full time without getting the feeling you're giving your life up to the contest like with semester-long contests. I also really enjoy having no limit on team size as it allows you to get some people coming in to help on parts they're experts at and then go back to their normal lives while the contest continues. This makes it reasonable to get people not willing to give up much of their time. You can also very easily get advice from people, which takes up very little of their time. Even if the person is not in the country, you can still contact them.

Just last week while in Zurich I was told about the Extreme Challenge. This is another marathon contest, but 24 hours this time. The teams are restricted to three and you aren't allowed access to any external resources, including the Internet. The finals are held in Budapest, Hungary. You are given a single power cord and a desk and you bring all your own hardware - and you can bring as much of it and whatever you like! It sounds like a very interesting contest, although I still think I'd prefer the ICFP due to the lack of restrictions. The problems seem very interesting though and they are very polished, which is seldom the case. I will definitely aim to try it out next year as I like these marathon contests. Until then, I can only go on what others have told me and that is that is is an excellent contest.

For those of you who haven't heard, there are no Code Jams this year. After four of them last year, the organisers are a bit exhausted and needed a break. With this break, some of the coaches discussed the possibility at the Google ACM meeting last week of Google starting a new, very different contest. The idea spawned from the Extreme Challenge, while they though extending it to 72 hours would be more exciting. The idea behind it is that the Code Jam is so short that it doesn't necessarily identify good software engineers, but rather those who can very quickly solve small problems. With this longer contest, planning is required as well as team work, which should provide a better of software engineering skills. Details are still very rough, but the idea definitely caught their interest. I think it's a great idea! So who knows, we might just have started a new Google contest!! :)

Those are just a few contests I have competed in. If you have another favourite, I'd love to hear about it. As I said, I only recently found out about the Extreme Challenge and it sounds like one I should have heard of long ago. Also, if you have anything to add about my analysis of these contests I'd love to here them too. This is one thing I'd really like to get your feedback on.

3 comments:

  1. From my experience I have to agree with what you said about the IT challenge. The problem descriptions and strict (in some cases you might as well call it ridiculous) output formatting strain the competition, and the judging is also a problem.

    For one of our solutions, the feedback we got from the judges was that we had an incorrect answer for only 1 of the test cases. We made changes and resubmitted about 5 times, with the same feedback every time.

    Then after about an hour they came in to tell us they made mistake with that particular test case. Having lost valuable programming time, there was no comprimise other than moving our submission time to that of the first correct solution :(

    ReplyDelete
  2. Hi Marco. One very interesting kind of programming contests you left out is Perl golf.

    ReplyDelete
  3. That's starting to get into a whole new category of contests. While I admire the obfusticated code people can produce and I do try understand what goes through their minds when putting it together, I honestly don't see myself coming up with anything worthy of entering in such a contest in the near future.

    ReplyDelete