1. Frozen - http://competition.binus.ac.id/icpc/result/
2. Final - http://competition.binus.ac.id/icpc/result/final.html
先說賽果: school rank 第 3, team rank 第 3
十道題目
五個小時
三個人腦 + 三十隻手指
一部電腦....... + 一個按鍵很硬的鍵盤 (超劣勢... 我們的 coding speed 下降了30％)
我們佔據一排桌子!! (一般是兩 team share 一排桌子, 這是優勢!!)
房間內... 右前方是 NTU ! (我們的主要對手!!)
過左面玻璃窗可望見上交女隊 (Joe 說, 他在比賽時看了她們很多遍)
一如以往，一開始我負責 (因為按鍵硬, 很辛苦地) 打Code Template
我在 ~1 min 後開始看題
Joe 看 A, 我看 B. Joe 又發現 題C 是 game, 就讓 CTLi 看. 沒多久，CTLi 上機 code C, 未過樣例/有bug, 列印 code. 跟Joe互相交流了 A,B 的題意, 發現都是一時間未能想出算法. 然後我跟Joe說題 I, 是一道簡單Greedy, 我想跟他說明我的想法 (其實我認為我的算法正確), 但Joe說他很有信心, 便交給他弄. 我繼續看題, 發現簡單的題D. (同時, 又發現 IsolatE 很快地過題C, 後來聽他們說才知道這是 Run 1.) Joe的 題I 也有點不順利. 不過卡題未算太嚴重. Joe 跟 CTLi 交錯 上機/用紙筆 Debug, 然後便一塊在兩分鐘內 AC 這兩題.
24 min - Problem C - Nim Game (1Y; CTLi)
25 min - Problem I - Greedy (1Y; Joe)
然後換我上題D. 是一道簡單的模擬題. 中間也卡了一陣子, 跟著在紙上寫的 pseudo-code, 算是順利地 AC.
34 min - Problem D - Simulation (1Y; Kn)
奪得榜首!
CTLi 的 A 貌似想好了, 他跟我說一下算法, 聽起來很合理, 便讓他 code. 又跟 Joe 討論題 F. 他說有些想法, 應該是 DP + DAG on SCC 做 counting.
Joe: "應該搵左個 DAG of SCC, 再 DFS 一次 (code+example 略過) 就做完"
(其實方向完全錯了......這是第一敗北/bug)
Kn: "俾我諗一陣"Joe: "得啦你唔洗諗, 應該啱, 你睇其它題目"
由於(?) 台大已過 E, Joe 先想E. 印象中他花了一會便把算法秒掉 - 是 LCA. 這段時間 Joe 跟 CTLi 交錯分別上 E 及 A. 在此同時, 我繼續找題目. (直到此刻, 感覺在contest中內沒有大貢獻-.-) 終於找到 - Problem J. 略讀題目後第一感覺是 Shortest Path + Greedy. 再細心讀一遍+想一遍就確定是 Shortest Path + Subset Sum DP (其實應該是BFS... 這是第二敗北/bug...)
然後 CTLi 62 min 提交 A - WA. CTLi 開始懷疑算法正確性... 試著修補算法. 過了 10 min...
72 min - Problem E - LCA (1Y; Joe)
(賽後才得知 Joe 在打 LCA template 時打錯字)
我做的題J未能過樣例... CTLi 繼續想 A, Joe 開始用武器上 F, 108 min 提交返回 WA.
題J 調了良久, 終於過sample, 提交卻返回 TLE... 此時 ManiAC 處於 Rank 3, 落後於 Rank 2 的 IsolatE. 不過此刻心還是挺鎮定的, 因為貌似我們有想法的題目比他們多. (但我沒有留意 NTU 正已神速神準地AC題目)
CTLi: "都話左用BFS 架啦" (他看見我code時曾提醒我)
Kn: "好啦, 我改..."
大約是同一時候我跟 Joe 說了 H 的題意
Kn: "我見 K=10, (據complexity) 可能係 inclusion-exclusion"
Joe: "應該係 AC自動機"
Kn: "係喎..."
然後很自然地, 我們同時回想起 Training 時做的 NWERC 2004 題A (雖那題存在低 dimension DP解法)... 幾乎完全相同.
對於題J... 改 Shortest Path --> BFS code 我又花了 7 min. 提交, 返回 RTE. CTLi 突然說題A算法修補經已完成, 可以做, 上機改了一會, 通過他自己生成的test case... 提交 - Yes!
123 min - Problem A - DP(?) (1WA,1TLE; CTLi)
在細心 debug 後... 終於通過... 最後一個 bug 是 <= VS <. 這裏又用了 8 min.
129 min - Problem J - BFS + DP (1WA,1TLE,1RTE; Kn)
此題我應記一過, 明明經已在紙上寫好 psedo-code, 卻在整過 coding 過程犯了大量低級錯誤, 包括: 把 > 寫成 >=, 列印了錯誤的variable, scanf("%d%d%d", &x,&y,&z,&p);.... 粗略估計這裏總共浪費了 ~40min machine time.
在我跟 CTLi 做A,J 途中, Joe 不斷在想 題F 的 bug, 他幾乎絕望了, 因為實在想不出 algorithm/code 的錯誤. 他讓我看列印出來的 code 並從中找 bug. 但怎麼看也找不出bug... Debug 工序便交給我, 他開始用紙筆準備題H. 在此同時, CTLi 開題B.
在 Joe 提供的 observation 之下, CTLi 幹掉 B:
152 min - Problem B - DP(?) (1Y; CTLi)
由於時間只過了一半, 而我們做了全場沒人通過的 題A, 而且 題H 的算法基本上已經確定, Joe跟我都認為至此刻形勢極佳.
在跟 Joe 討論片刻後, 便讓 CTLi 開始策劃 題G.
對於題F, 無奈之下只好 generate random test case ＋ 暴力 program (Floyd) diff output. 從中找出一個錯而且小的test case, 過程約花了10min. 經一輪功夫, 發現 DFS on DAG of SCC 統計會double count. (e.g. 1-->2, 2-->3, 1-->3, 3-->4)
Joe: "你諗下點handle double count"
(思考片刻)
Kn: "嗯... 做N次DFS計"
Joe: "咁之前做SCC啲嘢咪冇用?"
Kn: "但複雜度應該夠..."
Joe: "你叫 CTLi 諗下"
那只好稍為打擾 CTLi, 他想了一會, 亦想不出好方法. 我再看看數據範圍... N 次 DFS... 時間複雜度也只是 2500*10000 而已 (而且test case 只有10個).
我跟 Joe 說了我的想法, 過了幾分鐘終於獲得重寫的批準. ~4min後...
204 min - Problem F - DFS (2WA by Joe; Kn)
這是第 8 個 Yes. (此時看看scoreboard, 交大女隊超越了交大一(?)隊!
(然後我腦中閃過一絲念頭, 我人生第一場 regional 被交大女隊擊敗... 難道三年後依然要輸給交大女隊?)
Joe 繼續搞 H. 我跟 CTLi 討論 G, 有點深, 聽不太懂, 但貌似他已經有全盤策略. 又返回電腦看看有甚麼能幫 Joe, 他未能通過sample, 隨機丟出幾道問題+戳test case, 有其中一道問題命中 bug - "你有handle 0字起首的 number嗎?" 然後 Joe 憑藉對 AC自動機 熟悉的手腕, 相當快地修正及通過樣例. 但提交後卻反回 WA. 我駭然想起題目雖說答案不會超出 int 範圍, 但 DP 途中有機會超出 int. Joe 作出對應的修改(是一些local variable, DP本身他已經用 long long 記錄)後提交, 往洗手間. 他回來之前便返回 Yes!
225 min - Problem H - AC自動機 + DP (1WA; Joe)
我們在 封board 得到第 9 個 Yes, 是沒有任何隊做出的一道題 - 雕已射!
看看 scoreboard, 有相當多隊做出 題G...
題目全清在望呀...!
此時某twitter用戶樣寫道：
#acmicpc ACM ICPC Jakarta 2010: Chinese University of Hong Kong - ManiAC got problem H! Likely, rank 1 will solve 10
(Source: http://twitter.com/thanhvy)
賽事還餘下 75 min, 理所當然地我們三人聯攻此題
CTLi 的想法是 memorized search : 大約是對 sorted frequencey sequence 做 DP, 又把每一個 sorted sequence encode 做 integer 記錄. 中間過程出現了一些bug, 及運行太慢等問題. 總而言之, 我們 brainstorm 了很多方法怒 opt 依然未能通過. (大多數submission是返TLE.)
至比賽未段, 我們甚至嘗試打表/部份打表... 奈何硬件設置令我們未能如願: Copy and Paste 花了超過 5 min... 當一個 program 在 memset 一條很大的 array 時, text editor 會很 lag...等等
但無論如何, 這個方向是相當錯誤...
看著 frozen scoreboard, 我們猜度會獲得 Rank 2
但結果是 交大的 Halo 做出 9 題, 以更佳的 penalty 超越我們...
還有想說的...
0. 這次中大全部隊伍的表現相當不錯!
1. 同意Joe - 在分題策略上我們很正確. 不過不妨考慮多花點時間討論算法及細節(除非對算法極之肯定/頹題), 以旁觀者角度切入說不定能想出新方向... (e.g. South America 2010 - Problem E, Segment Tree VS Discretization, 今次 SCC VS DFS x N)
2. 題F 讓很多人想起 SCC... 包括上交, IsolatE 等等...
3. 我們居然沒有發現 Clarification 上有列出每題的 Time Limit! (這裏大家要記一過)
[馬後炮]假若知道, 說不定會有更高概率更正題G的錯誤思路[/馬後炮]
4. 對大會安排及比賽設置很不滿:
- 大會要求參賽者6am 抵達比賽場地, 而比賽開始是時間 9am
- 試機的意義, 不是在於測試比賽軟硬件嗎? 幹嘛第一天及第二天用的硬件是完全不同?
5. 嚴重感受到跟NTU之間實力差距... 準誠+速度. 其實我高度懷疑 NTU 那隊只是沒曾做過AC自動機的題目. 而跟上交比較... 貌似實力相差不多.
6. 整場比賽相當激烈, 包括 IsolatE 與 ManiAC 在前半段的爭持, 以及前列 Rank 在整隊賽事的微妙變化...
NTU 神速＋神準 => Time Penalty 超好; 倘若我們最後能以題數取勝, 將會是一個非常有趣的結果
7. 但始終... 比賽過程出現意外實屬正常... 我們檢討一下吧...
8. 總觀整場賽事, 我擔當著援助的角色... 算幫得上忙吧. 期待下一站有適合做的題目.
沒有留言:
發佈留言