2011年6月16日 星期四

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已完,這樣就退役了,還有甚麼想說的就遲些在寫吧,退役文後補。

2010年12月29日 星期三

Topcoder SRM 492

這次是早上10am的SRM (感覺上好像早上的SRM我表現會比較好)
題目分數是250, 550, 1000 (感覺上對我不利, 因為通常我最多只能做450/500)

先看250, 是計算幾何問題
還沒有plan好便想開始code, 一開始亂了一段時間
最後還是窮試兩點和最左/右邊為0的情況
頗慢地完成了, 得到188.xx分
交完還是作了數個test case才放心少許
看看division summary發現排名大約100左右, 心情不錯

然後開550, 看明題目後沒有甚麼想法
搞了一會發現有些括號sequence的感覺, 再想想就相信可以用DP
不難想出一個n^5的DP, 不過認為過不到, 便再想去降低一個dimension
一開始想了一個錯的方法, 覺得雖不中亦不遠, 覺得腦袋又有些累就開始code, 這時還有30分鐘左右
code好發現差一個sample, 細trace一下發現我之前降低dimension的方法是錯的
再想想覺得沒有甚麼好方法, 便把1個DP function拆成2個DP (其實好像可以更優美地做, 不過當時沒有心情想了)
再搞兩搞過了sample便交, 得到27x.xx分, 這時好像還有7-8分鐘
作兩個test case渣一下灘便完了coding session
我的房裏只有兩人(包括我)交了550
看division summary當時排名好像是40左右

到challenge session很緊張, 很怕被cha死
由於我的550沒有信心, 250又不太有信心, 於是便決定基本上不作出challenge
雖然如此, 我還是看看其他人的code, 由於沒有心情看的關係看不到有誰的code感覺會錯
不久同房另一個550被cha死了, 令我更加緊張

到最後被呆等challenge session完再等system test, 這時看division summary排名大概是30

到system test很緊張, 看着上面的1000一個又一個的炒, 我自己的排名一個一個地升上去
終於看到自己pass了system test, 最後總排名16


Current Rating: 1810
不過rating這個東西還是easy come, easy go, 所以下次要繼續努力

2010年12月22日 星期三

[轉載] 復旦某前輩對今年ACM Team的訓話

說得太好了
希望以後的隊員明白, 出去比賽是要肩負起為cuhk拿獎爭光的責任, 並不是去旅行去給cuhk丟臉
你代表的並不只是自己的隊, 而是背後所有支持信任你的老師和同學

===========================================================

诚然,每年关于ICPC WF出线的问题没有哪一次不在复旦ACM队里闹得鸡飞狗跳。关于今年
的什么什么PK之类的问题,我不得不说几句丑话。

其一,争夺出线资格本来没有错。但是,我很希望小队员们不要曲解了“出线”的含义。
代表复旦“出线”绝对不是荣誉的象征,它是代表你将挑起为学校在总决赛上斩获荣誉的
责任。在我眼里,与其去当着世界三百位选手丢尽复旦的颜面,还不如加把劲今后在国内
赛区得点金奖。

其二,ICPC的规矩奇葩不是什么新鲜事了,不必醉心于怨天尤人。历史上复旦在某地丢掉
冠军只有一次,那就是当年的南京赛区冠军,当年的总决赛队。今年国内赛区的成绩还望
各位现役队员能够深刻反省,“期中考试”,“状态不好”之类的人民日报新闻联播式的
理由就不必拿出来了,全国所有的大学都要期中考试,总决赛也不会专门安排在你“状态
好”的时候。

其三,今年出线的队希望居安思危,认清形势也认清自己,明白身上的责任;没有出线的
队也不必再提什么PK什么被黑了。还是那句话,如果PK的话我跟FGD不会缺席的,你们自己
掂量。

难听的话说了这么多,还是衷心希望小队员们能端正态度,明确使命,做当之无愧的复旦
“一队”。没有出线的队伍也不必嚷爹骂娘,好好想一想,自己真正输的是什么……

http://blog.renren.com/blog/246784220/702543083

2010年12月20日 星期一

PKU 3725 - I know the k-th integer

有趣的題目, 因為我實力不足的關係花了我幾天去想和寫和改良

這題我第一個想去就是想去binary search答案, 再看發現的確可以binary search
於是便寫了個binary search, 再找given一個n, 第k個數是多少
這個問題也不簡單, 但也不難, 花了一段時間寫完+debug, 再交得到TLE

看看discuss, 好像需要沒有binary search的做法才會不TLE, 於是再想想發現的確可以不binary search
詳細的details我想得很麻煩, 無謂寫在這裏
主要的想法就是一個一個digit去試, 直至找到most significant digit
大家花少許時間就會想到, 最後通過了之後再交PKU 2171, 竟然過不到
發現是<=和<搞亂了, 沒有詳細想清楚, 證明有些細節不想清楚的話, 雖然自己測試測不到, 但交上去還是會錯的

這題最後寫了很多個版本, 就等於做了幾道題目
不過對這類題目處理還是寫得不夠好, 想得也很慢, 希望WF之前可以改進

