A Satisfying Solve

On November 10^th, MIT’s team of crack coders made history by winning the globe’s oldest, largest, and most prestigious programming contest—the World Finals of the International Collegiate Programming Contest (ICPC). Held in Dhaka, Bangladesh, the 45^th World Finals drew a live audience of over 1600 viewers to the tense 12-problem competition, which featured 420 contestants, representing 140 universities across 45 nations.

The first ICPC World Finals contest was held in 1977, and the second (in 1978) was won by MIT—followed by many, many years of close misses for the team from Cambridge. “We have recently come close with very strong teams, and at times it felt like we might never make it,” said faculty coordinator Martin Rinard, Professor of CS and Engineering within MIT’s Department of Electrical Engineering and Computer Science. “Since I took over the team in 1997, we have won 5 gold medals, 5 silver medals, and 3 bronze medals. We have come in second three times. Overall, it’s a very good record, but it also feels great to finally win!”

That win was the work of many, including admin Mary McDavitt, who dealt with the daunting logistics involved in sending a team of undergraduates halfway around the world, and student coaches Ce Jin and Yinzhan Xu, both PhD students in EECS, who help select the best team to represent MIT. “In addition to the official regional contests held by ICPC, we also organize two selection contests every year especially for MIT students,” says student coach Ce Jin. “MIT students are usually extremely talented, and most of them are already experienced competitive programmers even before joining MIT. For example, the three members on this team all won medals at IOI (International Olympiad in Informatics) during high school!” That team is composed of Xiao Mao ’21 MEng ’22, who has degrees in both computer science and engineering and in mathematics; Jerry Mao, a senior in computer science and engineering; and Mingyang Deng, a junior in computer science and engineering. (Deng also recently competed in and won the 2022 North American Championships of the ICPC, clinching eligibility to attend the 46th annual ICPC World Finals next year.)

In this interview, conducted via email during and immediately after the flight back from Bangladesh, the trio reflected on their historical victory.

First off, congratulations on this incredible win. Tell me a little about how you got in the mental space to compete. What kinds of practices, rituals, and preparation habits do you recommend for this kind of intense, competitive brain work? 

Jerry: The ICPC is certainly intense—and unlike some other programming competitions, in the ICPC there is no such thing as partial credit! As a team, we did many test runs over the months leading to the competition, to iron out those nerves and develop a routine for the real thing.

Xiao: We ran several weekly practice sessions, but they were not optimal, since I 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 somewhat of a blessing in disguise, since they forced us to sharpen our communication skills and improve our strategies. 

Dhaka is a long way from Cambridge! Tell us about your experience of the city.

Jerry Mao: It’s a bustling city: there are people and cars and rickshaws everywhere. We didn’t go too far from where we were staying, because we knew we’d get stuck in the gridlock. ICPC signs were also everywhere around the city, including in the airport, on the roads, and even on the public transport—the world finals were definitely a major event for the city.

Xiao Mao: I did not experience the best traffic situation during our stay, but I still liked the city for many of its offerings and its hospitality! The food was also amazing and so were the people that prepared it. 

Jerry: I certainly enjoyed sampling the tastes, such as a mutton bhuna or a vegetable bhaji.

Mingyang Deng: I didn’t have time to visit many of the sights, but I wandered around the city a bit and had lots of conversations with local teenagers. Dhaka has a vast, visible wealth gap. The young people are aware of this, and hopefully, they can make a better future with their knowledge. 

Many folks may never have seen a programming competition before. Just from a logistical perspective, how do you divide up the work of programming? Is the fastest typist the person who gets the keyboard? Do all three work on separate possible solutions and compare? 

Jerry: All three of us are very experienced competitive programmers, so thankfully typing speed is not something we have to worry about. For most problems, the most challenging part is coming up with the idea of the solution, while programming is just a way to write it down. That’s why our teamwork is built on collaborating to find ideas; there are times when we’d each have partial ideas on a problem, and when we discuss them, we discover that they combine to a full solution.

