Brown CS Undergraduates Advance To The International Collegiate Programming Contest Nationals
- Posted by Jesse Polhemus
- on March 31, 2023
The International Collegiate Programming Contest (ICPC) is believed to be the oldest, largest, and perhaps the most prestigious programming competition in the world. An algorithmic programming contest for college students, it requires teams of three to solve real-world problems, fostering collaboration, creativity, innovation, and the ability to perform under pressure.
Brown CS faculty member Yu Cheng, the department’s new ICPC coach, is himself a prior ICPC World Finalist. On February 25, he brought twelve students to the ICPC’s 2022 Northeast North America (NENA) Regional Contest at the College of the Holy Cross site: one team ranked sixth, earning one of four silver medals, and advanced to the North America Championship (NAC), to be held at the University of Central Florida in May. Their competitors will include teams from 50 universities from the United States and Canada that advanced to the NAC from one of the 11 North America Regional Contests, and top teams from the NAC will continue onward to the ICPC World Finals. Another Brown CS team ranked twelfth and earned one of four bronze medals.
The scoreboard here shows the results of the students working within a five-hour deadline to solve the greatest number of problems in the fewest attempts in the least cumulative time. Eighty-four teams competed, and the four Brown CS teams were ranked 6th, 12th, 27th, and 40th, placing above teams from Boston University, Northeastern University, and Rensselaer Polytechnic Institute. Only one team from each institution is allowed to advance, and Brown University ranked third as an institution.
Team 1 (Bearly Made It): Yuqi Lei, Bin Zhang, Yiwei Zhang
Team 2: Alan Chen, Luke Choi, Mohammad Hijaz
Team 3: Seowon Chang, Brandon Gong, Christina Stepin
Team 4: Daniel Cai, Jay Sarva, Anton Tarazi
Below, we hear from three students who participated in the competition and share their experiences of the event.
“This year was first-come, first-served, so teams were just made by people who reached out to Prof. Yu earliest – I reached out with one of my teammates (Luke) a while back, near the beginning of the school year. We added our final teammate, Mohammad, with Prof. Yu's help in February.
Most online programming contests are all virtual, so ICPC being held in person this year was particularly refreshing. There's just something special about being in a room with other people also talking about the problems that makes it more exciting. We went to the College of the Holy Cross up in Massachusetts for our competition. The exam was in a big auditorium and you had to bring your own laptop this year. It ran for five hours, from 11 am to 4 pm, with lunch served in the middle.
Our team made a ton of silly mistakes, probably due to nerves, and the fact that none of us had been under the pressure of an n-person programming competition before, though it was definitely an exciting pressure. For example, Problem I was a standard dynamic programming problem that we could have been first to solve in the contest, but instead it took us forever to debug after we submitted a WA (wrong answer) solution because we just missed a small case when determining the valid transition states. We also ended up with WA on Problem F because we misread one line in the problem that greatly simplifies the solution from a horrendous mess to implement (also a wrong horrendous mess) to a problem that is classic brute force. Lesson learned: always reread the statement when you get a WA!
Ultimately, I felt like this year's problems were extremely implementation focused (i.e., had annoying implementation, even though the idea was simple), whereas I tend to enjoy problems where the difficulty and beauty of the problem are from coming up with the idea, whether it be clever uses of data structures or finding an invariant. I don't know how other teams or my teammates feel, but I felt like the problems were particularly messy and nasty – not very pretty problems.
For example, Problem K was about determining if two rooted trees are the same (super easy idea, just sort nodes at each depth), but reading in the input was annoying, since they formatted a tree so that (10 (23 23)) would be a node with 10 as the root and 23 23 as the children. Problem E had some floating point issues (teams reported passing solutions with double but not long double because of weird floating point behavior) and solutions to Problem E were rejudged after the contest.
There was also a huge difficulty spike after eight solves (ABEFHIJK were not that difficult), but the remaining problems were significantly harder – congrats again to Bin's team for pulling out a clutch solution to problem L, giving them nine solves.
Despite my personal dislike of the problems, I had a ton of fun. I am definitely going to participate again and I am sure my teammates agree. Prof. Yu is extremely smart and was a great mentor in not only helping us form our team and get organized, but also giving us mentorship in team strategies and problem solving, drawing upon his own experience as a previously successful competitive programmer himself.”
“I love competitive programming contests because they require intense collaboration between teammates, apart from technical skills. Only one computer is allowed for three people in a team, and teammates need good communication in order to make good use of the only computer.
The part I love most in a contest is the ICPC Resolver, which is a tool for graphical animation of contest results. In ICPC, the scoreboard is usually “frozen” in the last hour of a contest, where all submissions are shown as pending (instead of accepted or rejected). The standings of the contest remain frozen until the end, and all teams watch the changes in the standing together, from the bottom to the top. If you pass a problem, your team will move up to a new position and this process repeats until all pending submissions are resolved. You don't know your final rank until the end, which is so exciting.
Previously, I competed in ICPC contests in China, where more than four hundred teams were in a big stadium programming together. However, here in NENA, only ten teams shared the same site. Though there were fewer teams, I could still feel the intensity in the air. When other teams passed a problem, their excitement was broadcast across the room. Fortunately, MIT and Harvard were not at our site, so we were always the leading team out of all ten teams there, and we felt less pressure.
One of the most challenging problems from the problem set was Problem L, a hard graph theory problem. Out of all eighty-four teams, only five passed it, and luckily we were one of them. We completed it in the last ten minutes of the contest, enabling us to go to NAC. When we were done, we celebrated and clapped like we were on top of the world. Watching the live boarding after the ending of the contest was difficult for us, as we only ranked in the top ten in the first four hours, and there was little possibility for us to advance to NAC. Luckily, the two problems we passed in the end sent us to rank sixth in the standings (only behind three MIT teams and two Harvard teams) and gave us the ticket to NAC.”
“We are the team Bearly Made It that has earned our ticket to the North America Championship (NAC). The team consists of three first-year graduate students and ICPC veterans from the CS department, Zhang Bin, Zhang Yiwei, and Lei Yuqi, and was coached by Prof. Yu Cheng. We understand that Northeast North America is a strong region, and only four universities will leave with tickets to NAC. Nonetheless, we have always believed that we are one of the best teams on the contest floor, and we are not hopeless against anyone else, even the formidable MIT teams from this region.
However, the contest did not go as smoothly as we had expected. We were trailing after the first thirty minutes and had around five universities ahead of us, even after three and a half hours. We entered the final hour with seven solves and a huge penalty, and we needed to get two more solves in order to advance to NAC. We fixed our solution to a problem shortly after the scoreboard froze and decided to trust our instincts and start fresh on a problem that seemed to be harder in the final 30 minutes. We worked out the solution sketches, implemented the idea, debugged the solution, fixed a typo, submitted it to the judging system, and prayed for the best. We could not afford to miss this one, and fortunately, we made it! At minute 292, only eight minutes from the end of the contest, we solved our ninth problem and moved up to sixth place (and third place in terms of institutions). It feels good to compete against strong teams and even better to send them home! :)
We would like to thank Prof. Cheng for his coaching and for going to the contest site with us. We would like to thank Brown CS for sponsoring us for this event and for being supportive of competitive programming in general. We would also like to use this opportunity to express our love for the local competitive programming community at Brown. Despite being small in size, everyone we met is talented and committed to this activity.”
For more information, click the link that follows to contact Brown CS Communications Manager Jesse C. Polhemus.