Thursday, August 16, 2007

Informatics Olympiads (IV): Besides the IOI

IOI is the crown jewel of the CS competitions, but there are quite a few other competitons one has to know about.

Other high-school olympiads. Several regional olympiads have been created, modelled after the IOI. The ones I know are:

  • CEOI (Central European)
  • BOI (Balkan)
  • BOI again (Baltic)
If people from Asia or South America know other regional olympiads, please post a comment.

Policies for who goes to these olympiads vary from country to country and from year to year. Typical policies (Romania has tried all of them in different years):
  • send the top 4 to prepare them for the IOI
  • send younger kids (nonseniors) who haven't qualified to the IOI, so that they get experience for next year
  • send people on places 5-8 out of fairness (to allow other good students to get medals and build up a CV)
Regardless of which rule is employed each year, the students attending are obviously among the best. These olympiads are very competitive, and getting a medal in one of them is a serious achievement.

CEOI, in particular, is insane. It includes only the best countries from Europe, plus USA as a special guest (these countries typically get only gold and silver at the IOI). Getting a medal at CEOI is often likened to being among the top golds at the IOI.

Post high-school. Like the Putnam in mathematics, there are some olympiads for college students, but they are somewhat different in flavor:
  • the ACM Programming Contest: teams of 3 people try to solve 8 problems in 5 hours. By design, some problems are meant to have easy algorithms but painful implementation (the prototypical examples are from computational geometry).

  • TopCoder: individual contest over a long period of time, with many rounds conducted online. Huge prizes (in the 100K range). Each round is short (1 hour) so you have to be insanely fast at implementation.

  • IPSC (Internet Problem Solving Contest): teams of 3, working from home. You don't submit code, only answers to some truly massive problems.
Like the IOI, these are also highly competitive contests. Many IOIers participate, capitalizing on the previous exercise. Even more importantly, many students who weren't ready enough to make it to the stars during high school, are extremely motivated to add some prizes to their CV in university years.

In Eastern Europe, where most tenured faculty haven't heard the word research and attending classes is outright depressing, these competitions may be the only opportunity for students to not let their university years go to waste. (The other option is to work a full-time job as a programmer, for one of the miriad outsourcing companies.)

Unfortunately, the contests are less telling as to algorithmic skills than the high school olympiads. They rely on lots of coding under time pressure, so many pure algorithmists feel turned off. The fact that teams matter so much also makes results harder to interpret. (The successful teams typically include a very fast coder, and a theoretician who doesn't code... But who's who?)

Personally, I am an outsider (by choice) to these contests. With my slow coding and problems dealing with authority in teams, I would have been hopeless :)


Aryeh said...

Here's a "programming" question from a hopelessly confused mathematician: how do you get that "recent comments" thing to work in blogspot? Many thanks in advance. (NB I don't know html. Anything more complex than "copy this code and paste it into there" won't help me...)

Anonymous said...

Mihai .. great series of posts. I should go and look up the problems on IOI and try solving them instead of my boring day job ;)

I was a part of the Math olympiads though never made it to IMO. But the IOI is definitely very challenging.

I hope it helps sharpen my algorithmic skills!

Anonymous said...

Apparently you can also compete online from home this year:

It starts... in 34 minutes!

Mihai said...

Since Dave will not volunteer the information, he is among the IOI-turned-theorists that I forgot [gold 2000, silver 1999, silver 1998].

Anonymous said...

Hi Leo,

Blogger supports comment feeds now:
and hope it helps.

Another faithful reader of "Abs Reg" :-)

Anonymous said...

Hi Mihai!

>> In Eastern Europe, where most tenured faculty haven't heard the word research
>> and attending classes is outright depressing, these competitions may be the only
>> opportunity for students to not let their university years go to waste.

That is true; however, I think there is yet another alternative. Thanks to the web, students around the world have access to a great deal of information about research. This, in particular, includes various sources of open problems. Here are some open problem lists that I am aware of, I am sure there are many others. So, one can pick a problem or two, and try to crack them. Smart people + lots of free time + interesting questions can yield very interesting research. And, at least in principle, one can learn writing papers from examples.

So I guess what I advocating is moving from doing studies to doing research without the unnecessary step of getting an advisor. Boy, I really hope my students are not reading this blog...

Well, just in case they are: obviously, there are still advantages of having an advisor. Among other things: some open problems are really hard, other ones are unclear or even do not make sense, some could have been solved recently, etc. Some of this issues can be solved by reading recent surveys, some cannot. And learning with queries tends to be easier than learning from examples only.

Still, wrestling with open problems can be a great and useful experience for undergrads, even though frustrating at times. And it beats attending boring lectures for sure...


rgrig said...

I have no experience with Olympiads and everybody says that the problems there are less about coding and more about getting a good idea than the TopCoder problems. Personally I think that coding is hard and tests the ability to handle multiple cases and to reduce the number of cases. Both are important skills. Coding is not only about writing code, but also about figuring the best way to teach the computer your idea. It's a translation task, in a way.

Also, I think that the `hard' TopCoder problems are getting more and more interesting, especially since they tend to be written by former IOI contestants. For these my problem certainly isn't implementation speed, but thinking speed. (The following might look interesting to this community: PostfixRLE, RepeatingFreeStrings, SkipList)

Some people claim that being persistent is more important than being quick. I tend to agree. At least, I think that constant factors in thinking speed are not too important :)

Anonymous said...

Good post.

The list of successful participants you gave included only MIT students, and all of them are/were doing theory@mit; what happens to the other participants? How many of them ended up studying/working in theory/algorithms? (your text suggests that IOI are mostly algorithmic) Or perhaps most of them are doing systems or just programming? Any thoughts/opinions?

Anonymous said...

I don't agree with Piotr that the advisors are unnecessary (though he also backed off a little). Yes, there're a few lists of open problems (just take Clay's Institute 1 million dollars problems 8-), but what is really hard is to find open problems which are doable, problems that fit student's skills and background. Most of papers and most of good students' works don't solve open problems listed anywhere in the web.
Of course Piotr is right that one should study lists of open problems, but I don't think one should assume that this will replace a good advisor. It can be an excellent addition though.

Anonymous said...

Hi anonymous,

My critique of advisors was only half serious - I personally hope that they are at least somewhat useful creatures ;) However, in places "where most tenured faculty haven't heard the word research", one does not have much choice in this matter. In this case, the "do-it-yourself" approach to research might be a pretty reasonable option.

As far as the open problem lists go. Obviously, if a prize for solving a problem is $1M, one should think twice about attacking it. And even the "free" problems can be pretty hard. Then again, one does not have to solve all of them, one is good enough. And in any case, the experience gained while wrestling with the problems can be very valuable later in life.


Mihai said...

To Anon [Sun Aug 19, 02:09:00 PM]: The reason most people I mentioned are doing theory@mit is that those are primarily the people I know :) Check out the comments section of my post II, which includes other people (non-MIT), that folks reminded me about.

If you really want to know how many people ended up doing AI, systems, just programming etc., check out the link I had in post II to the list of Romanians. That is a rather large sample, and it should give you some idea. Of course, there's no way to get a hold of everyone who went to IOI and ask them what they're doing.

Anonymous said...

If people from Asia or South America know other regional olympiads, please post a comment.

I realise this is an old post (by blogging standards), but I'd just like to mention that we have a (recently started) Asia-Pacific Informatics Olympiad.

Mihai said...

Cool! It's nice to hear about the new Asia-Pacific olympiad.

Seems right now the Chinese team dominates it strongly, but a local olympiad tends to make every country better, so the result may get more mixed in a few years...