SciTech

Student progammers take on world finals

First-year and sophomore students from Carnegie Mellon’s School of Computer Science will be competing against 87 other teams in the world finals of the Association for Computing Machinery (ACM) International Collegiate Programming Contest (ICPC) this March.

The programming team, the “Tartans,” will join 87 teams in Tokyo, Japan, with the goal of claiming awards and a scholarship from IBM. The Carnegie Mellon team consists of sophomores Young Sub Bae and Nate Bauernfeind and first-year Lawrence Tan.

The contest began at the university level. According to ACM, 300,000 students took part in university-level competition this season.

Then, each university sent its top teams to compete against other universities in the regional competition. Carnegie Mellon’s team placed second out of 116 teams in the regional competition at the University of Cincinnati, beating upperclassmen and graduate students.

Carnegie Mellon professor and team coach Greg Kesden said, “Over the years, more schools in the U.S. have gotten involved.” Consequently, the contest has become more competitive.

In the regional and world competitions, university teams are asked to solve eight real-world problems and develop tests for these programs in five hours. The judges accept only correct submissions from teams, and teams that submit incorrect answers are penalized.

A team’s placement depends on how many programs the team solves, and in the case of a tie, the team with the lower time wins.

Bauernfeind said that the hardest part about the regional competition was communicating with his teammates about how to approach the problems. “Every problem had a different twist or something special to it,” he said.

Bauernfeind also said that each person took one problem, and then they paired up on problems that no teammate could solve on his own.

Tan, who competed in a similar contest in high school, said that programming contests like the ICPC are always challenging. He said that only one person is allowed to type at a time. Meanwhile, the other two teammates must work out solutions to their problems. “Keyboard time is precious,” he said.

Teammates are also free to discuss the problems with one another before beginning the program. “Sometimes, you just need a second opinion,” Tan said.

Tan said that the team had finished the two hardest problems in the regional competition within one minute of each other, completing all eight problems with a half hour to spare. “We just tried and we just hoped for the best.... It all worked out in the end,” he said.

Kesden said that the team must work together if it is to complete all of the problems.

“They need to talk about each problem together.... That’s actually one of the biggest challenges we find as coaches,” Kesden said. He said that some of the smartest students at CMU are used to working individually.

The team has three coaches: Kesden, systems scientist Eugene Fink, and doctoral student Betty Chang. Kesden said that each coach has a different strength that he or she contributes to the team.

“We work together very very well.... We’ve really added a lot of strength and different strengths [this year],” Kesden said.

All of the problems in the contest are real-world. Bauernfeind said that one of the problems from the regional competition, for instance, asked students to create a program that designed a roof, given a number of divisions in the roof and a set of points.

When approaching a problem, Bauernfeind said that he tries to first figure out what the problem wants. Then, he uses the given information to determine how to solve the problem.

Bauernfeind said that the problems can be categorized into different types, such as geometry and dynamic programs. “Basically, in the world finals, you see different kinds of problems put together.”

The problems vary in difficulty. According to ACM, two of the problems are intended to be solved in an hour by a first- or second-year student, two are intended to be solved in an hour by a third-year student, and two are intended to decide the first-place team. No team is expected to solve all eight problems in five hours.

In preparation for the world finals, Bauernfeind said that the team is going through all of the world finals problem sets since 1999, checking their solutions with their coaches.

Tan said that the level of competition at world finals is much higher than at the regional competition. He said that competitions have to be prepared to write programs of all different types.

Teams that finish in the top four places receive gold medals. The top-scoring team also receives the World Champion Cup and $10,000.
Bauernfeind and Tan both said that they would be interested in participating next year.

“I’m excited to be in the type of environment ... where we’re working on programs for a purpose,” Bauernfeind said.

“It’s interesting and it’s fun,” Tan said.