ACM ICPC World Finals 2011 - Orlando 比賽過程 + 感想

拖了很久，越寫越長，但還是要發出來。比賽過程其實也不太記得清楚，都是看着不同時間的scoreboard回憶起來的。
Final scoreboard: http://cm.baylor.edu/scoreboard/

比賽前心情不算很緊張，只是又要在門口聽Bill叔叔說一大堆廢話。有practice contest的教訓，我和kn特地提醒CTLi比賽的時候專心想題目，有甚麼硬件或機器的問題由我和kn處理。

比賽一開始和平時訓練差不多，kn打code template，我拆題目和把題目分類。看到有坐標的題目便分給kn，發現kn分到了5題，當時卻沒有想過整份題目卻沒有甚麼需要geometry技巧。看到有隊過題K，kn一看便想到做法，立即上機很快便通過了題K。

23 min: Problem K - Simple Geometry (kn)

過K之後不久CTLi上機做G，大家都沒有想過這就是悲劇的開始。這時我看了題H和題D，題H暫時沒有想法，題D很有flow的味道，但暫時沒有想到可行的算法。看到兩題graph都不太懂做，這時有少許緊張。因為最害怕會發生的情況好像有機會發生：有難的graph題目而我不太懂做，kn和CTLi又不熟graph thoery。看看scoreboard我們發現清華過了題C，一看題目就很明顯是kn的類型(data processing + pattern recognition)。kn解明白題目後很快便想到去數空白部份數目的算法，他看清楚後覺得有信心便繼續去想題E。題E是類似打斜45度的正方形的partial sum，我想了想覺得很麻煩，雖然已經有隊過了這題但也沒有再想。回頭繼續研究我的題H。

CTLi的題G搞了很久都過不到sample，貌似是binary search時永遠到出了infinity。這時畫完sample出來後我已經想到題H的做法，就是找出leaf的biconnected component感覺還挺肯定是正確的。CTLi的題G又沒有甚麼進度，於是我便開始上機做題H。上機的途中也不是很順利，中途和CTLi交替了幾次上機和debug，kn也好像在中途開了很多隊已經過了的題C來做。這時比賽到60分鐘左右很多隊已經有三題，而很明顯我們的開局不太順利，但想起立志賽前說當年waterloo都是89分鐘才出第一道題而最後過了7題，又看見對面中山一題也沒有，我還是挺冷靜的。不久CTLi的題G終於通過sample，提交卻得到Wrong Answer(WA)。我的題H也很快過了sample，提交也是WA。這時候終於有機會給kn專心上題C。過了十分鐘發現沒有處理整個graph是一個biconnected component的情況，改完再交還是WA。又過了十幾分鐘kn的題C通過了sample提交也是WA，而CTLi的題G再改還是WA。我的題H幾本上絕望，看了很多次也找不到任何bug。我便轉看有不少隊通過了的題J和繼續想肯定是flow的題D。

kn的題C和CTLi的題G再交仍然是WA，於是我便問一下kn的狀況。他說他發現物件接觸到邊位時有機會會錯，想外加一層空格去處理。我想了想發現kn的方法會處理錯只有一件物件的情況，和kn討論一下得出解決方法。花了一些時間再改再錯多了一次便終於通過題C了。不過題G和題H的WA仍是沒有任何idea去解決。

109 min: Problem C - Flood Fill (kn; 3WA)

之後kn和CTLi討論一會兒後便想開始做題E。kn跟我說他的做法但我聽不明白，而我亦覺得他的做法很麻煩，不過他說他有信心便由得他去做了。CTLi的題G搞了搞還是過不到，而題A又開始有不少隊通過，於是我便叫CTLi研究題A。這時候我看完題J覺得規模很大沒有想法，便一邊看看題H又一邊再想想題D。過了不久kn的題E有bug而CTLi的題A好像想到做法，於是又開始交替地寫。在比賽150min左右(比賽時間的一半了)，kn通過了題E的sample，過了sample後好像有些慢，我建議kn將memset改為for loop去initialize。這時候我不知道kn在想甚麼，竟然落機和CTLi討論一大輪後想重寫。[這大概也是我們隊策略和teamwork的失誤，代表這也是我的錯誤] 心急的我很不滿地問他們甚麼情況，然後決定先交一下kn已經通過sample的program，結果得到Runtime Error。他們討論完後kn決定重寫，不久CTLi的題A也寫好通過sample了，在這個情況當然立即提交，得到WA。他們兩人寫了寫又要落機研究，而我又不想電腦空着，所以我便在這段時間開始寫題D的dinic武器。（這個時間我們隊是同時開了五題來做，絕對破了我們自己在任何比賽或training的紀錄）幸好，不久之後kn找到了題E的bug，改完通過sample再交，終於把這題過了。

171 min: Problem E - Coordinate Transform + Partial Sum (?) (kn; 1WA)

