STOCKHOLM – Three hundred computer science students from around the world face off Tuesday at Sweden’s Royal Institute of Technology (KTH) in a five-hour competition to see who’s got the sharpest problem-solving skills.
In the ACM International Collegiate Programming Contest, held annually since 1977, three-member teams from 100 universities lock horns with some the of the knottiest word problems you can imagine, and write the algorithms that will undo them. The competition is operated by the Association for Computing Machinery (ACM) headquartered at Baylor University, and receives sponsorship from IBM Corp.
Winners will be honoured at the Stockholm Concert Hall, where Nobel Prizes are distributed, Tuesday night.
More than 7,000 teams from 1,800 universities were winnowed down to the 100 finalists in regional competitions last fall. Four Canadian teams made the cut, from McGill University in Montreal, University of Alberta in Edmonton, University of British Columbia in Vancouver and the University of Waterloo, Ont.
The Waterloo team has a heritage to protect. It’s one of the few schools that’s had a world championship more than once.
How do you prep for this kind of mental effort? Practice. Assistant coach Richard Peng figures the teams done about 100 of the word problems since the regionals, with two practice sessions a week.
Choosing the teams doesn’t sound like rocket science. Results from local contests, where questions are answered individually rather than by teams, are usually the best indicator, said coach Ondrej Lhotak. Out of the 60 or 70 who test, he said, “usually, the same people come out on top.” Knowing how well they’ll work together helps, he said, but usually the ranking is enough.
But only one team from each school that qualifies at the regionals can go to the finals, and “it’s not always the team you expect to win that wins,” Lhotak said. Waterloo qualified three teams this year, but could only send one.
Two of Lhotek’s team are back for a second hack at a championship. Third-year student Malcolm Sharpe made an appearance in 2007, while second-year student Konstantin Lopryev was at last year’s finals. Both those teams finished ninth. Andy Tsz Yin Kong is the rookie on the squad. One advantage they might have is their complementary skills. Sharpe does a lot of work with geometry. Lopryev does what he calls “visa card” problems, with lots of mathematical details. And Kong builds test cases to try to demolish the answers.
“You start by reading the questions to find what’s easy,” Sharpe said.
“As soon as we see a problem we know how to solve and there isn’t one we can solve faster, we call the problem,” Lopryev said.
“It’s a bit of both (collaborative and individual effort),” Sharpe said.
Peng called the team from Tsinghua University in Beijing “the scariest team this year.” Google them, he said, and you’ll find a long list of individual awards.
If a win isn’t in the cards, it’s not their Canadian colleagues they want to beat. The rivalry’s a friendly one, and teams sometimes practice together. Lopryev names Massachusetts Institute of Technology, runner-up last year and regularly in the medals, as a team to beat. Peng adds Carnegie Mellon University in Pittsburgh to the list.
Though Waterloo has two championships in its trophy case, Lhotak said, “It’s about time” for another.