*****UPDATE******
Due to the recent political events in Egypt, the 35th Annual World Finals of the Association for Computing Machinery (ACM) International Collegiate Programming Contest (ICPC) was moved to Orlando, Florida. The contest will take place from May 27 to May 31. Best of luck to the School of Mines team!
*******************
By Katie Aurand
Editor in Chief
Three School of Mines students will travel to Sharm El-Sheikh, Egypt, in February 2011 to compete in the World Finals of the Association for Computing Machinery (ACM) Programming Contest. One hundred teams will compete at the World Finals. More than 8,700 teams, made up of more than 26,000 students from 86 countries, vied for those 100 slots at regional competitions. At the finals, the School of Mines will join 16 other American universities, including Duke, MIT, and Princeton.
“This year’s success, I think, were the choice of practice problems, careful team planning by the coaches, an emphasis on team dynamics, combined experience of the team members, and the extra practices,” said Matthew DesEnfants.
The team of DesEnfants, Randy Foudray, and Ethan Robish, all computer science majors, are advancing to the World Finals after they finished third in the regional ACM competition.
“Very few schools ever get to see results like we had this year,” said DesEnfants. “We cleaned house.”
The four other School of Mines teams finished fifth, seventh, 13th, and 14th against 223 teams representing 63 colleges and universities.
“We usually do very well,” said DesEnfants, who has been competing for three years. “Our school is known throughout the region for being competitive and keeping the larger schools on their toes. It’s very David v. Goliath. The reputation of the programming team is one of the reasons I came to the School of Mines.”
DesEnfants cited two reasons why his team was able to do so well.
“1. We had a secret weapon – Randy Foudray,” said DesEnfants. “For as fast as he could churn out code, I was amazed the keys on his keyboard could spring back fast enough to meet his next strike. He’ll probably be escaping the Matrix soon.
“2. We fought wasps. This may sound silly, but I think practicing in the most infested room in an already infested McLaury built up a certain level of mental stamina. By competition day the number of wasps had died down, and we could focus more on the problems at hand. That being said, we smote more wasps than we solved problems that day.”
The roles on the three-person teams are typically known as the “coder,” the “algorithms guy,” and “the tester”.
“Randy was definitely the coder of the team, and he was very good with algorithms,” said DesEnfants. “Ethan was also a very talented with algorithms and general problem solving. I mainly focused on test cases and debugging.”
“Randy can not only type fast, but he can think as fast as he can type,” said Robish, who competed for his first time this year. “It’s sometimes a challenge to keep track of what he’s doing while watching him code. Matt comes up with his share of solutions. He also is great at helping others develop solutions and asking key questions that give a sanity check. I think I’m decent at debugging. When debugging another person’s code, I’ll ask questions to help me understand what they are doing, and a lot of the time my questions will help them realize errors on their own. No one knows code like the person who wrote it.”
When the competition starts, the team gets all of the problem statements. They must do a quick scan through them and decide which ones to focus on first. Doing the easy ones first is crucial for getting a good time. The team that solves the most problems wins, but any ties are broken by time. With 9 problems and 225 teams at regionals, there are a lot of ties. The team uses one computer and must share time at it. While one person is coding, the other two are working on another problem. When the person on the computer submits a solution or gets stuck, another person can hopefully jump on the computer and start coding up a solution to a different problem. When a person gets stuck on a problem, he prints out his code and combs through it by hand to find errors.
“The dream team would have three very fast, mathematically-fluent problem solvers with insane coding skills who could produce thorough test cases. The kind of people needed to build a team like that don’t usually compete in the ICPC because they have already escaped the Matrix and are busy trying to free humanity from the sentient machines with which we are unknowingly at war.”
The contest structure is as follows: Each team is allowed one computer and all the print materials they can find (class notes, printed Wikipedia pages, old contest problems, etc). They cannot use the internet beyond submitting problems, and all pages other than the submission page and the live standings are blocked. They also are not allowed to use any other programmable devices, so TI-89’s are out. Because they resources are so limited, deciding who gets computer time to hash out a problem is very deliberately thought out. The coaches aren’t allowed to give them advice or hints on how to solve a particular problem, so as soon as the competition starts, they are essentially on their own.
When the team submits what they believe to be a working problem, one of their coaches will return with a slip of paper that says if it is correct or not.
“We only get credit for completing a problem if we get a Correct,” said DesEnfants. “If we don’t get a Correct, we have to figure out on our own why the answer was wrong, the formatting was bad, or the time limit was exceeded.”
DesEnfants said there were a number of easy problems where some of our class notes from Analysis of Algorithms, Data Structures, and Finite Structures turned readily into a solution with some tweaks, like using Pascal’s triangle to quickly count the paths through a grid. The medium difficulty problems required a little more creativity.
“The problem that stuck us for a long time was #5,” said DesEnfants. “It had to do with determining how much time a person could save by speeding along a highway with a single stoplight. Given a few parameters, we needed to calculate the average time savings. Most teams throughout the region were solving it rather quickly, but we just couldn’t get it to work for a long time. We were just making our solution too complex. When we finally got a working solution, we were worried for a while that our incorrect submission penalties might have knocked us out of the running for World Finals.”
Now the team is preparing for the competition in Egypt.
“On top of the extra practices that we’ll have with our coaches soon, I’ll be hitting up Project Euler and old practice problems in my spare time to help with my algorithms, math, and problem solving skills,” said DesEnfants. “We’re also going to have a bit of a crash course in Egyptian culture before we leave to make the best of our trip.”
DesEnfants credited the coaches Dr. Logar, Dr. Corwin, and Roger Schrader, and our Computer Science and Mathematics faculty for their guidance and expertise, and recognized the achievement of the other School of Mines teams who did not make it to the World Finals, but still placed really high at regionals.
“I was amazed how well the Green and Silver teams did,” said DesEnfants. “I knew they were really bright guys, but Green was ahead of us for a long time early in the day, and Silver knocked out most of the region. Keep in mind that our Silver team was made of guys who didn’t make the original cut but kept showing up to practice anyway. They were doing so well that our coaches knew it would be a mistake to not let them compete. It says a lot about a program when even the rookies can part waters, so to speak.”
