這個可能是近十年中大最有機會拿冠軍的regional，最後還是輸了，很失望。相信我們過H的時候應該中大的朋友都十分興奮，甚至可能有我們興奮程度的一半。除了中大的朋友，可能還有一眾花生友(http://twitter.com/thanhvy)和judges也應該這樣想吧。雖然已提供了精彩的比賽，可惜不能把餘下的做完，否則過了台大的話將是經典的一場反擊。
final scoreboard: http://competition.binus.ac.id/icpc/result/final.html
================================================================
比賽大會要求早上六時正乘車去大學，然後等到九點才比賽。這樣的時間大會解釋是因為改遲時間的話會大塞車，10分鐘的路程可能會需要1小時。就這樣，我們便一早起來去比賽的大學吃早餐，然後躺在三張椅子上睡覺，意外地這樣睡還睡得不錯。
比賽開始雖然有少許緊張，但還不算是太緊張。雖然沒有World Final的輕鬆心情，但至少比以往的regional比賽較為放鬆。一開題目先把全部題目掃一遍，看到題C是game，立即叫CTLi看。這時聽到kn 打template的keyboard聲音非常怪異，心知不妙。我再看A，題意很簡單，constant數目的input，想了想又想不到，但又覺得有可能是極簡單被秒殺的題目，再想還是想不到。CTLi這時開始上機做題C。我又發現kn好像看了很多題目，於是讓他解給我聽，是有關BST的input sequence的counting題目，暫時不懂，但相信不難。之後kn又解了I的題意給我聽，一聽便知道是NWERC 04 Problem E和HKOI2004 Junior Compeition一樣，就是greedy。算法也懶得和kn說，便說我可以做這題了。上機寫便立即感受到keyboard真的很爛。寫完過不到 sample，打印題目看，再看看題目發現沒有考慮A這種咭。等CTLi的C做完後便上去改，改完立即過sample。CTLi的C回來一個 Yes(24)。我也交了我的I，不久又回來另一個Yes(25)。之後kn可以上題D，他說是頹題，果然很快便寫好提交，得到第三個Yes(34)
中途解了A的題意給CTLi，他搞了一會兒好像有些頭緒。kn解題F給我聽，想一想覺得可以SCC縮點，然後再做DP應該可行(大錯特錯)。我發現台大己經秒殺了題E，我看看題目，好像有些難又或者要類似segment tree，硬着頭皮再想想又立即發現簡單的算法。在題D過了後便上機做E，做到中途有bug，找了一段時間都不明白，只好退下來給CTLi做題A。再研究了一會兒知道錯了甚麼，準備好改的時候CTLi又如火如茶，心急地等他寫完提交得到WA。我再上機把E完成，還是有點錯，原來有些麻煩地方沒有 handle好，唯有硬着頭皮再開一個數組特別處理，辛苦地搞完發現過了sample，提交興奮地得到第4個Yes(72)。我可以繼續做F，但kn這時候又可以做題J，他說是簡單題。本來我想先做題F，但看見他已經在紙上寫好code，便讓他先做。做到中途有嚴重的卡住，不知道錯甚麼。CTLi又可以修改他的A，這時他們交錯的做，kn發現打錯了variable名，過了sample後交，得到TLE。CTLi又可以交了，可惜改完卻又只得TLE。搞了一大段時間，CTLi終於把A暫時射雕Yes了!(123+2)。kn改過他的無聊錯鋘後很快又把題J過了(129+2)。這時我開始做F，我以為是 SCC縮點後DP的題目，中途聽kn說H的題意，亦把我在題B想到的observation說給CTLi聽。題F很快便寫好，提交卻得到WA。打印出來卻又找不到bug。
中途看到台大已經八題遙遙領先。在這時候我才開始有些擔心：我一直沒有擔心是因為好像還未做的題目都懂得做(我假設了CTLi會做到那題數字題目G)，但他們還有兩小時去做剩下的題目，很有機會可以把題目做完，這樣我們即使全清也不可能奪冠。在這時候 CTLi上B，雖然打得有少許慢，但還是穩住地把題目過了(152)。而我亦可以上題H，便便請kn幫我debug題F,最後還是要寫generator 去測試。當我交替寫H和kn trace我的program debug的時候，終於找到算法的錯誤。大家再想卻想不到修補的方法，絕望了一會兒後便決定由kn去頹做。頹做當然很快code完，提交竟然輕鬆得到 Yes(204)。看到Yes的一剎我不由自主地大叫了一聲，竟然在隔了一間房的chin也聽到這一下叫聲.....
而有關題H，我一聽便知道和NWERC 04 Problem A接近一模一樣, 就是經典的AC自動機+DP。kn又不能代我做題H，唯有我自己上, 打AC自動機的武器(又打武器了)。因為曾經做過的關係，有些第一次做會錯的地方都避免了，所以做的過程還算順利。但題目要撇除由0為開頭的 string，唯有另外再開一個類似的DP處理。之後過多了幾個sample，不過最後的還是過不到。搞了一段時間又發現TRIE有未 initialize的地方，改了後立即過sample，提交，得到的是WA。kn提出long long的問題，我發現雖然我DP數組有用long long，但中段有些variable沒有留意，只用了int，改了後再交，感覺好累好暈，去一去洗手間。回來後還沒有回到座位kn便告訴我過了，我興奮得跳了起來，整個房間都望着我 = =。這樣便射雕，達到9題，只淨那題數字的DP，還有超過一小時的時間，形勢還算不錯。
CTLi 這時可以上G，他說都是搜索＋DP。雖然做到中途我開始覺得似乎不是這樣做，但又覺得應該相信一下CTLi。而我在做完H的時候精力差不多已經用盡，看看 scoreboard，發現除非IsolatE全清，否則我們罰時領先，心情安心了一點。中途看看旁邊的交大女隊，她們同樣是9題但還未做H，看到她們做了一段又三個停手，應該做不到H，又安心了一點。再望兩望還是集中僅有的精神想想G有沒有其他方法做，方向正確但還是想不到，看還有半小時，唯有放棄轉而支持CTLi。CTLi在最後二十分鐘過了sample，提交得到TLE。於是便轉而用其他data structure或優化，希望可以加速，但一直到最後還是各種No的結果不斷出來，比賽就這樣結束。台大和交大很明顯最後也做不到H。
比賽完後很灰，錯失了champion的好機會，而出線world final的機會亦不太肯定。灰了一段長時間後心情恢復了少許，心想還好拿到第二。交大的coach zhuojie(去年world final冠軍)和其他coach還有眾隊員走來問我題H的做法，原來交大他們全部都想不到做法，於是我便很有型地把算法告訴他們。在頒獎禮前chin看到香港大家send來的email才知道我們只得第三，又灰了很長時間。後來聽Leo補充，原來這隊冠軍的台大是由三個IOI金獎組成。
這次比賽落敗的原因並不在於前面的失誤，完全是因為做不到G。我們雖然做前面的題目做得很慢，但到最後亦有超過一小時的時間去做G。即使前面失誤減少，亦再需要很多運氣才可以比得上台大開局的完美表現。題G是我們應該有能力可以做到的，所以題G是本次落敗的關鍵。假如中途做好一點，就可以拿第二，出線機會又增加10-20%。假如運氣好一點想到G的做法，出線的機會便會升至100%了。現在感覺出線的機會只有50%，因此在Kuala Lumpur的比賽又更加努力。
[回憶比賽過程做題的先後次序可能和實際有少許偏差]
PS1: 題F有很多老手中伏，都往SCC的方向想，但其實頹做N次DFS也很快。
PS2: I hate Jakarta.
沒有留言:
張貼留言