麻省理工学院 | 麻省理工学院赢得第45届国际大学生编程大赛世界总决赛

第一届ICPC世界总决赛于1977年举行，第二届(1978年)由麻省理工学院获得冠军，随后来自剑桥的队伍在许多年里险胜。该队教员赞助商、麻省理工学院电气工程与计算机科学系(EECS)计算机科学与工程教授马丁·里纳德(Martin Rinard)说，自从他1997年接管该队以来，该队已经多次接近胜利。其中包括五枚金牌、五枚银牌、三枚铜牌和两枚亚军。但他认为这次表演特别特别。

赢得冠军得益于许多人的努力，包括高级行政助理Mary McDavitt，她处理了派遣一支本科生团队穿越半个地球的艰巨后勤工作，以及学生教练Ce Jin和Yinzhan Xu，他们都是EECS的博士生，他们帮助选择了代表麻省理工学院的最佳团队。这个团队由小毛21孟' 22组成，他拥有计算机科学、工程和数学学位;以及计算机科学与工程专业大三学生邓明阳(Mingyang Deng)。(邓超最近还参加了ICPC的2022年北美锦标赛，并获得了冠军，获得了参加明年第46届ICPC世界总决赛的资格。)

在这次通过电子邮件进行的采访中，三人回顾了他们的历史性胜利。采访是在从孟加拉国飞回来的途中和之后进行的。

问:首先，恭喜你!告诉我们你是如何进入到竞争的心理空间的。对于这种激烈的、竞争激烈的脑力劳动，你推荐什么样的练习、仪式和准备习惯呢?

作为一个团队，我们在比赛前的几个月里进行了多次测试，以消除紧张情绪，为真正的比赛制定例行程序。

小毛:我们每周进行几次训练，但都不是最理想的，因为我已经毕业了，在另一个城市。我们必须通过Zoom进行交流，通过交流模拟“一个键盘”的环境。然而，这些困难在某种程度上是塞翁失马焉知非福，因为它们迫使我们提高沟通技巧，改进策略。

问:从后勤的角度来看，你是如何在这样的比赛中分配编程工作的?

对于大多数问题，最具挑战性的部分是提出解决方案的想法，而编程只是把它写下来的一种方法。这就是为什么我们的团队合作建立在寻找创意的基础上;有时我们每个人对一个问题都有部分想法，当我们讨论它们时，我们发现它们结合在一起形成了一个完整的解决方案。

小毛:因为只有一个键盘，我们必须在不同的编码员之间交替使用。当一个人在编码时，另外两个人可以互相检查对方的解决方案。我们一开始采用的策略是一个人负责编码，另一个人负责思考，但我们很快就放弃了这种策略，因为我们意识到，如果一直不停地做一件事，我们很容易感到疲劳。

一些最具挑战性的问题可能会将这些组合在一起，这时我们的团队才能发挥最大的作用。

问:你在12个问题中得到了4个第一次解决!速度是你策略中有意为之的一部分吗?

邓明阳:我们的目标不是速度。然而，尽管大多数团队遵循排行榜，我们的团队更喜欢探索新问题。结果，我们率先解决了许多未被探索的问题。

在排行榜上，解决问题更快的团队排名更高，所以速度是最重要的。

小毛:我们从两个不受欢迎的问题开始着手，而不是大多数团队都在解决的问题，这就是我们最初解决的两个问题的原因。此外，我们更关注正确性而不是速度，因为不正确的解决方案可能会浪费大量时间。我们在编码员和交叉检查解决方案之间交替使用的策略确保机器上没有“空闲时间”(即没有人编码的时间)，并且我们也不会有错误的解决方案。尽管别人对我们寄予了很高的期望，但我们带着“只是为了好玩”的心态参加比赛，并没有什么目标。获得第一名对我们来说当然是一个惊喜。

