USA Computing Olympiad Picks Final Four

Director, USACO


On June 15, fourteen students from around the United States traveled to the University of Wisconsin — Parkside to participate in the seventh USA Computing Olympiad Training Camp. Their goal — to become one of four students to represent the United States in the Central European Olympiad in Informatics in Brno, Czech Republic, and later in the International Olympiad in Informatics in Antalya, Turkey, October 9—16. These final fourteen students were chosen from over 300 participants who had entered the three Internet competitions and the National Championship held in April.

The fourteen finalists were: David Cheng, Junior, Brandywine HS, Wilmington, DE; John Danaher, Junior, Thomas Jefferson HS for Science and Technology, Alexandria, VA; Gary Huang, Sophomore, Appleton West HS, Appleton, WI; Bill Kinnersley, Junior, Lawrence HS, Lawrence, KS; Percy Liang, Junior, Mountain Pointe HS, Phoenix, AZ; Benjamin Mathews, Senior, St. Marks HS, TX; Jon McAlister, Senior, Langham Creek HS, Houston, TX; Ilia Mirkin, Sophomore, Thomas Jefferson HS for Science and Technology, Alexandria, VA; Oaz Nir, Sophomore, Monta Vista HS, Saratoga, CA; Vladimir Novakovski, Freshman, Thomas Jefferson HS for Science and Technology, Alexandria, VA; John O'Rorke, Junior, Centennial HS, Boise, ID; Kaushik Roy, Senior, Montgomery Blair HS, Silver Springs, MD; Daniel Wright, Senior, St. David's College (South Africa), Lafayette, CO; Daniel Zaharopol, Junior, Vestal Senior HS, Vestal, NY. Also attending the camp as a guest was Mathijs Vogelzang, Senior, The Netherlands.

All New Training Materials

Preparations for this year's camp began in April when head coach Rob Kolstad and Hal Burch met in Colorado Springs over Hal's spring break and began studying past IOI competitions. After studying past competition, they identified sixteen problem types that appear in programming contest problems. Among those sixteen, they found that, 80% of the time, only a handful were used. They also discovered that when several different algorithms are combined into one problem, it becomes much more difficult to get the problem right.

Armed with this knowledge, Rob and Hal began creating a personalized training program for the participants, based on which algorithms participants knew well and on which ones they were weak. This was determined by a diagnostic exam given at the first session. It was quickly discovered that dynamic programming was a universal weakness among the participants.

During the eight-day training program, topics such as "Crafting Winning Solutions" by Greg Galperin, "Graph Theory" by Brian Dean, and "Debugging & Test Data" by Russ Cox were presented by the other coaches.

The first challenge round was held on the fourth day of the camp. It was the traditional five-hour competition in which each participant worked on finding solutions to four problems: Bessie's Gambit, Alfalfa Field Forever, Bull Dozing, and Playing Herd. Every problem had been "cowified" in keeping with our Wisconsin dairy farm tradition. This allows the staff a creative outlet unparalleled in other academic competitions!

Automatic Grading

The grading was done automatically and at a distance by an ingenious program created by Russ Cox. Russ sent the source code for each program over the Internet to his PC back at Harvard, which contained his grading program. Everything worked as planned, and within a couple of hours all programs were graded and returned. His program revolutionized the way we graded all programming competitions this year and the way we'll go in the future.

Recreation

For recreation, we visited the student union rec room on the first night, where we enjoyed unlimited bowling, pool, and ping-pong. Ultimate Frisbee was the game of choice for relaxation. In addition, this year the participants were treated to a private lesson in Disk Golf and played a newly installed eighteen-hole course on the UW—Parkside campus. In the evenings we played Mancala and a business simulation game. Participants wrote programs to play Mancala, which they played against each other, with the moves projected onto a big screen for all to admire.

Special Events

The jeopardy-like quiz show complete with multimedia sound and graphics, hosted by Rob Kolstad, was a special treat. This event got even the most serious of computer nerds to laugh — a major accomplishment. Movie night, a picnic in the park, and a picnic at the beach of Lake Michigan helped relax the participants.

The second day of competition followed the same pattern as the first. Once the scores were back from the automated grading program, we combined the results from the two days and ranked them all. As usual, the top three were easy to spot but the fourth was not. After a discussion of the merits of those who were close, a vote was taken and the final four selected. They were, in alphabetical order: David Cheng, Percy Liang, Ben Mathews, and Daniel Wright. The first alternate was Jon McAlister.

The awards banquet followed at a restaurant on the Lake Michigan shore. Everyone received an individual picture, a group picture, and a finalist or team-member certificate. The top four each received a personalized trophy. Of course, we could not resist handing out special certificates immortalizing a particular behavior unique to each participant.

The following day we made a visit to the dairy farm owned by farmer Jim. He was a replacement for farmer Paul, whom we had visited for the last four years. Unfortunately, after three generations of milking farmer Paul has decided to give up dairy farming. A wind storm last October had blown down a small barn and a silo, and that, coming on top of falling milk prices, was the last straw.

Then it was off to Six Flags Great America and the chance to ride "Raging Bull," the newest and most challenging roller coaster. Just trying to get a ride on all the roller coasters in the park was a full-day enterprise.

Once again, the curtain came down on another successful USACO training camp. Thanks to the generous support of USENIX, over three hundred students in the United States and an equal number abroad were challenged by the competitions provided by the USACO. All expenses for food, travel, lodging, awards, polo shirts — you name it — were paid for by a grant from USENIX.

The final four team members have been chosen and have their tickets for the trip of a lifetime to the Central European Olympiad in Informatics in Brno, Czech Republic, and the 11th International Olympiad in Informatics in Antalya, Turkey.