ACM Kuala Lumpur Regional 2010 感想

我的最後一個regional比賽
終於,終於,拿到了期待已久的champion
某種感動週期性地在腦海中徘徊

其實在比賽前,我完全沒有想過可以拿champion
不知道為甚麼,我在jakarta的比賽前真的覺得有機會拿冠軍,但今次旅程卻沒有甚麼感覺。
在比賽中途,因為中段大家的失誤,令我亦完全沒有幻想有機會拿冠軍。現在的感覺真的很難以置信。

有人問我們隊玩ACM有甚麼秘訣,忍不住答了teamwork。
隊友的合作和支持真的非常重要。
亦非常感謝大家在香港的支持。

香港中大在ACM的名聲一年比一年響。
自從我們E++和++Zz;在大陸賽區頭段表現出色,到去年Intuition在寧波拿了第三
而今年Jakarta的射雕+放雕亦令大家緊張了一段時間,之後在twitter也有人討論我們
導致TJU看到我們大學的名後便問我們是不是香港中大,是不是jakarta第三 (雖然之後他們發現CDQ後便無視我們了)
相信在今年,CUHK的名字終於在大家心中留下深刻印象吧。

ACM Kuala Lumpur Regional 2010 比賽過程

中大終於拿到了十一年來的Champion!
賽前真的沒有想過這麼順利
我們training經常縱使中途很多無聊失誤亦全清早走,今次真正比賽終於可以發揮出來!
之前聽到題目是由美國的人出,曾經擔心會很頹,但最後題目質素還是非常好
原來是由uva那堆有名的出題者出的

------------------------------------------------------------

比賽因為技術問題延誤了很多,又加多了一個試機session。之後從volunteer中得知我們比賽的機和試機的機不同,又躁底了。試完機大家再入場準備比賽,卻在比賽場地等了一個多小時才開始。他完全沒有嚴止大家使用電腦,於是大家便一起打自已的template。打完template發現還有很多時間,kn又把geometry的library打完。打完後還是有很多時間,大家便伏在枱上休息。
過了很長時間,終於比賽開始了。一開始開題目,題目感覺不長,先把一堆短的題目抽出來看。不久發現頹題B,上機提交得第一個Yes(5)。CTLi隨即上題I,中途卡了一卡,有少許慢,過sample後提交,又得到Yes(23)。我和kn在CTLi做的途中發現已有隊過H,研究一下卻不懂做,找kn討論一下。中途嘗試問CTLi但被無視,結果和kn討論一大堆後想到了公式,待I打完立即上H,很快便Yes(25)。kn隨即緊接做他已看的頹題,亦不久成功解決得到第4個Yes(34)。CTLi看完題D解給我聽,感覺很簡單,我便分給kn做D,悲劇就此開始。kn搞了一會兒很辛苦終於過到sample,這是已經6x分鐘,提交首先交錯題目,再交得到WA。我的題G也想得差不多,便搶機開始coding。Code到中途有bug,過不到sample,便和kn交替地上。CTLi又可以上,於是便讓他先上。中途kn找我幫忙,但好像沒有理會他,看了看便繼續埋頭做自已的題G。搞了好一段時間和不斷的換位上機,CTLi終於過了題C(98+1RE)。看到F已經有人過,是經典的steiner tree DP,想了想便想到DP的狀態和做法。經過一輪掙扎,我還是我的算法告訴做DP有更高準確度的CTLi,讓他準備上題F。我又發現我的code有些很無聊的bug,改完後過了sample,又再交幸運地沒有bug,得到第6個Yes(108)。之後看看kn的題D的題目,發現有地方CTLi看漏了,便叫kn過來看,很快想到解決辦法,kn改後再交終於Yes了(114+3WA)。一輪失誤後終於過了題D到了7題,但是現在罰時已經大幅落後南洋理工(NTU)。值得一提的是雖然旁邊大會有很多準備好的氣球,但在頭一個多小時都沒有派。

出了第7題後心情可以放鬆少許,看看scoreboard的情況,但知道形勢不妙,因為我們不懂得做題E,而罰時落後,而最不利的是CDQ有機會會做到。不管怎樣,我和kn開始研究題J的幾何。聽kn說明題意後,好像便是經典的O(n^2 log n) sort by angle的題目。過了一段時間CTLi需要debug,便換上kn開始code,我亦幫kn寫中間計算面積的部份。CTLi的題F搞了很久終於過到sample,提交卻得到TLE。我再想想,過了一會兒想到加速的方法,可以降低一個dimension,和CTLi討論一下便繼續讓CTLi上。這是kn又說他的題J差不多寫好,等我寫幾何計算面積的部份。我便立即在紙上寫我的code,讓kn打上機,但那段code發現有錯。CTLi這時又得到一個WA,我便沒有理kn,專心幫CTLi fix那個bug。中途又幫kn作test case去測試我寫錯的部份。終於CTLi上機改好,再交得到第8個Yes(168+1TLE+1WA)。我們的第二維持了不久便被HKUST過頭了。之後我讓CTLi全力想E,我和kn一起做J。又過了一大段時間,終於過了sample,提交得到WA。中間發現kn寫rotation的東西寫得很差很亂,把那段code簡化,和修改了有些for loop撞counter variable名的情況再交,仍是得到WA。這時候和CTLi討論了很長時間(途中因為CTLi不斷ban我的想法又不說原因令我有些躁),發現我們的assumption不正確,有一個case完全沒有考慮。這時我還高興,因為這個case不太易想,很可能NTU會發現不到,這樣我們有機會9題便勝出。kn上機加上再考慮那個case,又handle兩點分在兩邊的case,又過了自已新加的test case再交。交完不久kn發現那個case handle錯了,未等response再交,最後得出兩個也是Yes(229+2WA)。再看scoreboard失望地發現NTU亦過了題J,同樣達到9題,罰時領先我們。而CTLi又一直說不懂做題E,於是就等同於這次比賽已經輸了。

