On Nov. 10, MIT’s team of student 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 45th world finals drew a live audience of over 1,600 viewers to the tense 12-problem competition, which featured 420 contestants representing 140 universities across 45 nations.
The first ICPC World Finals 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. Team faculty sponsor Martin Rinard, professor of computer science and engineering in MIT’s Department of Electrical Engineering and Computer Science (EECS) says that the team has come close to winning numerous times since he took over leadership of the team in 1997. That includes five gold medals, five silver medals, three bronze medals and two second-place finishes. But he considers this performance particularly special.
Winning the championship resulted from the work of many, including Senior Administrative Assistant Mary McDavitt, who dealt with the daunting logistics involved in sending a team of undergraduates halfway around 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. 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 reflect on their historic victory.
Q: First off, congratulations! Tell us 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 Mao: 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 Mao: 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.
Q: From a logistical perspective, how do you divide up the work of programming in a competition like this?
Jerry Mao: 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 Mao: 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 Mao: 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.
Q: You got four first-solves out of 12! Was speed a deliberate part of your strategy?
Mingyang Deng: We didn't aim for speed. However, while most teams follow the leader board, our team prefers to explore new problems. As a result, we were the first to solve many unexplored problems.
Jerry Mao: While we weren't specifically aiming for first-solves, there are 12 problems to work on, but only five hours. And on the leader board, teams that solve more problems faster are ranked higher, so speed is of utmost importance.
Xiao Mao: 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.
Q: 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 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'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 Mao: 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 Mao: 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.
Q: Individually, did you have a “favorite” problem?
Xiao Mao: 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 Deng: 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 Mao: 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.
Q: Dhaka is a long way from Cambridge. Describe 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: 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 Mao: 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.
Q: In this YouTube clip, shared by Professor Rinard, you’re being announced as the world champion gold medalists and called up to the stage to receive your trophies. What you were thinking about and feeling at this particular moment?
Mingyang Deng: 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 Mao: This competition was my swan song performance, concluding my more-than-a-decade-long competitive programming career starting from the fifth 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 Mao: 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.
de MIT News https://ift.tt/3rj6oVP
No hay comentarios:
Publicar un comentario