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.
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
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
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
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
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
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]
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]
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
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
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
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
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
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]
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 Everybody dies | Pharmacologic Waterboarding Newer »
This thread has been archived and is closed to new comments
posted by 2bucksplus at 8:38 AM on December 2, 2010