Join 3,512 readers in helping fund MetaFilter (Hide)


Teen Mathletes Do Battle at Algorithm Olympics
December 2, 2010 8:21 AM   Subscribe

In today's example of kids smarter than you and I, Wired follows the exploits of two teens competing at the International Olympiad in Informatics.
posted by reenum (14 comments total) 16 users marked this as a favorite

 
I'm glad someone's doing this and I'm glad it's not me, but then I was very handsome and modest at 18.
posted by 2bucksplus at 8:38 AM on December 2, 2010


Brings back fond memories of the International Math Olympiad. The Communists whipped us every year, but boy, we had fun.

That these problems can be judged instantly and automatically is a nice innovation; at the IMO, we had to wait two days for the panel to finish grading the papers, and I'm told there was epic judge-wrangling and arm-twisting by the coaches behind the scenes.
posted by escabeche at 8:43 AM on December 2, 2010


Can someone explain why Korotkevich's solution is accepted for the sample problem? From my reading of the question, there's no guarantee that if you ask the same question twice, you will get the same answer.
posted by tksh at 9:06 AM on December 2, 2010


Is there any correlation between success in the IOI and theoretical computer science research? The analogy I am thinking about is % of Fields medalists who are also IMO contestants/winners. A lot of the incentive structure seems to be geared around tech companies that might use this event as a recruiting ground.

Also, ouch:
Someone spots Korotkevich. The organizers crowd around him, patting him on the back, congratulating him on his second straight win. Kolstad watches Korotkevich quail from the attention and shakes his head. “He was ahead for 98 percent of the competition. The question is,” Kolstad says slowly and with utter gravity, “will he die a virgin?”
posted by bodywithoutorgans at 9:19 AM on December 2, 2010


Not sure which direction you want this analogy to go, but here are his year's Fields Medalists: Stas Smirnov (IMO gold medalist, 1986,1987), Ngo Bao Chau (gold medalist, 1988,1989) Elon Lindenstrauss (bronze medalist, 1988) and Cedric Villani, the only one who didn't participate.
posted by escabeche at 9:29 AM on December 2, 2010


Backwards. I was wondering about success in IOI and theoretical computer science research.
posted by bodywithoutorgans at 9:35 AM on December 2, 2010


I did this. It pretty much defined me when I was in high school. I was never involved in an international competition, but I was never defeated in the many midwest regional competitions where I participated. I too preferred Pascal. You're just less likely to get hung up on an undetected syntax error or an unflagged out-of-bounds reference in Pascal.

I actually feel like I've lost something since then, but I'm not sure what. I had much less depth of knowledge, but I was much faster. I'm a CS prof now, and I still code a lot, but it's very different with the benefit of ten years of graduate education and research experience. If I could take what I know now and pack it into my 16-year-old brain, I would have been scary.

Oh, and it turns out I won't be dying a virgin.
posted by rlk at 11:01 AM on December 2, 2010 [4 favorites]


tksh: "Can someone explain why Korotkevich's solution is accepted for the sample problem? From my reading of the question, there's no guarantee that if you ask the same question twice, you will get the same answer."

The key insight is that the three parts of the answer (man, implement, location) are independent because the oracle will tell you which part of the answer is incorrect. So if you guess, say, Mustard with a wrench in the library and the oracle says you've got the wrong location, you don't need to check any other possibilities involving the library.

The worst case for Korotkevich's solution is (6 6 10). It takes five incorrect guesses to rule out the first five men, at which point you know it's man six. Then you start guessing (6 1 1) (6 2 1) etc. until five guesses later you know it's implement six. (Of course, the oracle might not be so obliging as to tell you all your mistakes in order, but that's why Korotkevich kept counters.) For each part, you need one fewer guess than the number of possibilities, which leaves you the twentieth guess for the solution you now know to be correct.
posted by d. z. wang at 12:46 PM on December 2, 2010 [1 favorite]


bodywithoutorgans: Is there any correlation between success in the IOI and [success in] theoretical computer science research?

Based on the
one data point I have: Yes. Absolutely.

Also, huge ups to WIRED for correctly calling the IOI an algorithm contest and not just a "programming contest".
posted by erniepan at 2:56 PM on December 2, 2010


Oops, I dropped this: </a>
posted by erniepan at 2:59 PM on December 2, 2010


Just one data point, but I went to the IOI a couple times and now I'm doing computer science research.
posted by esprit de l'escalier at 11:22 PM on December 2, 2010


The smarter kid would say "you and me," by the by.
posted by thinkpiece at 12:20 PM on December 3, 2010


I actually didn't like that phrasing in the post. I think that a big part of life is discovering the nature of your own intelligence. As soon as you start deferring to "smarter people", you may as well give up on your own self-discovery.
posted by esprit de l'escalier at 2:55 PM on December 3, 2010


I had much less depth of knowledge, but I was much faster.

I'm sure you realize this by now but it still bears repeating: The best optimizations are algorithmic. Depth of knowledge will definitely save run time and will probably save coding time.

Then again, I usually overestimate how much time I'll save by thinking. I'll often think for 3 days to save myself 10 minutes of typing...
posted by DU at 5:36 AM on December 8, 2010 [1 favorite]


« Older Sam Cohen, Father of the Neutron Bomb RIP....  |  The Defense Department forced ... Newer »


This thread has been archived and is closed to new comments