Every year some 70 programming teams advance to the ACM (Association of Computing Machinery) world finals programming competition. This many teams may seem to be a large number, but it represents only a small fraction of the 1000-plus universities that tried to go but did not survive their regional competitions, whether in California or Kuala Lampur. At every competition, as the big day approaches, teams assemble alone or with their coaches. They familiarize themselves with the host site computers, they discuss strategy, exercise their brains on tricky algorithms. They are about to go through one of the most intense, exhilarating, challenging, pumped-up times of their lives. The Waterloo team thinks it's fun. So does their coach, Gord Cormack.
In a typical programming contest teams receive a set of problems at the opening bell. Each team has its own computer running the languages that the team will use to solve the problems. At first they almost ignore the computer, whispering and mumbling about who will take the first problem and who the second. "Hey, the third one looks kinda tricky, but I have an idea. Okay?"
As team members construct code for problems, they merge it into programs that must first be debugged, then tested. If the team thinks a particular program is ready, they submit it to the judges, who test it on a special set of data. If the program gives correct answers for the data, it is judged a success. The judges then attach a coloured balloon to the team's table, indicating that another problem has been solved. There is no letup in the process. Sometimes two or more programs are nearing completion, sometimes none. Occasionally a team is struck by a combination of circumstances that, in the sporting world, would be called a “slump.” Everything seems to work against them, whether a bad choice of problem or too much Coca-cola the evening before. Waterloo programming teams have often presented Cormack with cliffhangers, including one at the 1998 world Finals in Atlanta, in which they placed third!
As the five-hour contest proceeds, everyone glances at the scoreboard from time to time. It shows the number of problems solved by each team, with any penalty points deducted. The board is updated continually until the last hour, when all is silence. But who better to give a blow-by-blow sports report than journalist Sean Silcoff of Canadian Business magazine, who traveled with the year 2000 team to Orlando, Florida, where team members Donny Cheung, Ondrej Lhoták, and Jeff Shute represented Waterloo:
Ninety minutes into the contest, St. Petersburg has the early lead, with three correct answers. Waterloo is now 0 for 2, and showing the stress. "I can't believe what is happening," mutters University of Alberta coach Piotr Rudnicki. "I know them very well. They've never done anything like this, having two wrong submissions in a row for extremely simple problems."
An hour later, the competition is half over. Waterloo is out of the top 20, far behind St. Petersburg, which is putting on quite a show. The Russian team has just received its fifth balloon of the day. Trailing it are Germany's University of Ulm and Hong Kong's Chinese University, with three correct answers each. Waterloo has only one. It's beginning to look like a disaster for the defending champions.
Hanging over the Waterloo team like a dark cloud is Problem F. Lhoták has tried it twice and still hasn't cracked it. The problem should be the easiest of the contest, but it's confounding a lot of teams. What most of them don't realize is that there's something wrong with the data. But Lhoták doesn't give up. He figures a way around the discrepancy. At the 156-minute mark, the judges accept his submission, giving Waterloo its second correct answer. Relief. Twelve minutes later, Waterloo scores its third. Excitement. The team is back in the game, and suddenly in fifth place. Seventeen minutes later, Cheung solves the rubber-stopper stumper. The team vaults into second. Jubilation.
Over in the stands, Cormack looks like a new man. But other teams are gaining. At the four-hour mark, when the scoreboard is frozen until the contest ends. Waterloo has dropped to seventh place, stalled at four correct answers.
But Cheung and the boys are on a tear. Waterloo gets another correct submission, its fifth. Cheung pumps the air with a fist and issues a loud "Yes!" With about 30 minutes to go, the team nets its sixth correct answer. More air punches and high-fives. But Lhoták looks around the room and sees other teams starting to collect their sixth balloons. Still, he knows Waterloo is destined for the top 10; with one more correct answer, they could be the champs.
With only 10 minutes left, Cheung submits the team's seventh answer and springs from his chair, allowing Shute to take his place and start coding No. 8. Two minutes later, the judges have ruled on Cheung's answer. It is wrong. Shute bolts up and Cheung takes over control of the computer. He has a fix ready, and pounds it out in mere seconds. He resubmits, and with less than five minutes to go, the answer comes back from the judges: Correct.
Lhoták rocks up and down in his chair like he's on a bucking bronco, his face clenched in glee. Cheung, standing in his stocking feet, starts to shuffle about in a victory dance similar to what a cocky wide receiver would do after catching a touchdown pass. Shute remains focused on the computer, however, trying to type in the lone remaining answer before the final countdown. With 40 seconds to go, he submits his program. If this one's right, they're guaranteed winners. Moments later, the answer is rejected.
It doesn't matter. The contest is over. Cormack bursts onto the floor. 'I'm so proud of you guys,' he gushes amid bear hugs and handshakes. 'I can't imagine what you were thinking two hours ago.'
Any hopes of winning, however, are quickly dashed. A St. Petersburg team member comes over and reveals that they, too, got their seventh correct answer in the final hour. With so many penalty points amassed against Waterloo for all their late answers, there's no way they'll topple the Russians. But they beat everyone else. No other team in the room has managed seven answers, although fellow Canadians from the University of Alberta and the University of Toronto post respectable 10th and 15th place finishes."
Who can doubt it's a sport? The problem is that major networks do not carry even the ACM World Championships. But if you want to see the team in action, all you have to do is attend the next World Championships. Everyone (well not quite everyone) will be there.
Gordon Cormack must be one of the harder working faculty members in the School of Computer Science. Not only does he run a full-blown research program and teach a full roster of classes, he also coaches the UW programming team. This means not only shaping the team for big competitions, but little ones as well.
He seems uncomfortable with the suggestion that coaching the programming team somehow enhances the academic program at Waterloo. It's not about school, but about sport. "As with any sport, it has intangible benefits, of course. It's nice if our success enhances the prestige of the university but, as far as I'm concerned, it's exactly like fastball." On the other hand, team members must be familiar with many areas of computation to be successful: algorithms, computational geometry, operations research, graphics and so on. His colleagues may disagree, but Cormack is even reluctant to say that team members are improved programmers, for all the preparation and practice. "They get some intellectual benefits," he allows, "For one thing, team members must be equally agile in both theory and practice."
Cormack became coach in the academic year 1996-97, replacing Jo Ebergen who had coached teams since 1993. It was Ebergen who helped to launch Waterloo's winning tradition, placing in the finals in his first year as coach, then winning Waterloo's first world title in 1994. Ever since that year, Waterloo has always made the finals.
Is it stressful being coach? "The most stressful time for a coach," says Cormack, "starts about halfway through the contest." Waterloo teams have traditionally been slow starters. It has often happened that by this point the team had barely solved any problems. For example, even the 1997-98 'dream team,' as Cormack calls it, had a struggle in the ACM finals held in Atlanta. They were behind by one problem but, try as they might, they just couldn't solve it. Only in the last minute of the contest did they submit their latest attempt at a solution, with no idea of whether they were successful or not.
Even by the time of the post-competition banquet that evening, the tension
had not let up. Winners were announced in reverse order. As soon as they announced
the eight-place finishers, however, we knew that out final solution had been
a success. After all, the eighth-place team had solved all six problems. At
that competition, the Waterloo team placed first in North America and third
in the world. Four years earlier the programming team had won the world championship
and it would again the following year in Eindhoven in the Netherlands.
Are there perennial favorites or teams that Cormack looks forward to meeting?
The Russians are very strong, with St Petersburg State University winning the
world title two years in a row. The Czech Republic and Slovakia also field strong
teams year after year. Other contenders include the Universities of Ulm and
Freiberg in Germany, as well as several Polish and Chinese universities.
Preparations for the annual contenders begins early. There are usually two contests in the fall, with many local contestants. "We have a contest at Waterloo every term. Everyone is welcome. It's an inclusive sport, like road racing; anyone can come out. We get 50-60 students participating. Only a quarter are serious contenders. Some people surprise themselves when they qualify."
For those that make the team, just being at the World Championships is a big thrill. And to win? Unimaginable. But as every team knows, it takes a great coach to ge great results.
For more details of the contest, visit Cormack's home page at
http://plg.uwaterloo.ca/~gvcormac/
The two sample problems displayed here barely hint at the vast range of subject matter which programming problems may address. The first problem is stated and explained fully, while the second problem, quite different, is left for the visitor to solve. These examples were adapted from actual programming contest problems. The second example may be considered a challenge problem.
A plane contains a finite number of circles, each with its own position and diameter. No two circles intersect. In addition to the circles, two points A and B are given, neither inside any of the circles. Write a program that finds the shortest path from A to B which does not pass through any of the circles.
Analysis: Sooner or later, someone analysing this problem might imagine a string joining A to B. At first the string winds loosely among and around the circles. Then the string is slowly pulled taut. As it tightens, the string hugs every circle it touches, becoming part of the circle's arc. At this point, the "aha" insight may emerge. Any shortest path will consist of alternating straight line segments and arcs of circles. Since the number of circles is finite, a program that solves this problem merely has to compute all line segments that are mutual tangents of the circles in all possible pairs.
If the points A and B are treated like degenerate circles, they can be added to the list. The program then runs through the list of line segments, attempting to link them into paths from A to B. It may do this by using a depth-first-search technique, calculating the length of each path (being sure to include the arc between consecutive line segments), retaining only the shortest path found thus far at any point in the search process.
The Ministry of the environment maintains a number of weather stations in the high arctic. To enable the stations to stay in touch, the Ministry is about to invest in two different radio technologies. Every station will have the same model of radio transceiver for direct communication, provided that the distance between them does not exceed the critical value D (to be given) which reflects the power of the transceiver. In addition, some of the stations (number to be given) have satellite communication and any two of these may communicate, no matter how far apart they are.
Since higher transceiver power (D) costs more, the Ministry has decided to cut D to the bare minimum, provided that every pair of stations can communicate one way or another. Can you make a recommendation to the Ministry?
The input comes in the following parts: 1. the number of test cases your program must solve; 2. the number of stations with satellite radio (up to 100) and the number of stations (up to 500); 3. coordinates for each of the stations, where coordinates are integers between 0 and 10,000. The output of your program must be a single value for D, a real number with two decimal points.
Sample Input
1
2 4
0 100
0 300
0 600
150 750
Sample Output
212.13
Note: If you are a high school student and were able to program your computer to solve this problem successfully in the space of two hours or less, please contact Gord Cormack! (See above.)
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Monday, 11-Sep-2006 14:19:28 EDT