问:看一下最终的记分牌，很明显被称为“画廊守护者”的问题D是最具挑战性的问题。虽然许多团队都尝试过，你也勇敢地尝试了19次，但没有人正确地解决了它。D问题为什么会给大家带来这么大的麻烦?

D题是一个看似简单却异常复杂的几何问题——让它更难的是，不精确无处不在。问题的概念很简单:美术馆里有个警卫，一件珍贵的雕塑就会响警报。美术馆的形状很奇怪，所以雕塑可能不在警卫的视线之内。你能计算出他们要多快才能跑到某个地方去看吗?

让这个问题变得棘手的是，一些画廊的墙壁之间会有极小的缝隙，根据形状的不同，守卫有时可以透过缝隙看到东西。如何处理这些微小的碎片是大多数尝试这个问题的团队失败的原因。

小毛:挑战的部分是所有棘手的边缘情况和精度问题。想想电子游戏中物理引擎的所有故障!虽然我们确实修复了很多bug，但19次尝试中的大多数都是“万幸的尝试”，我们只是尝试不同的参数，希望其中一个能够通过。

虽然我们在比赛中有一个解决问题的清晰路径，但我们没有足够的时间来达成完整的解决方案。

问:就个人而言，你有“最喜欢”的问题吗?

小毛:第一个问题对我们来说是一个特别有趣的经历。它使用一种最常见的数据结构，称为“段树”。我们的解决方案以一种非常非常规的方式借用了一种称为“惰性传播”的技术。

邓明阳:我特别喜欢e题。这是一个魔术的问题，一个仆人帮助魔术师猜一张隐藏的牌。这个话题本身就很有趣;此外，巧妙的数学直觉参与了精确建模的技巧。我发现建模部分具有挑战性和令人兴奋。

几何问题通常被认为是所有编程竞赛的根源，因为它们带来了独特的障碍:就像你放大的越多，图片就会变得越模糊，这种“模糊”或“不精确”会让很多正确的想法难以在代码中表达。然而，发现一个只处理数字的计算机程序如何与一幅图像(如几何图形)连接起来是有一定的美感的。事实上，正是在这种联系下，数学中最优美的结果变得相关起来。

问:达卡离剑桥很远。描述一下你在这个城市的经历。

毛杰瑞:这是一个熙熙攘攘的城市:到处都是人、车和人力车。我们没有离开我们的住处走太远，因为我们知道我们会被困在交通堵塞中。ICPC的标志也遍布整个城市，包括机场、道路，甚至公共交通工具上——世界总决赛无疑是这座城市的一件大事。

肖:在我们停留期间，我没有体验到最好的交通状况，但我仍然喜欢这个城市的许多东西和它的好客!食物也很棒，准备食物的人也很棒。

邓明阳:我没有时间参观很多景点，但我在城市里逛了一下，和当地的青少年聊了很多。达卡存在着巨大而明显的贫富差距。年轻人意识到了这一点，希望他们能用自己的知识创造更好的未来。

问:在里纳德教授分享的这段YouTube视频中，你们被宣布为世界冠军金牌获得者，并被叫上台领取奖杯。在这个特殊的时刻你在想什么，有什么感觉?

邓明阳:太棒了。当这一切发生时，我感到不真实。许多强队参加了比赛，但我们出色的表现使我们名列前茅。Xiao和Jerry是很棒的队友，我很享受和他们在一起的时光。

小毛:这次比赛是我的告别演出，结束了我从五年级开始十多年的竞技性编程生涯。在舞台上，我很高兴它以一个高的结果结束，我能够报复我在国际奥林匹克信息学(IOI) 2017年的灾难性表现。我也感谢所有让这一切成为可能的人，特别是我的两个队友，明阳和杰瑞。

ICPC是世界上历史最悠久、规模最大、最负盛名的编程竞赛。能够有机会参加世界总决赛已经是一种巨大的荣誉;成为奖牌得主是不平凡的;成为世界冠军队伍，代表麻省理工学院把奖杯带回家，这是一个梦想成真。