Teen Mathletes Do Battle at Algorithm Olympics
- By Jason Fagone
- November 29, 2010 |
- 12:00 pm |
- Wired December 2010
Neal Wu’s last chance for international glory, and maybe America’s, too, begins with a sound like a hippo crunching through a field of dry leaves—the sound of 315 computer prodigies at 315 workstations ripping into 315 gray envelopes in unison. “You have five hours,” a voice booms across the packed gymnasium. “Good luck.”
At his desk on the gym floor, Wu, age 18, pushes his glasses up on his nose and squints. He shouldn’t need luck. This is a coding competition—the International Olympiad in Informatics, held in August at the University of Waterloo in Ontario, Canada—and Wu is one of the world’s top competition programmers.
Gold medals awarded at the International Olympiad in Informatics (1999-2009)
He just graduated from Baton Rouge Magnet High School in Louisiana; his parents are chemical engineers originally from Shanghai, although Wu was born in the US. In seventh grade, he took first place in a nationwide contest for middle schoolers called Mathcounts. (There’s a Neal Wu fan club on Facebook that celebrates his “awesome math skills.”) Yet according to Rob Kolstad, the US team’s 57-year-old head coach, Wu is merely “very good” at math. His true gift is for creative problem-solving with code. In 2008, the first year he competed at the IOI, he finished 10th out of 300 contestants. In 2009, he moved up to seventh place. Since then, he has competed in six coding contests run by Kolstad’s organization, the USA Computing Olympiad; he won three of them with perfect scores. Wu has the relaxed disposition of a star athlete; he’s confident without ever letting on that he is America’s Great Nerd Hope. “I hate to say he’s the Tiger Woods of computer programming,” Kolstad says, “but he shares the properties of cool, calm under pressure, and consistent, consistent performance.”
Cool or no, there are a lot of expectations on Wu as he shuffles through the contents of his gray envelope. Four stapled packets of paper. Four word problems designed to test programming prowess—specifically, the ability to crunch incredibly huge and complex data sets in seconds. For each problem, Wu first has to choose an algorithm, or series of computational steps. Then he has to code it. Wu’s coaches have drilled into his brain 16 standard algorithms with names like Two-Dimensional Convex Hull, Greedy, Eulerian Path, and Knapsack—an arsenal of mathematical machetes for hacking through thickets of numbers—and in Wu’s years of coding he has flexed and massaged the algorithms into no fewer than 100 subtle variations. But what makes IOI so difficult, unpredictable, and yes, even dramatic is that competitors like Wu may have to invent and code their own ad hoc algorithms on the spot. One-of-a-kind solutions to one-of-a-kind problems. From scratch. In five hours.
It’s grueling work, so Wu starts out slowly. He flips through the problem sheets, scribbling an occasional note with his mechanical pencil. The dominant sound in the gym changes from the shuffling of paper to the clacking of keys, but Wu resists the urge to type right out of the gate. “Typing is hypnotic,” Kolstad says emphatically. “When you’re typing, you’re not solving problems.”
But Wu’s nemesis, the Boy Wonder of Belarus, does not subscribe to this theory.
A tall kid with skinny arms, short brown hair, and a bashful smile, Gennady Korotkevich started competing at IOI when he was 11. When Wu was 11, he didn’t even know about programming. At last year’s IOI in Bulgaria, Korotkevich upset Wu and everyone else to take first place, becoming the youngest winner in the contest’s 20-year history. This year Korotkevich is back again, at the ripe age of 15, looking to deprive Wu of his last shot at winning IOI. Next year Wu will be in college and therefore ineligible.
Clockwise from top left: A printout of the Maze problem; Gennady Korotkevich of Belarus; work in progress on Maze; American Neal Wu.
Photo: Michael Schmelling
Their styles couldn’t be more different. While Wu is relaxed and thoughtful, Korotkevich is a jackrabbit. “My parents are programmers, and now I like it as well,” he says in tentative English. Unlike the sociable Wu (who interned at Facebook last summer), Korotkevich squirms when I talk to him about his abilities, insisting he’s nothing special. At IOI, he sticks close to his Belarus teammates and coaches. The gossip at IOI is 40 percent about the word problems, 10 percent about which country’s coaches have the best liquor (Canada, hands down), and 50 percent about Gennady Korotkevich. Ask the kids who’s going to win this year and regardless of whether they’re Kazakh or Japanese, Swiss or Egyptian, they’ll invariably grunt, “Belarus, Belarus.” And then they’ll start laughing, as if to say, haven’t you been paying attention?
This morning, Korotkevich began typing five minutes and 40 seconds after the competition began. Like several of the elite competitors at IOI, he can code as fast as he can touch-type. Three minutes later, Korotkevich completed his first program: a mere 22 lines of Pascal.
The three approved IOI programming languages are Pascal, C, and C++. The Western kids, including Wu, tend to use C++, the most modern and streamlined of the three. But Pascal still has a following in Eastern Europe and Asia, even though coding in it is like “building a car with just a screwdriver and a wrench,” says Troy Vasiga, this year’s IOI chair.
One Murder, Two Solutions
Competitors at the 2010 International Olympiad in Informatics tackled eight programming problems in two days of competition. Here’s one of the simpler challenges, along with the solutions supplied by Gennady Korotkevich and Neal Wu. Of the 315 competitors, 269 received a perfect score.
The Task: Dr. Black has been murdered. Detective Jill must determine the murderer, crime scene, and weapon. There are six possible murderers (numbered 1 through 6, Professor Plum to Mrs. Peacock), 10 locations (1 through 10, ballroom to cellar), and six weapons (1 through 6, lead pipe to spanner). Detective Jill tries to guess the correct combination (there are 360 possibilities). Each guess is a theory. She asks her assistant, Jack, to confirm or refute each theory. When Jack refutes a theory, he reports that one of the guesses—murderer, location, or weapon—is wrong. The contestants are tasked with implementing a procedure that plays the role of Detective Jill. A brute-force program that tests all 360 theories earns a mere 50 points. An efficient program that tests no more than 20 theories earns an additional 50.
Korotkevich’s solution: Clear-headed and sleek. He sets up three variables, x, y, and z, to represent the murderers, locations, and weapons, respectively. Then he systematically tries all the combinations in order, increasing the variables incrementally. In other words, if his first theory is 1, 1, 1 and the computer tells him that the location is incorrect, his next theory is 1, 2, 1. This is efficient because all he has to do is keep track of which murderer, which location, and which weapon to try next. That’s just three things to remember.
Language: Pascal
Lines of code: 22
Wu’s solution: Successful but more complicated than necessary. Wu first sets up a master list of all murderers, locations, and weapons. To do this, he creates three arrays called, naturally, mur, loc, and wep. Then he loops through the arrays, crossing off incorrect guesses as he goes. Each time he forms a theory, he searches all three lists to find a murderer, a place, and a weapon that hasn’t been crossed off.
Language: C++
Lines of code: 46
Korotkevich uploads his Pascal code to a network of 10 machines running a set of grading programs. Appropriately, there are no human graders at IOI; instead, robots provide immediate results, which in 2010 were posted for the first time on a live online scoreboard. A few seconds after Korotkevich submits a solution, his program receives a perfect 100 and the scoreboard shows him in first place.
At the 20-minute mark, Korotkevich posts a perfect score on his second problem, going up 200 points on Wu.
Meanwhile, Wu picks up his mechanical pencil, clicks the lead a couple of times, puts it back down. He likes to alternate between a mechanical pencil and a pen, drawing graph axes in ink and labeling the vertices in pencil, which allows him to erase if he wants to backtrack. He’s still thinking, still strategizing. He has yet to write a single line of code.
At the one-hour mark, Korotkevich runs his score up to 255. He’s cruising now.
Wu, a smallish kid with black hair that is less unkempt than that of your ordinary nerd, cranes his neck and glances around the gym, taking in the scene: kids from 83 countries, their desks arranged in cloverleaf clusters of four, looking—despite their races and nationalities—like members of the same tribe. Many are wearing the black Google T-shirt that was stuffed into their IOI schwag bag, and most of the rest are decked out in team-issue polos or T-shirts from prior competitions. (Notable exceptions: the three young women in head scarves representing Team Libya.) Korotkevich is out there somewhere, a mysterious wraith in a blue pullover. Wu has no idea how well his rival is doing—during each competition period, the kids can see only their own scores—but the contest organizers certainly know. They’re up in the gym balcony, tracking the live scoreboard on their laptops. And it looks pretty bad. Wu is not even on the board yet. This is a slaughter in the making.
And then, 70 minutes into the competition, Wu places his fingers on the keyboard.
Competitive programming may strike you as history’s worst idea for a sport—shuffleboard minus the bracing speed, the Scripps National Spelling Bee without the adorableness. In fact, battle-coding is a surprisingly popular global pastime, indulged in by thousands of high-school and middle-school programming clubs and turbocharged by websites like TopCoder, a sort of social networking and gaming site for algorithm nuts. At TopCoder, kids and adults alike battle one another to solve IOI-style problems for cash prizes. Member ID neal_wu shows up in red, signifying elite status. To get your name in this color, you need a TopCoder rating of 2,200 or better. To become a “target”—the elite of the elite—you need at least 3,000. Wu’s rating is 3,248, making him number six in the world. (Korotkevich also has a TopCoder handle, tourist, and is ranked number five.)
As if TopCoder weren’t enough, many of the national programming teams host their own sites, where they post sample problems and practice exams. The USA Computing Olympiad site is run by Kolstad, who also holds a weeklong camp every year for 15 elite American coders—at the end of that week, the four-person IOI team is selected. With his thick shoulders and deep bellowing voice, Kolstad seems more like a football coach than a computer guy. “I don’t know how to do most of the algorithms,” he says. He prefers to focus on mental preparation and attitude: “Just like Vince Lombardi, who, of course, didn’t play football on the field with his players.”
The Training Pages section of USACO.org is open to coders from all countries, but Kolstad says it’s dominated by the Chinese, who have been commanding the team portion of IOI for as long as anyone can remember (“n large years,” in IOI-speak). They also dominate the International Collegiate Programming Contests. In February, a team from China’s Shanghai Jiaotong University won the ICPC world championship in a stroll, while several American universities tied with 16 other countries and foreign universities for 14th place. The trend is the same in both contests: Western decline, Eastern ascendance. Since international collegiate coding competitions began in 1977, US universities won the first 13 ICPC contests in a row and went on to earn four titles in the 1990s; the 1993 champion squad from Harvard included a young Tony Hsieh, now CEO of Zappos. But the last American victory came in 1997, and since then the contest has been ruled by Russia, China, and Poland. “We’re getting outtrained,” Kolstad laments.
China’s approach to IOI is proof of just how serious the contest has become and how tied up it is in notions of national prestige and economic competitiveness. To earn a spot on the Chinese team, a coder has to beat 80,000 of his compatriots in a series of provincial elimination rounds that last an entire year. Then he—the competitors are almost all male—has to sit on a stage in front of hundreds of onlookers and answer questions in English like “How will you show the traditional culture of China to the foreign friends?” says Yi Wu, a member of China’s team. China is an extreme example, but pretty much every kid roaming the Waterloo campus this week has beaten hundreds or thousands of countrymen just to get here. Even the losers are brilliant.
Photos: Michael Schmelling
Universities and corporations have taken notice, treating the IOI—competitive programming’s crowning event—as the equivalent of the NFL Scouting Combine. This year’s primary sponsor is BlackBerry maker Research in Motion, whose CTO spoke at yesterday’s glitzy opening ceremony featuring the Waterloo Warriors cheerleading squad. Other sponsors include Lenovo, IBM, Amazon.com, and Google. It’s understandable that so many tech companies would want to nurture IOI: Google is famously built atop an algorithm called PageRank; Twitter’s “Who to Follow” feature is a set of algorithms; Amazon’s entire site, from sales rank to product recommendations, is a system of interlocking algorithms. IOI may be an academic competition, but its purpose is to advance a discipline that has driven the growth of the Internet and turned geeks into billionaires. Here in Waterloo, what’s at stake for the kids is a college scholarship, but what’s at stake for the industry is something larger: the ability to keep innovating new algorithms to make sense of an increasingly complex world.
The organizers of IOI, acknowledging this happy nexus, have decided this year to sneak a few problems with real-world applications into the coders’ gray envelopes, particularly one called Languages.
By the time Wu gets to Languages, around the 90-minute mark on the first day of competition, he has already made up much of the ground he lost to Korotkevich, posting two perfect scores on the two easiest problems within seven minutes of each other. Now he’s got three and a half hours to crack Languages. Good thing, because it’s a hell of a curveball: Given 10,000 text strings selected from random Wikipedia articles written in various human languages, create a program that identifies the language. The competition’s science director, Gordon Cormack, threw Languages into the mix out of sheer curiosity; he genuinely didn’t know what the best answer was and hoped the kids would show him. Now they have: Wu’s 227-line program analyzes the frequency of each letter in the string (English has fewer ks and zs than, say, Czech), narrowing the possible tongues to a handful, then refining the guess by breaking the string into four-letter chunks and analyzing the frequency of the chunks. With this strategy, Wu can distinguish 56 languages, everything from Azerbaijani to Vietnamese, 85 percent of the time.
Wu finishes the day in seventh place, followed by his three US teammates: Michael Cohen, an energetic, curly-haired Elijah Wood look-alike and the son of a physics professor; Wenyu Cao, from the prestigious Phillips Academy in Andover, Massachusetts; and Brian “Hamster” Hamrick, from Thomas Jefferson High School for Science and Technology in Virginia. (Kolstad and the kids joke that the US team boasts “two and a half Asians,” with Wu and Cao as the two and “Hamster,” whose father is Caucasian, as the half.) They’re no slouches: This summer, Cao studied advanced math at MIT and Cohen studied physics at the University of Maryland. All except Hamrick will begin day two within striking distance of becoming the overall winner. In fact, their performances are good enough to push the US into a virtual tie with China—a shock even to Kolstad.
The coach is giddy at the chance to bring attention to the American coding program. The only kid returning next year is Cao, so Kolstad will have to recruit a new team to carry the torch, on top of securing new funding, as he does every year. (Team USA is itself an ad hoc hack; one of its main sponsor, for some reason, is IBM Canada.) Nothing could make Kolstad’s job easier than a splashy rout of China.
As for the Boy Wonder from Belarus, he wraps up the day in first place, 11 points ahead of Wu. He submitted 400 lines of tight, efficient code and held the lead almost the entire five hours. Once or twice, when an opponent from Bulgaria or Singapore overtook him, it was almost like he could “sense the scoreboard,” as Kolstad puts it. Then he’d shoot back to the top. The day’s events have dealt a fatal blow to the theory that Korotkevich is a mere coding robot, an uncreative automaton; if it were true, Languages would have fried his circuits. But he aced it, achieving slightly higher than 90 percent accuracy. “It was interesting, actually,” Korotkevich tells me when I stop him on the steps of the gym, his hands clasped behind his back and eyes darting from side to side like a panicked squirrel. “I am not used, quite, to such problems.” He tells me that the rumors are untrue: He practices only three to four hours a day, not six to seven.
There’s nothing to do now but wait for the second and final day of competition. Some of the English-speaking kids pass the time with an afternoon game, their version of Taboo. At a long table in a dining hall, each competitor writes down four nouns on slips of paper, crumples them up, and tosses them into a hat. The kids will have to guess the words from verbal clues. The hat fills with words to warm a coder’s heart: bubble sort, polynomial, integration. Also czar, Lakers (a tricky one for this crowd), serial killer, and scandalously, a word whose clue is given as “a way of showing affection with your tongue.”
“French kiss,” Wu guesses correctly as the table explodes into giggles.
Every year at IOI, there’s a question so difficult that it humbles even the adults who try to crack it. This year, that question comes on day two. Called SaveIt, it’s a classic ad hoc problem, not solvable with any standard algorithm. SaveIt asks the coder to calculate a table of the shortest distances through a large transportation network consisting of 1,000 cities and 36 hubs. Then, to get the full 100 points, the coder has to cram that table into an incredibly small space and decompress it without losing any information. It’s as if someone gave you an inflated beach ball and said, here, pack this into a cookie jar. If you find the air nozzle, it’s simple. Otherwise, it’s impossible.
At IOI, if you don’t get full points on a program, you’re allowed to tweak it and resubmit it, which means that with most IOI problems you can start off with a rough approach, a kludgy halfway solution, and optimize it as you go. But you can’t do that with SaveIt. If the key insight eludes you—if you don’t grasp how the transportation network can be represented with 1s and 0s (the integers, not binary code) and therefore compressed quite easily—you’ll spend hours bashing your head against your desk. Cormack, the science director, tells me that he anticipates SaveIt will stump the vast majority of the kids. No more than 10 of them will get the full 100 points, he predicts, and it will take the whole five hours.
Wu, wearing a Facebook T-shirt, denim shorts, and running shoes, rips into his gray envelope. As on day one, he pages through the tasks with gentle, unhurried motions. When he gets to SaveIt, he thinks about it for a while, then puts it down and decides to start on the day’s other hard problem instead, called Maze, whose difficulty is more like climbing a ladder than a sheer rock face. Maze requires the coder to draw a series of mazes of various sizes and complexities. A riff on a classic unsolved question in computer science, it’s a type of problem called NP-complete, meaning that it’s possible to find a good-enough solution with a combination of creativity and moderate computing power, but to find the best possible solution could take trillions of years. The first couple of mazes are small enough to create by hand, but as they get more labyrinthine, the kids have to write code to generate them.
Meanwhile, Korotkevich starts on the two easiest problems, called Memory and Traffic. He solves Memory within five minutes and Traffic within 19, and by the 90-minute mark, he earns partial scores on Maze and SaveIt.
Wu is off to a characteristically slow start, posting a measly 18 points to Korotkevich’s 274. (He submitted an incomplete version of Maze to make sure he was on the right track; if he weren’t, he would have gotten 0 points rather than 18.)
Up in the gym’s balcony, a Dutch technology entrepreneur named Kim Schrijvers is doing ESPN-style color commentary on a live web feed. He notices the gap between Wu and Korotkevich. “Is Neal toying with us?” Schrijvers asks.
I take a walk, get a cup of coffee, come back, reload the scoreboard. No change. Wu in 272nd place; Korotkevich in first. Two hours left. Over on his patch of gymnasium floor, the Boy Wonder from Belarus allows himself a slight display of emotion. He smiles. Cormack rushes up to me in the balcony.
“Gennady got SaveIt, he got it,” Cormack says, making a noise like he just coughed milk through his nose. “Wasn’t hard enough! He got it with two hours to go. Amazing.” It’s not only the speed that impresses Cormack—it’s the fact that Korotkevich used a sophisticated compression technique known as arithmetic coding, one that requires graduate-student-level chops. I ask Cormack if he’s surprised to see a 15-year-old who knows arithmetic coding: “It would be foolish of us to say that we are surprised by anything that Gennady does.”
Wu can still catch up, but he’s got to hurry. With an hour to go, he’s stuck in 23rd place, struggling with SaveIt. The flash of insight hasn’t hit him. His teammates are having more luck, though: Cohen posts a perfect score on SaveIt and shoots up to fourth place, and Cao thinks he’s almost there. He makes a tweak, compiles his program. Error. Segmentation fault. Crap. Something’s off with his variables… Half an hour left.
“It is quite amazing,” says Vasiga, the contest chair, “how time pressure focuses the mind in terms of optimization. Now is crunch time, when all the neurons are firing and fingers are starting to go at light speed.”
Cao changes an n to an h, and his SaveIt program suddenly runs. He submits it, and the next time the web scoreboard updates, it shows—with 23 minutes left!—Cohen in fourth place and Cao in fifth.
“You have exactly 15 minutes remaining,” the contest emcee booms.
A few more points on Maze push Cao up to fourth place.
“You have exactly five minutes.”
“It’s the desperate time,” Schrijvers says. After all his banging away on Maze, submitting his answers nine separate times, Wu has entered the top 15. But his SaveIt program is still getting only 50 points out of 100. With three minutes left, he makes a final SaveIt submission: 370 lines of C++. He clicks to reveal his score: still just 50 points …
“Time is up.”
Wu slowly threads his toothpick arms through the straps of his backpack. As the gym empties, he lingers at his computer, staring at the screen, as if he can’t quite believe what just happened. He still doesn’t know how he did in relation to everyone else, but he knows that he underperformed in his last IOI. The unflappable Tiger Woods of computer programming looks dazed.
Schrijvers and his play-by-play crew roam the gym with a video camera, capturing footage for the live feed. They spot Wu and stick a laptop in his face so they can record his reaction as he learns the final standings.
“So this is you, Neal,” Schrijvers says, pointing to the web scoreboard. “You are in 13th place.” The top 25 are all considered gold medalists, but that result still stings. Wu looks away and purses his lips, clearly disgusted with himself.
Meanwhile, Kolstad enters the gym, beaming. “Troy, guess what?” he booms at Vasiga. “We won your contest!” Cao and Cohen held on to fourth and fifth places, and “Hamster” Hamrick was 43rd for a silver medal. That was good enough for the Americans to pull off a stunning upset, beating China. They’re the new world champions.
“This is absolutely, absolutely brilliant,” Schrijvers says.
Amid the jubilation, one of the US coaches nods to Wu: Nice job, man. “Aaaaaahhh,” Wu mutters dismissively. He’ll have none of it.
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?”
At the closing ceremonies two days later, the medalists clamber one by one onto a banquet-hall stage for grip-and-grins with various dignitaries. All are male except for a lone, pale-skinned girl from Poland. Wu claps for silver medalist Hamrick and his fellow gold medalists Cohen and Cao.
I catch Korotkevich sneaking a look at himself in a mirror before his big moment. As he hoists the enormous Lucite winner’s trophy, his frail shoulders nearly buckle from the weight. His grin is epic.
Afterward, a slightly bummed Wu flies home to Baton Rouge to start packing for his next adventure: freshman year at Harvard. A month later, I give him a call to see how he’s doing. He tells me he’s taking four classes: Expository Writing, Chinese, Math 55 (a course so infamously punishing that it has its own Wikipedia entry), and CompSci 226, a graduate-level class taught by Michael O. Rabin. (Yes, the Michael O. Rabin, Turing Award recipient and cocreator of the Rabin-Karp string-hashing algorithm.) Wu reports he is the only freshman in the class, and he says that his algorithm knowledge is progressing to “way-more-advanced theoretical things” than IOI contests tend to cover, including “ridiculous” new types of functions.
Wu is toying with the idea of joining the table-tennis club. He has also met with the coaches at the Harvard Computing Contest Club, which sends two teams to the International Collegiate Programming Contest every year. For kicks, he took the tryout test for Harvard’s team. He came in first place.
Jason Fagone (@jfagone) writes for GQ and Philadelphia magazines and is working on a book about the future of cars.
'관심사' 카테고리의 다른 글
| '애국열사 집안'과 '침략자 집안'의 101년 엇갈린 운명 (2) | 2011.03.10 |
|---|---|
| 쿵푸팬더 2 예고편... (0) | 2011.03.08 |
| Elvis Presley - Always On My Mind -full video (0) | 2011.03.07 |
| Apple iPAD 2 실제 동영상. (0) | 2011.03.03 |
| Apple's Jobs unveils the iPad 2 (0) | 2011.03.03 |