Xiao: As there was only one keyboard, we had to alternate between coders. When one person was coding, the other two could cross-check each other’s solution. We actually started with some strategy where one person did all the coding and the other did all the thinking, but we quickly abandoned it since we realized we could easily get tired if we kept doing one thing without a break.

Jerry: We each have our own individual strengths, whether that be math, geometry, data structures, or something else. Some of the most challenging problems may pull together a combination of these, and that’s when our teamwork is able to shine the most.

You got four first-solves out of twelve problems! Was speed a deliberate part of your strategy? 

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

Jerry: While we weren’t specifically aiming for first-solves, there are 12 problems to work on, but only 5 hours. And on the leaderboard, teams that solve more problems faster are ranked higher, so speed is of utmost importance.

Xiao: We started on two unpopular problems instead of the one most of the teams were solving, and that was what contributed to two of our first-solves. Moreover, we focused more on correctness than speed, since an incorrect solution could waste a lot of time. Our strategy of alternating between coders and cross-checking solutions made sure that there was no “idle time” on the machine (i.e. time when no one was coding) and that we also never had incorrect solutions. Despite the expectations other people have put on us, we came into the competition with a “just for fun” mindset, and were not aiming for anything. Being first was certainly a surprise for us. 

Looking at the final scoreboard, it’s evident that Problem D, called “Guardians of the Gallery”, was the most challenging problem. While many teams attempted it, and you gave it a valiant 19 tries, no one solved it correctly. What was it about Problem D that gave everyone such trouble? 

Jerry: 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’s a guard in an art gallery, and an alarm goes off for a treasured sculpture. Art galleries are oddly-shaped, so the sculpture might not be in the guard’s line of sight–can you calculate how quickly they can run somewhere to see it?

What made this problem tricky was that some galleries would have walls with the tiniest sliver of a gap between them, and depending on the shape, the guard would sometimes be able to see through that gap. Figuring out what to do with these tiny slivers is what caused most teams who tried this problem to stumble.

Xiao: The challenging part of it was all the tricky edge cases and precision issues. Think about all the glitches in any physics engine in video games! Although we did fix a lot of bugs, most of the 19 attempts were “Hail Mary” attempts where we simply tried different parameters in hope that one of them would pass.

Jerry: I solved problem D this afternoon after getting off the plane back to Boston — unfortunately a bit late, but a satisfying solve nonetheless! While we had a clear path to solving the problem during the contest, we didn’t have enough time to reach the full and complete solution.

Individually, did you have a “favorite” problem?

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

Mingyang: I especially liked problem E. It’s a problem related to a magic trick in which a servant helps the magician guess a hidden card. The topic is interesting on its own; moreover, clever mathematical intuition is involved in modeling the trick precisely. I found the modeling part challenging and exciting.

Jerry: My favorite problems are about geometry. Geometry problems are often considered the bane of all programming contests due to the unique obstacles they bring: just like how a picture gets blurry the more you zoom in, this “blurriness” or “imprecision” can make a lot of correct ideas hard to express in code. However, there is a certain beauty to discovering how a computer program, which works with just numbers, can connect with a picture, such as a geometric diagram. In fact, it is in this connection that the most elegant results in mathematics become related.

In this YouTube clip, shared by Prof. Rinard, you’re being announced as the World Champion Gold Medalists and called up to the stage to receive your trophies. Can you tell us a little about what you were thinking about and feeling at this particular moment? 

Mingyang: It was awesome. I felt unreal when this happened. Many strong teams participated, but our excellent performance placed us at the top. Xiao and Jerry are amazing teammates, and I enjoyed the time spent with them.

Xiao: This competition was my swan song performance concluding my more-than-a-decade-long competitive programming career starting from the 5th grade. On the stage, I was very happy that it ended on a high note, and I was able to avenge my disastrous performance at International Olympiad in Informatics (IOI) 2017. I was also grateful for all the people who made this possible, especially my two teammates, Mingyang and Jerry.

Jerry: We’ve all been medalists on the world stage before at international contests, but this was an entirely different feeling. The ICPC is the oldest, largest, and most prestigious programming contest in the world. To have 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 bringing the trophy home, is a dream come true.