這時候我把題J的想法告訴kn，讓他準備用最簡單的DP頹做。我提出實際狀態可能很少，用vector之儲可達到的狀態可能可以大大加速，CTLi卻不太贊成。我也不理太多，認為有這麼多隊通過，算法必然很簡單，而我又找到頹greedy的反例。於是kn便看題目和準備preprocessing的地方。寫完dinic後過不到sample，改了改才發現我理解錯了題目，有一個重要的constraint一時想不到解決方法，唯有落機讓CTLi繼續改他的題A，我亦再看看我們沒有人看過的題I。經過幾次WA，CTLi還是穩住地把題A通過。

200 min: Problem A - Greedy (CTLi; 3WA)

CTLi：“well，終於有少少貢獻啦。”
Joe：“咁你即係話我無貢獻啦。”
CTLi：“well...”

CTLi過了A後，他認為kn的題J寫得有些問題，可能會比較慢，在CTLi不停口說很慢但我又聽不明白他的解決方法下，我便果斷決定讓CTLi接手做題J，然後讓kn幫我再看一次題H。kn看完題H認為我沒有看錯題，所以還是沒有idea錯甚麼，唯有找時間和kn討論我的題H。kn不太明白我的做法，當我解釋時突然就發現了自己的特別處理有問題。立即趕走CTLi搶機來改，這時我緊張得有些手震，改完交後傳來一個WA，淡定想起特別處理沒有用long long，立即再改再交，仍是WA，心情再次受到打擊。而我這時看scoreboard已經可以知道拿牌必定要7題，因此我們除了題J和題H外必須再過多一題。CTLi的題G好像已經放棄了，而kn說題B是簡單的暴力和幾何，於是我便叫kn開始準備去寫題B。不久，CTLi的題J已經寫完但過不到sample。這時其實好像大家腦筋也不太冷靜，在大家的協助和混亂下過了一段時間終於改好通過sample，提交後compile和run了很長時間終於過了我們的第五題。

231 min: Problem J - DP (kn + CTLi)

過了題J後，我說了題I的題意給大家聽，一致贊成立即放棄這題，然後我立即讓CTLi重新研究一開始過不到的題G。我的題H還是沒有頭緒，太沮喪的情況下搶過機來，測試我biconnected component的部份有沒有問題，然後好像發現有一些邊是從來沒有被分到任何一個biconnected component。[註：其實我的武器沒有問題，只是做checking的地方寫錯了] 這時我完全沒有信心去改正我這部份的code，於是想了另一個做法不需用biconnected component讓kn幫我重新寫一次。kn寫完後發現有問題，debug時驚訝地發現連n的數值也錯了。看一看code發現我找n的值時竟然寫了n=max(x,y)，而正確的應是n=max(n,max(x,y))。修改後kn寫的新版本還是錯，我修改我舊版本的code再交一次，終於得到了ACM生涯最悲劇的Accetped。

249 min: Problem H - Biconnected Component (Joe; 6WA)

過完題H終於到了6題趕上大隊，只要拚出多一題就大概能拿牌。最後50分鐘kn主力上題B，CTLi中途好像重新有idea錯甚麼，間中搶機改code再交。kn說題B很多細節怕看錯題目，叫我重新看一次題目。題目很長很煩，而我的精神和心情仍是很混亂的狀態，花了一段時間看明白題目，和kn討論後改正了他很多地方對題目的理解。到最後十五分鐘還有接近一半未寫好，預計之後還需要調試，而我又覺得kn某些地方的做法不正確，根本沒有可能完成，於是便叫kn放棄題B，轉而讓CTLi用機怒交題G。很可惜到最後我們的題G都是在WA和TLE之間始終過不到，比賽就始結束。

比賽完結後十分失望，頹坐在椅子或地上坐了很久，直至立志進來。他的印度朋友來恭喜我說我們表現很好，我都不知道怎樣答他。本來在隊中應是最需要穩定和提供支援的角色，到最終卻因為自己的低級失誤拖累了整隊的發揮。這也許是我唯一一次比完賽有想哭的感覺吧。這種失落比08年成都的灰心大很多很多。

---

雖然對整場比賽哪一隊領先哪一隊表現較好完全沒有感覺，但也覺得清華輸了很可惜，看到Michigan爬過清華的時候周冬他們的表情時，除了為自己的難過外也仿佛感受到他的難過。比賽前我心中的大熱是台大Warsaw和清華，但最後好像三隊的表現都不太滿意。最後冠亞軍竟然是爆大冷的浙大和Michigan，輸了給以前嬴過的對手感覺更差 (雖然自己和對手的隊友都已經完全不同)。

事後自我檢討我們這場比賽爭牌失敗(除了實力和運氣外)的原因和這場比賽做得不好的地方：

