MIT Wins Global Final of 45th International College Programming Competition

MIT Wins Global Final of 45th International College Programming Competition

On November 10, MIT’s team of student coders made history by winning the world’s oldest, largest, and most prestigious programming contest, the International Collegiate Programming Contest (ICPC ). Held in Dhaka, Bangladesh, the 45th World Final drew a live audience of over 1,600 viewers for the tense 12-issue competition, which featured 420 contestants representing 140 universities from 45 countries.

The first ICPC World Final was in 1977, and the second (in 1978) was won by MIT – followed by many, many years of failures for the Cambridge team. The team’s faculty sponsor, Martin Rinard, professor of computer science and engineering in MIT’s Department of Electrical Engineering and Computer Science (EECS), says the team has come close to winning several times since he took charge of the team in 1997. This includes five gold medals, five silver medals, three bronze medals and two second places. But he considers this performance particularly special.

Winning the championship is the result of the work of many people, including Senior Administrative Assistant Mary McDavitt, who handled the daunting logistics involved in sending a team of undergraduates to the other end. of the world, as well as student coaches Ce Jin and Yinzhan Xu, both PhD students in EECS, who helped select the best team to represent MIT. This team is composed of Xiao Mao ’21 MEng ’22, who graduated in computer science and engineering and mathematics; Jerry Mao, graduate in computer science and engineering; and Mingyang Deng, a computer science and engineering junior. (Deng also recently competed in and won the 2022 CIPH North American Championships, earning her eligibility for the 46th Annual CIPH World Finals next year.)

In this interview, conducted by email during and immediately after the return flight from Bangladesh, the trio reflects on their historic victory.

Q: First of all, congratulations! Tell us how you got into mental space to compete. What kinds of preparation practices, rituals, and habits do you recommend for this kind of intense, competitive brain work?

Jerry Mao: CIPC is certainly intense – and unlike other programming contests, in CIPC there is no partial credit! As a team, we did a lot of testing in the months leading up to the competition, to iron out those nerves and develop a routine for the real thing.

XiaoMao: We organized several weekly training sessions, but they were not optimal, because I had already graduated and was in another city. We had to communicate via Zoom and emulate the “one keyboard” environment via communication. However, these difficulties were something of a blessing in disguise, as they forced us to sharpen our communication skills and improve our strategies.

Q: From a logistical point of view, how is the programming work divided up in a contest like this?

Jerry Mao: The three of us are very experienced competitive programmers, so luckily typing speed isn’t something we need to worry about. For most problems, the hardest part is coming up with the idea for the solution, while programming is just a way to write it down. This is why our teamwork relies on collaboration to come up with ideas; there are times when we each have partial ideas about a problem, and when we discuss them, we discover that they combine into a complete solution.

XiaoMao: Since there was only one keyboard, we had to alternate between encoders. When one person was coding, the other two could cross-check the other’s solution. We actually started out with a strategy where one person did all the coding and the other did all the thinking, but we quickly abandoned that because we realized we could easily get tired if we kept doing one thing non-stop.

Jerry Mao: We each have our own individual strengths, whether it’s math, geometry, data structures, or something else entirely. Some of the toughest problems can bring together a combination of these, and that’s where our teamwork is most effective.

Q: You have four first resolutions out of 12! Was speed deliberately part of your strategy?

Mingyang Deng: We didn’t aim for speed. However, while most teams follow the leaderboard, our team prefers to explore new issues. As a result, we were the first to solve many unexplored problems.

Jerry Mao: While we’re not specifically aiming for early resolutions, there are 12 problems to solve, but only five hours. And in the standings, teams that solve more problems faster are ranked higher, so speed is of the utmost importance.

XiaoMao: We started with two unpopular issues instead of the one most teams were solving, and that contributed to two of our early resolutions. Also, we focused more on accuracy than speed, because an incorrect solution could waste a lot of time. Our strategy of alternating between coders and cross-checking solutions ensured that there was no “idle time” on the machine (i.e. time when no one was coding ) and that we also never have incorrect solutions. Despite the expectations others placed on us, we entered the competition with a “just for fun” mindset and we were aiming for nothing. Being first was certainly a surprise for us.