最後當然三個人一齊在想題E。我提出了可以拆成兩個式然後再用Chinese Remainder Theorem,而mod 2^12的式可以暴試找答案。但對於另一公式亦想不到解決方法。再想了一陣子CTLi說他可以試試頹做,我提出他把算法告訴我們然後他繼續想,我們上機頹做,但他說很簡單很快便寫好。無奈地讓他上機去做,不久CTLi便寫好了,打入sample發現極速出結果。再randomly打一寫大的數亦是立即可以出答案。CTLi提出立即交,但我和kn建議先打表。但打表途中我們發現如果沒有答案便會loop死,而我們又不知道怎樣check有沒有答案。我又提出去數iteration的數目,太多時便break。寫完發現打表打得極慢,於是不知道為甚麼又放棄了。最後我們一致通過交CTLi那個“頹”program,便很緊張地等結果。這時我們再試試random的test case,發現仍然是很快。由於CTLi不斷說他的方法很頹,我擔心假如NTU知道我們過了便又會試試頹做,所以還是不讓NTU知道的好。我便叫隊友看到Yes不要大叫,保持秘密不讓NTU知道。

因為judging time很長時間,我在很緊張和沒有警惕的情況突然下看到巨型綠色YES(247),也不小心大聲叫了YES,很失敗。到最後我們還是繼續假裝很忙,一開始在分題目,把整份題目從我們打印的code中抽出來。中途又有volunteer見我們渣攤來和我們說話,但由於他們壓低聲量,我完全不知道他們說甚麼。只記得有位大叔走過來看到我們8個氣球,笑說題目是不是很難,沒有可能做完呢。之後無聊了一會兒便叫CTLi打code,讓我留意CTLi打code的問題,好讓在World Final可以進步。CTLi的問題發現有:1.不用alt-tab,2.不用右手尾指,3.雙手放在keyboard沒有default固定的位置,4.不懂用numpad。現在已策劃一連串特訓給CTLi。感覺最後50分鐘時間過得很慢。

比賽結束後很緊張,先走到南洋理工一隊問題數,他們很灰地搖頭(大概自己在jakarta也是差不多的表情吧)。然後再跑去問HKUST的題數,是8題。這時腦袋有些空白,回到座位向隊友報告後,仍好像未必接受自己是champion的事實,有點不知所措的感覺。先把漏掉的氣球拿回拍一下照,之後又有很多人找我們問題目和拿code,又有找我們拍照。走時統一統計,當我還想認叻的時候,發現原來自己只是做了兩題。結論就是我今天的比賽是渣灘的。有傳言說新加坡某大學出了10題,我不太相信,因為已問過NTU。我猜是他們把我們認錯是新加坡的隊伍吧。

到頒獎禮,心急等了一大段時間終於證實自已確實是champion。上台的一刻想到等了十一年終於拿到了,有些感動。驚訝地發現HKUST一個人都不在,NTU也只有一個人上台拿獎。之後有很多人找我們拍照,亦有不少人借我們的獎盃拍照。我們亦找judges討論題E的做法,發現兩個judges和我們的做法也不相同。最後不斷拍照,連回hostel的巴士也沒有上。最後Derek Kisman在我們拍照時走過來又不敢打擾我們拍照,我們便立即輪流和他單獨拍照,他顯得有些無奈XD。拍完後原來他是想來找CTLi討論E的題解,說CTLi的做法好像可以解釋他一個之前不明白的地方。走的時候本來打算步行回到hostel(大約15-20分鐘路程),但途中看到volunteer姐姐的車,她們很好心地車了我們回去了。對於IIUM主辦的volunteer姐姐印象還是很不錯的。

趣事:
1. CJ還是很喜歡叫全部人拍手掌的演講
2. CTLi影相時不肯笑,連volunteer姐姐都忍不住說他"You look so sad!" 我和kn一齊“sosad!”
3. 最後找CJ拍照時,他有點不耐煩。問我們甚麼學校,答了發現我們第一,然後送了我們特別禮物,是一個空的袋 (o:

ACM Jakarta Regional 2010 比賽過程

這個可能是近十年中大最有機會拿冠軍的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.