1. 比賽中第一個技術性失誤應該是kn的題E寫完後才和CTLi討論結果要重寫。中途由於我和CTLi的各自卡題導致kn要孤獨作戰而陷入一個很複雜的想法，事實上假如一早找CTLi談幾句的話這題應該會順利很多。
2. CTLi卡題G的時候我和kn從頭到尾都沒有幫手。比賽中途我理解題目後曾給CTLi建議試一試O(n^3)的簡單DP，但後來到我過題H前後也望過CTLi的code但感覺是我不可能理解的算法。我們完全也沒有意識去幫CTLi，某程度上都是因為CTLi沒有找我們幫手。不過回想起來，在訓練中好像沒有CTLi做不到的題目，而CTLi從來沒有主動找我們幫忙。事實這題目遠比我想像中簡單，而我相信我亦有在這題找出一些observation和幫忙CTLi debug的能力。
3. 最後一小時開題B的決定其實很值得商確。kn當時還是很沒有把握，題目有很多地方他也理解得不清楚，因此到後來需要作出很多修改。當時完全失去信心的我沒有意識到我題D的flow model已經是非常接近，事實上只要再加一層exhaustion就能完美解決我早前看錯的constraint而解決題目。假如我繼續去攻題D會否有更大機會過題？這永遠是一個謎。
4. 到比賽前的最後一星期，我似乎都未能把ManiAC的狀態調較到最好位置。出發前一星期做南韓regional時某程度上已嚴重反映狀態不足的問題，而當時我亦非常明白這個情況。之後來到Orlando做練習時大家還是有很多很多的卡題和無聊失誤，但無輪是出發前一星期或是出發後我也是沒有辦法解決這個問題。

到後來我總覺得這次比賽中team work和策略上做得很差，有很多決定都好像做得不夠好。比賽從最初選錯題和卡題開始，我們已失去了平時的節奏。大家在比賽中從頭到尾好像都沒有靜下來慢慢想題目的時間，這也是我們在最後一小時出不到題的其中一個原因。我們三人以往比賽經驗都未能令我們在最後關頭作出正確的決定。不過也許如果沒有以往比賽的經驗，我們隊早在同時卡五題的時候就崩沮了。


我們隊三人都是老隊員了，也都是第二次參加World Final。對於World Final上的一切事也不太覺得新奇，在比賽前幾天所有活動中都能很集中於比賽中。記得兩年前在瑞典看到Petr的時候還大驚小怪然後要和他合照，今年幾乎每天也看到Petr但已經沒有甚麼感覺了。從比賽角度上看，假如和上一次Stockholm的World Final比較，雖然同樣是悲劇，可能因為上一次的期望和信心不太大，而這次目標只有拿牌，而且真的因為自己的錯而拖累了隊友，所以失望的感覺非常大。比賽後亦沒有當年沒有懷念KTH library的氣氛和感覺，只記得自己在比賽時過題H之後崩沮地躺在地氈的感覺。

我們大概在World Final一年前組成ManiAC，也好像是香港中大ACM team有史以來第一隊三個人也是第二次入World Final的。隊友kn是主力coding的隊員，專長於幾何，搜索和模擬題。CTLi的coding較慢，但對數學和算法非常有信心，總能把複雜的DP和數學題解決，有時候對題目又可以有些很創新的解法(如Kuala Lumpur 2010最後一題的E)，對於幾何題有很多時候都能給出很有用的意見，是我們的皇牌武器。而我的特性就在兩人之間，比較特殊的能力可能就是做過類似的題目會很有印象吧。

由於我們的特性，比較容易的題目會多由kn去做，較難的題目會給CTLi去想，而我就卡在中間，主要去做些要花時間想但又不需要用到CTLi想的題目，和協助kn去做麻煩的題目。因此在較多的訓練後已經逐漸演變成我較少coding的情況。在訓練當中通常都是擔當支援的角色。除非有很多graph題，否則正常情況都是我用機時間+做題數量都是我最少的。

我們隊其中一個特點是絕對的信任隊友，就是在開始階段假如隊員說很有信心的時候通常都不會過問，直至提交後過不到。這個策略也許是我們這次比賽做得很差的原因，但我自己也沒有後悔的，因為想拿牌就要進取一點，這次運氣差賭輸了也沒有辦法。

我們這隊ManiAC是完全為了World Final而組成的。由於World Final要求的coding能力非常高，而歷年的試題中亦有很多幾何題。因此我們早在一年前訓練的時候已針對麻煩或是幾何的題目投放很多的時間去熟習，直至對這些題目有信心，而對算法的思考可能卻不是特別出眾(但也不弱)。可惜這次World Final的題目的題型卻是意料之外，連judge的其中一員Per也在他的題解說這份題目是“unusually geometry-free problem set”，因此其實我們特別為WF組成的隊型在這次比賽中發揮的空間不是太多。做這份題目，的確我們隊比起其他強隊沒有太大優勢。

---

寫完這篇總結，比賽已經過了差不多兩個星期，遺憾的感覺已經淡化了很多。不過每回想起來總覺得這次的表現實在是差得不能再差，做出6題其實完全沒有難度，即使只是中大以往幾年的一隊的能力都應該可以做到。最後我們的能力就只是用於挽救一連串不幸事件的危機，感覺有點可惜。

World Final已完，這樣就退役了，還有甚麼想說的就遲些在寫吧，退役文後補。