麻省理工學(xué)院 | 麻省理工學(xué)院贏得第45屆國(guó)際大學(xué)生編程大賽世界總決賽
指南者留學(xué)
2022-11-17 21:53:48
閱讀量:1300
<p><img src="https://info.compassedu.hk/sucai/content/1668693590640/1668693590640.jpg" width="808" height="539" /></p>
<p>11月10日,麻省理工學(xué)院的學(xué)生編程團(tuán)隊(duì)創(chuàng)造了歷史,他們贏得了全球最古老、規(guī)模最大、最負(fù)盛名的編程競(jìng)賽——國(guó)際大學(xué)生編程大賽(ICPC)的世界總決賽。在孟加拉國(guó)達(dá)卡舉行的第45屆世界總決賽吸引了1600多名現(xiàn)場(chǎng)觀眾,共有來(lái)自45個(gè)國(guó)家140所大學(xué)的420名選手參加了12個(gè)問(wèn)題的緊張比賽。</p>
<p> </p>
<p>第一屆ICPC世界總決賽于1977年舉行,第二屆(1978年)由麻省理工學(xué)院獲得冠軍,隨后來(lái)自劍橋的隊(duì)伍在許多年里險(xiǎn)勝。該隊(duì)教員贊助商、麻省理工學(xué)院電氣工程與計(jì)算機(jī)科學(xué)系(EECS)計(jì)算機(jī)科學(xué)與工程教授馬丁·里納德(Martin Rinard)說(shuō),自從他1997年接管該隊(duì)以來(lái),該隊(duì)已經(jīng)多次接近勝利。其中包括五枚金牌、五枚銀牌、三枚銅牌和兩枚亞軍。但他認(rèn)為這次表演特別特別。</p>
<p> </p>
<p>贏得冠軍得益于許多人的努力,包括高級(jí)行政助理Mary McDavitt,她處理了派遣一支本科生團(tuán)隊(duì)穿越半個(gè)地球的艱巨后勤工作,以及學(xué)生教練Ce Jin和Yinzhan Xu,他們都是EECS的博士生,他們幫助選擇了代表麻省理工學(xué)院的最佳團(tuán)隊(duì)。這個(gè)團(tuán)隊(duì)由小毛21孟' 22組成,他擁有計(jì)算機(jī)科學(xué)、工程和數(shù)學(xué)學(xué)位;以及計(jì)算機(jī)科學(xué)與工程專(zhuān)業(yè)大三學(xué)生鄧明陽(yáng)(Mingyang Deng)。(鄧超最近還參加了ICPC的2022年北美錦標(biāo)賽,并獲得了冠軍,獲得了參加明年第46屆ICPC世界總決賽的資格。)</p>
<p> </p>
<p>在這次通過(guò)電子郵件進(jìn)行的采訪中,三人回顧了他們的歷史性勝利。采訪是在從孟加拉國(guó)飛回來(lái)的途中和之后進(jìn)行的。</p>
<p> </p>
<p>問(wèn):首先,恭喜你!告訴我們你是如何進(jìn)入到競(jìng)爭(zhēng)的心理空間的。對(duì)于這種激烈的、競(jìng)爭(zhēng)激烈的腦力勞動(dòng),你推薦什么樣的練習(xí)、儀式和準(zhǔn)備習(xí)慣呢?</p>
<p> </p>
<p>作為一個(gè)團(tuán)隊(duì),我們?cè)诒荣惽暗膸讉€(gè)月里進(jìn)行了多次測(cè)試,以消除緊張情緒,為真正的比賽制定例行程序。</p>
<p> </p>
<p>小毛:我們每周進(jìn)行幾次訓(xùn)練,但都不是最理想的,因?yàn)槲乙呀?jīng)畢業(yè)了,在另一個(gè)城市。我們必須通過(guò)Zoom進(jìn)行交流,通過(guò)交流模擬“一個(gè)鍵盤(pán)”的環(huán)境。然而,這些困難在某種程度上是塞翁失馬焉知非福,因?yàn)樗鼈兤仁刮覀兲岣邷贤记?,改進(jìn)策略。</p>
<p> </p>
<p>問(wèn):從后勤的角度來(lái)看,你是如何在這樣的比賽中分配編程工作的?</p>
<p> </p>
<p>對(duì)于大多數(shù)問(wèn)題,最具挑戰(zhàn)性的部分是提出解決方案的想法,而編程只是把它寫(xiě)下來(lái)的一種方法。這就是為什么我們的團(tuán)隊(duì)合作建立在尋找創(chuàng)意的基礎(chǔ)上;有時(shí)我們每個(gè)人對(duì)一個(gè)問(wèn)題都有部分想法,當(dāng)我們討論它們時(shí),我們發(fā)現(xiàn)它們結(jié)合在一起形成了一個(gè)完整的解決方案。</p>
<p> </p>
<p>小毛:因?yàn)橹挥幸粋€(gè)鍵盤(pán),我們必須在不同的編碼員之間交替使用。當(dāng)一個(gè)人在編碼時(shí),另外兩個(gè)人可以互相檢查對(duì)方的解決方案。我們一開(kāi)始采用的策略是一個(gè)人負(fù)責(zé)編碼,另一個(gè)人負(fù)責(zé)思考,但我們很快就放棄了這種策略,因?yàn)槲覀円庾R(shí)到,如果一直不停地做一件事,我們很容易感到疲勞。</p>
<p> </p>
<p>一些最具挑戰(zhàn)性的問(wèn)題可能會(huì)將這些組合在一起,這時(shí)我們的團(tuán)隊(duì)才能發(fā)揮最大的作用。</p>
<p> </p>
<p>問(wèn):你在12個(gè)問(wèn)題中得到了4個(gè)第一次解決!速度是你策略中有意為之的一部分嗎?</p>
<p> </p>
<p>鄧明陽(yáng):我們的目標(biāo)不是速度。然而,盡管大多數(shù)團(tuán)隊(duì)遵循排行榜,我們的團(tuán)隊(duì)更喜歡探索新問(wèn)題。結(jié)果,我們率先解決了許多未被探索的問(wèn)題。</p>
<p> </p>
<p>在排行榜上,解決問(wèn)題更快的團(tuán)隊(duì)排名更高,所以速度是最重要的。</p>
<p> </p>
<p>小毛:我們從兩個(gè)不受歡迎的問(wèn)題開(kāi)始著手,而不是大多數(shù)團(tuán)隊(duì)都在解決的問(wèn)題,這就是我們最初解決的兩個(gè)問(wèn)題的原因。此外,我們更關(guān)注正確性而不是速度,因?yàn)椴徽_的解決方案可能會(huì)浪費(fèi)大量時(shí)間。我們?cè)诰幋a員和交叉檢查解決方案之間交替使用的策略確保機(jī)器上沒(méi)有“空閑時(shí)間”(即沒(méi)有人編碼的時(shí)間),并且我們也不會(huì)有錯(cuò)誤的解決方案。盡管別人對(duì)我們寄予了很高的期望,但我們帶著“只是為了好玩”的心態(tài)參加比賽,并沒(méi)有什么目標(biāo)。獲得第一名對(duì)我們來(lái)說(shuō)當(dāng)然是一個(gè)驚喜。</p>
<p> </p>
<p>問(wèn):看一下最終的記分牌,很明顯被稱(chēng)為“畫(huà)廊守護(hù)者”的問(wèn)題D是最具挑戰(zhàn)性的問(wèn)題。雖然許多團(tuán)隊(duì)都嘗試過(guò),你也勇敢地嘗試了19次,但沒(méi)有人正確地解決了它。D問(wèn)題為什么會(huì)給大家?guī)?lái)這么大的麻煩?</p>
<p> </p>
<p>D題是一個(gè)看似簡(jiǎn)單卻異常復(fù)雜的幾何問(wèn)題——讓它更難的是,不精確無(wú)處不在。問(wèn)題的概念很簡(jiǎn)單:美術(shù)館里有個(gè)警衛(wèi),一件珍貴的雕塑就會(huì)響警報(bào)。美術(shù)館的形狀很奇怪,所以雕塑可能不在警衛(wèi)的視線之內(nèi)。你能計(jì)算出他們要多快才能跑到某個(gè)地方去看嗎?</p>
<p> </p>
<p>讓這個(gè)問(wèn)題變得棘手的是,一些畫(huà)廊的墻壁之間會(huì)有極小的縫隙,根據(jù)形狀的不同,守衛(wèi)有時(shí)可以透過(guò)縫隙看到東西。如何處理這些微小的碎片是大多數(shù)嘗試這個(gè)問(wèn)題的團(tuán)隊(duì)失敗的原因。</p>
<p> </p>
<p>小毛:挑戰(zhàn)的部分是所有棘手的邊緣情況和精度問(wèn)題。想想電子游戲中物理引擎的所有故障!雖然我們確實(shí)修復(fù)了很多bug,但19次嘗試中的大多數(shù)都是“萬(wàn)幸的嘗試”,我們只是嘗試不同的參數(shù),希望其中一個(gè)能夠通過(guò)。</p>
<p> </p>
<p>雖然我們?cè)诒荣愔杏幸粋€(gè)解決問(wèn)題的清晰路徑,但我們沒(méi)有足夠的時(shí)間來(lái)達(dá)成完整的解決方案。</p>
<p> </p>
<p>問(wèn):就個(gè)人而言,你有“最喜歡”的問(wèn)題嗎?</p>
<p> </p>
<p>小毛:第一個(gè)問(wèn)題對(duì)我們來(lái)說(shuō)是一個(gè)特別有趣的經(jīng)歷。它使用一種最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu),稱(chēng)為“段樹(shù)”。我們的解決方案以一種非常非常規(guī)的方式借用了一種稱(chēng)為“惰性傳播”的技術(shù)。</p>
<p> </p>
<p>鄧明陽(yáng):我特別喜歡e題。這是一個(gè)魔術(shù)的問(wèn)題,一個(gè)仆人幫助魔術(shù)師猜一張隱藏的牌。這個(gè)話題本身就很有趣;此外,巧妙的數(shù)學(xué)直覺(jué)參與了精確建模的技巧。我發(fā)現(xiàn)建模部分具有挑戰(zhàn)性和令人興奮。</p>
<p> </p>
<p>幾何問(wèn)題通常被認(rèn)為是所有編程競(jìng)賽的根源,因?yàn)樗鼈儙?lái)了獨(dú)特的障礙:就像你放大的越多,圖片就會(huì)變得越模糊,這種“模糊”或“不精確”會(huì)讓很多正確的想法難以在代碼中表達(dá)。然而,發(fā)現(xiàn)一個(gè)只處理數(shù)字的計(jì)算機(jī)程序如何與一幅圖像(如幾何圖形)連接起來(lái)是有一定的美感的。事實(shí)上,正是在這種聯(lián)系下,數(shù)學(xué)中最優(yōu)美的結(jié)果變得相關(guān)起來(lái)。</p>
<p> </p>
<p> </p>
<p>問(wèn):達(dá)卡離劍橋很遠(yuǎn)。描述一下你在這個(gè)城市的經(jīng)歷。</p>
<p>毛杰瑞:這是一個(gè)熙熙攘攘的城市:到處都是人、車(chē)和人力車(chē)。我們沒(méi)有離開(kāi)我們的住處走太遠(yuǎn),因?yàn)槲覀冎牢覀儠?huì)被困在交通堵塞中。ICPC的標(biāo)志也遍布整個(gè)城市,包括機(jī)場(chǎng)、道路,甚至公共交通工具上——世界總決賽無(wú)疑是這座城市的一件大事。</p>
<p> </p>
<p>肖:在我們停留期間,我沒(méi)有體驗(yàn)到最好的交通狀況,但我仍然喜歡這個(gè)城市的許多東西和它的好客!食物也很棒,準(zhǔn)備食物的人也很棒。</p>
<p> </p>
<p>鄧明陽(yáng):我沒(méi)有時(shí)間參觀很多景點(diǎn),但我在城市里逛了一下,和當(dāng)?shù)氐那嗌倌炅牧撕芏唷__(dá)卡存在著巨大而明顯的貧富差距。年輕人意識(shí)到了這一點(diǎn),希望他們能用自己的知識(shí)創(chuàng)造更好的未來(lái)。</p>
<p> </p>
<p>問(wèn):在里納德教授分享的這段YouTube視頻中,你們被宣布為世界冠軍金牌獲得者,并被叫上臺(tái)領(lǐng)取獎(jiǎng)杯。在這個(gè)特殊的時(shí)刻你在想什么,有什么感覺(jué)?</p>
<p> </p>
<p>鄧明陽(yáng):太棒了。當(dāng)這一切發(fā)生時(shí),我感到不真實(shí)。許多強(qiáng)隊(duì)參加了比賽,但我們出色的表現(xiàn)使我們名列前茅。Xiao和Jerry是很棒的隊(duì)友,我很享受和他們?cè)谝黄鸬臅r(shí)光。</p>
<p> </p>
<p>小毛:這次比賽是我的告別演出,結(jié)束了我從五年級(jí)開(kāi)始十多年的競(jìng)技性編程生涯。在舞臺(tái)上,我很高興它以一個(gè)高的結(jié)果結(jié)束,我能夠報(bào)復(fù)我在國(guó)際奧林匹克信息學(xué)(IOI) 2017年的災(zāi)難性表現(xiàn)。我也感謝所有讓這一切成為可能的人,特別是我的兩個(gè)隊(duì)友,明陽(yáng)和杰瑞。</p>
<p> </p>
<p>ICPC是世界上歷史最悠久、規(guī)模最大、最負(fù)盛名的編程競(jìng)賽。能夠有機(jī)會(huì)參加世界總決賽已經(jīng)是一種巨大的榮譽(yù);成為獎(jiǎng)牌得主是不平凡的;成為世界冠軍隊(duì)伍,代表麻省理工學(xué)院把獎(jiǎng)杯帶回家,這是一個(gè)夢(mèng)想成真。</p>
<p> </p>
<blockquote>
<p>注:本文由院校官方新聞直譯,僅供參考,不代表指南者留學(xué)態(tài)度觀點(diǎn)。</p>
</blockquote>