Programmed to succeed

Works in Theory qualifies for the computer-programming world finals.

By Benjamin Recchie, AB’03
Photography by Dan Dry

The computer-programming team Works in Theory qualified for the world finals for the third straight year, but this year’s competition in Egypt was postponed.

Say you have a rectangular chocolate bar, made up of rectangular pieces, measuring three pieces by four. And suppose you have four friends who want part of your bar—six, three, two, and one pieces, respectively—but only if their pieces can be broken off from your bar in rectangles themselves. Can it be done? And more importantly, can you write a computer program to tell you so?

Welcome to the Association for Computing Machinery’s International Collegiate Programming Contest, in which teams from colleges and universities around the world test their ability to program under pressure. By placing second at the Mid-Central USA regional competition, the University of Chicago team Works in Theory—composed of two undergrads, Korei Klein and Matthew Steffen, both ’11, and second-year graduate student Denis Pankratov—qualified for the world finals, which were to be held in Sharm el-Sheikh, Egypt, from February 27 to March 4. The finals, postponed because of the unrest in the country, will instead be held May 27–31 in Orlando, Florida.

In a typical competition, dozens of three-person teams are sealed in a room together for five hours. Each team receives eight to ten problems to solve with a program and a computer with which to write their code. The solutions must work for the test cases the judges provide (in the above example, the number of friends and the sizes of their desired pieces of chocolate) and must be submitted in one of three programming languages (Java, C, or C++).

Rankings are based on the number of problems solved and the amount of elapsed time. Failed solutions can be resubmitted—but that adds time to a team’s total. The team that solves the most questions the fastest wins.

“The first couple of hours are really crucial” because some problems are harder than others, says Pankratov, a five-year veteran of the contests (he started as an undergrad at the University of Toronto). Before the competition begins, team members agree to split up the problem set, with one person taking three or four problems. Each competitor quickly judges the difficulty of his or her problems and immediately gets to work on any that seem straightforward.
Then the team member looks at the rest of the set, tackling ones he or she can do alone. For difficult problems, the team members discuss how to approach a solution. The easiest problems might require 15 minutes to solve; the toughest, an hour and a half. Pankratov notes that not even the best teams in a competition can answer every question in the allotted five hours.

At Works in Theory’s weekly practice, coach Borja Sotomayor, a computer-science lecturer, gives sample problems to work on, compares the team’s performance with results from previous tournaments, and then advises the members on problem-solving strategy. The University’s three teams—besides Works in Theory there is also Terminal 1337ness, which placed third at the regional tournament, and Gigagargoyles, which placed 23rd—practice together. A typical Saturday session can last two hours, but some last the full five hours of a real competition.

This academic year marks the third year in a row that a Chicago programming team has qualified for the world championships. Last year Works in Theory also won second place at regionals and earned an honorable mention at the finals in Harbin, China. As hard as the team members have been working to place high, and maybe even win, they know they face a big challenge—the world finals tend to be dominated by Chinese and Russian teams.



Return to top