Q: Looking at the final scoreboard, it’s obvious that problem D, called “Guardians of the Gallery”, was the hardest problem. While many teams attempted it, and you gave it 19 valiant tries, no one solved it correctly. What was it about problem D that was causing everyone so much trouble?

Jerry Mao: Problem D was a deceptively simple but exceptionally tricky geometry problem – and to make it harder, imprecision was everywhere. The concept of the problem was simple: there is a guard in an art gallery and an alarm goes off for a precious sculpture. The art galleries are oddly shaped, so the sculpture may not be in the guard’s line of sight. Can you calculate how fast they can run somewhere to see it?

What made this tricky was that some galleries had walls with the smallest gap between them, and depending on the shape, the guard could sometimes see through that gap. Figuring out what to do with those tiny shards is what has tripped up most teams that have tried this glitch.

XiaoMao: The hard part was all the tricky cases and accuracy issues. Think of all the bugs in any physics engine in video games! Although we fixed many bugs, most of the 19 attempts were “Hail Mary” attempts where we simply tried different settings in the hope that one would pass.

Jerry Mao: I solved problem D this afternoon after getting off the plane for Boston — unfortunately a bit late, but a satisfying solution nonetheless! Although we had a clear path to solve the problem during the contest, we did not have enough time to reach the full and complete solution.

Q: Individually, did you have a “favorite” problem?

XiaoMao: Problem, I was a particularly fun experience for us. It uses one of the most common data structures called a “segment tree”. Our solution borrowed a technique called “lazy propagation” in a very unconventional way.

Mingyang Deng: I especially liked problem E. It’s a magic trick problem in which a minion helps the magician guess a hidden card. The subject is interesting in itself; moreover, intelligent mathematical intuition is involved in the precise modeling of the trick. I found the modeling part challenging and exciting.

Jerry Mao: My favorite problems concern geometry. Geometry issues are often considered the bane of all programming contests because of the unique obstacles they bring: much like how an image blurs as you zoom in, that “blur” or ” vagueness” can make many correct ideas difficult to understand. express in code. However, there is a certain beauty in discovering how a computer program, which only works with numbers, can connect with an image, such as a geometric diagram. In fact, it is in this respect that the most elegant results in mathematics become linked.

Q: Dhaka is far from Cambridge. Describe your experience of the city.

Jerry Mao: It’s a bustling city: there are people, cars and rickshaws everywhere. We didn’t go too far from where we were staying, as we knew we would be stuck in traffic. ICPC signs were also all over the city, including at the airport, on the roads and even on public transport – the World Finals were definitely a major event for the city.

Xiao: I didn’t experience the best traffic situation during our stay, but I still liked the city for its many offers and hospitality! The food was also amazing as were the people who prepared it.

Jerry Mao: I certainly enjoyed tasting the tastes, like a mutton bhuna or a vegetable bhaji.

Mingyang Deng: Didn’t have time to see many sites, but wandered around town a bit and had lots of conversations with local teenagers. Dhaka has a vast visible wealth gap. Young people are aware of this and hopefully they can build a better future with their knowledge.

Q: In this YouTube clip, shared by Professor Rinard, you are announced as the world champion gold medalists and called to the stage to receive your trophies. What were you thinking and feeling at that exact moment?

Mingyang Deng: It was awesome. I felt unreal when it happened. Many strong teams participated, but our excellent performances put us at the top. Xiao and Jerry are amazing teammates and I enjoyed my time with them.

XiaoMao: This contest was my swansong performance, concluding my decade-plus competitive programming career starting in fifth grade. On stage, I was very happy that it ended on a high note and I was able to avenge my disastrous performance at the 2017 International Olympiad in Computing (IOI). I was also grateful to all the people who made this possible, especially my two teammates, Mingyang and Jerry.

Jerry Mao: We’ve all been medalists on the world stage at international competitions before, but it was a completely different feeling. The ICPC is the oldest, largest and most prestigious programming competition in the world. Having the opportunity to compete in the World Finals is already a great honor; to become a medalist is extraordinary; and to be the world champion team, representing MIT and taking home the trophy, is a dream come true.

#MIT #Wins #Global #Final #45th #International #College #Programming #Competition

Leave a Comment

Your email address will not be published. Required fields are marked *