CMU students place first at ACM programming competition
A team from Carnegie Mellon recently obtained first place at the regional level of the Association for Computing Machinery International Collegiate Programming Contest (ACM-ICPC), one of the biggest college programming contests in the world, on Nov. 3.
Composed of senior computer science major Nathaniel Barshay, computer science Ph.D. student Yan Gu, and senior computer science and mathematics double major Jonathan Paulson, the team surpassed 130 others from the northeastern U.S. and Canada. Their win qualifies them for the ACM-ICPC World Finals, which will take place in St. Petersburg, Russia, this summer from June 30 to July 4.
“It was a lot of fun,” Paulson said. “A lot of the problems on this particular contest were brute force. It was pretty easy to see what the answer was, but it was hard to code up the solution.”
The competition required members of each team to solve nine complex programming problems in five hours. One of the problems was inspired by a physical game. Say you are given seven hexagons with the numbers one through six written on the sides, and you want to rotate the pieces so that the matching numbers line up. The solution will have one hexagon in the center and six surrounding it. You can pick up the center piece, move it somewhere else and move another piece to the center. The teams had to find an arrangement that solved this puzzle or declare that there was no solution.
“That’s an example of a problem which is brute force,” Paulson said. “You pick the hexagon that is going to go in the center and then you pick the one that is going to go above it.” Knowing that the numbers should match up, there was only one possible rotation for the second hexagon. The next step was to pick the third hexagon that matches.
“You are going to try all possible hexagons to go in the center — there are seven,” Paulson said. Then there are six hexagons from which you can pick the next one and so on. “You just try every possible solution,” he added. Since there were not many possible solutions, the algorithm was fast.
The Carnegie Mellon team was the only one that was able to solve the most difficult problem, a geometry problem. Given four completely arbitrary points on a plane, they had to build a fence around the four points such that every is five feet away from the fence. The fence is supposed to be a square and every point should be closest to a different, unique side of the fence.
“That’s the weird condition,” Paulson said. “The other tricky thing is that the square can be rotated; it’s not necessarily horizontal.”
Paulson wrote his code in the Java programming language, while his teammates used C++. They had trained for a minimum of seven hours each week since the beginning of the semester.
Carnegie Mellon offers the course “Competition Programming,” which Paulson said is good practice for the contest. The course is being taught every semester by computer science professor Danny Sleator, who is the head coach of the team. “The course also gives good practice for Google Code Jam, Facebook Hackathon, and job interviews,” Paulson said. “I think these programming contests are getting more popular.”
In total, Carnegie Mellon sent five teams to the regional competition. The rule is that the top four teams advance in competition, with only one team being allowed to represent each school. Although the other Carnegie Mellon teams got fourth, fifth, sixth, and 23rd place, none of them got to advance.
“The other teams from CMU were our biggest competition,” Paulson said. “We were pretty sure we would be in the top four schools, but we were worried about the other teams from CMU beating us.”
One of the tough parts of the competition is that there is only one computer for each team. “Everyone has a copy of the problem set,” Paulson said. Everyone reads the problems and thinks about them. When a person is sure that they know the right answer and can write the code, he or she can use the computer.
“Whoever thinks that they need the computer for the shortest time for a problem, gets it,” Paulson said. The teammates usually try to work on different problems simultaneously. For the hardest problems at the end, there might be two people working on them, but in general, this is not advised.
“We had two people coding and the last person was just thinking about problems. His job was to find the hardest problems and solve them so that we don’t get stuck on those at the end,” Paulson explained.