CUHK 終於再一次獲得 ACM ICPC 區域賽的冠軍!!
我們最終解掉全部十條題目
以題數勝出賽事！
(Non-ACMer 可以直接跳到最後
(或者略過本篇 entry ，閱讀即時賽後感想)
We are the CHAMPION!!!!
Final Scoreboard: http://www.iium.edu.my/acmicpc/upload/html/
(以下事件順序可能有錯誤)
(當我們想拍下PC^2 Submission page 的時候...
(我們發現 PC^2 被別人關了... Server 也停了)
(注：內含題目及算法透露)
(略過一開始的賽情延誤)
等了好久，終於開始正式比賽
題目只有一份，由 Joe 分派
我一望題目 format... UVa Contest ?
然後閱讀了某題 (好像是F)，感覺不頹
一下子安心了 (這次不是 Rush 頹題比賽)
沒久，Joe 把我趕走
原來有一道超頹題
5 min: Problem B - Extremely TUI (1Y; Joe)
與此同時，我把 Problem I 題意告訴 CTLi：
Given 一棵 Directed Tree，求 Topological Sort 的方法數
CTLi 想了一會，在 Joe 離座時便可以上機了
(後來聽 Joe 他們說才知道，基本上這題是跟 Jakarta Problem B 極相似的 DP/Counting
(另外，這道題有隊伍極速 AC...
(大概是我們圈子內不知道的 Classical Problem)
同一時期，Joe 告訴我老早有隊 Accept 的 Problem H
其題意是：
找 N 根整數長度的 rod，使得當中沒有四條能組成嚴格四邊形
最小化其中的最大長度
(e.g. 1,2,3,6 不算是四邊形)
Simulate 一下 N=4 的 case: 1,1,1,3
又 Simulate 一下 N=6 的 case: 1,1,1,3,6...
Joe 沒久便發現 / 猜想：
Given 一組 rod，"最容易" 形成四邊形是最長那四根 rod
所以便猜想答案是：
- dp[1..3]=1
- dp[n]=dp[n-1]+dp[n-2]+dp[n-3] (for n>=4)
我們沒仔細驗證算法便上機了
這類 "純打字" 工作當然留給我
同期，我又順度把 Problem A 告訴他
因為這題 Range 小，DFS 暴試即可
Joe 問應該由我做還是也做
Discuss 一輪後，嗯... 這類 "純打字" 工作還是交給我吧...
(我是 team 中的打字員 -.-)
當 CTLi 的 I AC後 了，我緊隨其後上機
23 min: Problem I - DP (1Y; CTLi)
25 min: Problem H - Observation→TUI (1Y; Kn)
此時後看 scoreborad... 學校 + team name 是錯的...-_-
用 time penalty 做 mapping，發現我們 rank 1，感覺很好！
(此時我在暗爽：在香港看 scoreboard 的你們或許在替 "我們team" 擔心吧? XD)
然後我就繼續寫 Problem A
卡了一會： < VS <= (again...)
但通過 sample 後 還是順利 AC
34 min: Problem A - Exhaustion (TUI DFS) (1Y; Kn)
在我做題的同時
CTLi 再跟 Joe 討論 Problem F
Joe 聽完我 (之前) 說題意以後
認為這類 steiner tree 問題存在簡單的 壓縮DP 算法
(而我則感覺到可能要 插頭DP)他們兩大DP 高手一番商討以後
最終得出一個 四維DP 算法
同一時間， Joe 把 Problem D 題意告訴我
並決定由我來寫
丟下了一句引述 CTLi 的話：
只要由上至下，由左至右 scan
貪心地放 十字型tile 就可以了
這題有一點點 (不算極度) 麻煩，在於填十字及 build graph
不過寫一些類似
dx[] = {0, -1, 0, 1, 0}, dy[] = {0, 0, -1, 0, 1};
還是能簡潔地解決但我沒想過寫這題居然還會錯無聊 bug...
(感覺很像自己當時在 Jakarta 卡 Problem J...)
卡了好久才過 sample (@~60 min)
提交，返回 WA在我 debug 同時
Joe 發現陸續有隊伍通過 Problem C (我閱題那時的第一感覺是煩題...)
便叫 CTLi 解決之
另外，Joe 開始獨力解決並編寫 Problem G (看起來很有信心)
對於 Problem D，我再改了兩遍還是 WA
Bug 1: 放十字 tile 時沒有檢查那些 grid 有沒有 overlap 其它十字tile
Bug 2: build graph 時沒有檢查 grid out of range
同一時期，Joe 的 Problem G 出現 (本機) infinite-loop 的 bug
如是者，我們三人各自卡題... orz
而 CTLi 的 C 沒能通過 sample...
(感覺真的很像 Jakarta 2010 當時一起卡3題...)
過了好一陣子 CTLi 的 Problem C 終於搞定
98 min: Problem C - DP (1Y; CTLi)
(按：在scoreboard上看見的 2Y........
(......是因為我把 D 錯交做 C /_\ )
沒久，Joe 的 Problem G 終於通過 sample
(我驟眼看起來，code有點複雜及長)
Joe：都冇架啦，都係要交架啦
便 Submit，返回 Yes!
108 min: Problem G - Geometry + Greedy (1Y; Joe)
我太挫了...
最早開始做，中間卡了很久，de了兩個 bug 仍未能 AC
心情很低落 /_\
我向 Joe 兩度發出求救訊號：
"我真係唔知錯乜...不如你幫下手 /_\"
終於得到他的幫忙
他重新閱讀題目，發現 "Bug" 3：
8-connected VS 4-connected!!!
CTLi 在說題意時沒有講清楚...! orz
讓我和 Joe 都以為是 4-connected...
(其實我認為若能發現 Bug 3 的話
(Bug 2 就不會發生
(因為在 那條array 前方有另一條array，有足夠被被 memset 成為 0 的空間)
114 min: Problem D - Greedy + Bi-coloring (3WA; Kn)
我從灰灰的心情恢復過來!
開始閱讀 Problem J !此刻形勢：
兩小時已經完成七題... 可是 penalty 落後
若果輸了，"功勞" 便要歸我 / CTLi 了
CTLi 的 Problem F 也 submit 過
第一次 返回 Time Limit Exceeded，第二次 返回 Wrong Answer
Joe 幫忙 debug，修正了一些錯誤
(詳情我不知道，這些時候我在做 Problem D，AC 後在看 Problem J)
終於 AC!
168 min: Problem F - 壓縮DP (1TLE,1WA; CTLi)
(按：Problem F 的算法細節大多由 Joe 構想)
剩下的就只有 Problem J 及 Problem E
Problem E 是數學題，題目一句就講完：
Given K, find X s.t. K^X = X (mod 10^12)
數學題理所當然地交由 CTLi 想
Problem J 是 2D Geometry
算法幾乎肯定是對每點進行極角排序，再線性掃描統計
整條題目有點 "1999"... 跟 Joe 一起看了幾遍
才確定前半部份，以及最後一段是廢話
(根本沒有甚麼 crack，亦不需考慮甚麼 minimize "inconsistency")
然後寫 sort-by-angle... 也不太難
題意如下：
在一半徑為 R 的圓內有 N 點
畫一條直線將圓形分為兩部份
令第 i 部份 (i=1,2) 的面積為 Ai, 有 Ki 點
求 劃分方法，最大化 Mi = || Ai / (A1+A2) - Ki / N ||
(按：M1 = M2)
直接地想劃分方法未必通過兩點...
但最大化，或許應該必然通過兩點 (這裏想錯了...)
在紙上規劃了一陣
便上啪喇啪喇地把 排序 + 掃描部份寫好
(但有bug，未能通過 sample-.-)
另一方面，Joe 幫忙推導弓形面積公式
(同一時間，CTLi 繼續苦惱 Problem E，期間我好像聽到一些 "Well" 之類的聲音)
Joe 說他可以幫忙編寫計算弓形面積那部份
可是公式有一些正負號問題
最後我還是幾乎重寫了整段個 function
他幫忙出了一些 test case 以進行 unit test
另外，core 部份的 bug 也同樣修正了
終於通過 sample!!
提交... 返回 Wrong Answer (稍灰)
再 debug，找到小問題
再提交... 還是 Wrong Answer
經驗告訴我：是時候找 CTLi 了
只好不好意思地打擾他 (他正忙著想 Problem E)
CTLi：(思考時間近乎零) 下？一定唔會同時穿過兩點
well...點解唔早啲俾我知呢，可以早啲做吖嘛...
呢題簡單 (過E) 咁多
他提出修補方法：只要添加 constant 個 special event point 便可以了
另外，Joe 也看了我的 code，認為有兩個問題：
- Nested for loop iterator variable 的重用
關於這個問題，在有問題的時候 compiler 會給 warning
而我在編寫時候也曾遇過 warning，可是都消除了
所以其實沒有必要修改的
不過當然，改了會安全一點 (以後我會再留意) - Code 寫得很亂
對，有很多不必要的 statement，但它們的存在是沒有影響
我這樣寫是因為以前聽 CTLi 說過
在做這類題目最好開 boolean array 及 用兩支 pointer 旋轉兩周
可是在今天我發現，那些 mark / unmark visited 其實不必要的...
(比賽後當晚我找了 POJ 2280 驗證)
不過我還得承認 code 寫得差 的責任
應該再添加多一重 A1 包括/不包括 event point 的 enumeration
(sorry for "1999"，這裏沒有足夠文字去解說清楚)
CTLi 認為沒必要 (令 Joe 有點躁底)
最終我認為加了會比較安心
而且添加也只是舉手之勞而已
他們同時戳了一個 test case
successfully challenges 我的舊 code
在修改 code 及通過此 test case 後
便義無反顧地提交... (非常緊張...)
可是，在提交不夠兩分鐘又發現有 bug... (關於 special event point)
只好稍作修改再提交 (那時還未有 Judge response)
怎料第一個 submission 居然反回 Yes
(i.e., 我們 "水" 過了)
(再過一會，就接收到第二個 Yes)
229 min: Problem J - Geometry - 極角排序, 線性掃描 (2WA; Kn)
這是第9個 Yes!!
正當我們興奮之際
expect 已經開始做 J 的 NangYang (簡稱 NTU, 下同) 大概還在 frustrated 之際...
發現 NTU 早我們一分鐘 AC 此題!
我們此刻 Rank 2... 跟他們一樣做了 9 題...
只能靠題數分勝負了!!
CTLi 和 Joe 一直在想 Problem E
我的數論沒認真讀，根基不扎實，沒能幫忙 -.-
(有時間的話，要重溫一些與 ACM 相關的數論知識)
突然，CTLi 說：
Well... 不如試下頹做啦...
他說應該很快 code 好
便由得他上機了 (Joe 形容："無奈地讓他上機去做")
(相當快地) 寫好後 發現 sample (run-time) 極速通過
CTLi 難以置信："嘩... 咁神既..."
隨機打了一些大數亦很快地通過...
這種情況... 當然是先提交再算
同一時期，我們策劃打表提交... 防止 TLE
然而表未打好，居然返回一個大大隻的 YES 字
247 min: Problem E - 數論 (1Y; CTLi)
"YES!!" Joe 再一次極大聲地喊出 "Yes" 字
(再一次把我嚇倒了)
CTLi: "E... 衰左喇..."
因為 Joe 先前說過，若果返回 Yes 我們不要讓 NTU 知
以防止他們發現頹做可以通過...-.-
Anyway，對手未必認出我們
是以我們繼續裝忙
只能說 CTLi 太屈機... "水"出如此簡單的算法
接下來的 50分鐘 我們無事可幹
Joe 調教 CTLi... 在鍵盤使用方面 (CTLi 的囧臉流露痛苦神情)
(我則在旁吃大會提供的麵包充飢做 observer)
最後我們協定：CTLi 要誓必要進行 Numpad使用 的 Training
做完全部 10 題的感覺有點奇怪...
心裏沒太大的緊張
以往 Training 很多時候我們都能得到 Champion 的成績
甚至把所有題目做好
終於... 在真正的 Regional 我們成功做到了...
感覺有點難以置信同時... 又認為這是非常合理
我們一邊在 Hea 的同時，有 volunteer 突入搭訕：
"How many have you solved? (問罷便無視我們，自己在數汽球數目)
Eight? Carry on! Try your best to solve all problems!"
OK -.-...
我們的 guide 也忍不住問我們："How many have you solved?"
我們回答： "Ten"
她面露驚訝："All Ten?!"
我們舉起食指示意，叫她不要告訴別人
終於，等了好久，比賽時間結束了
Joe 一個箭步衝向我們正左後方的 NTU 詢問題數
Joe 回來匯報：佢地搖頭(嘆氣)，應該得 9 題
CTLi 說：可能佢地突登扮野呢，可能佢地好慢先做好呢
(嗯...well... )
我跟 Joe 又去找 HKUST 問題數
他們回答：8題
我們沒有回話就離開了 (感覺好像有點不禮貌-.-)
汽球只有 8 個 -.-
只好走到外面找剩下的 2 個
在比賽場地拍了好多相
在個人照中，其中有一張是自己握著十個汽球，抬頭望著它們
我非常記得，在我人生第一個 Regional (i.e., Tokyo 2007) 有一張同樣 pose 的照片
只是那些 (用剩的) 汽球全部是從 volunteer 手中搶回來的
會場內有不少人走來問我們做了多少題目
然後 follow-up question 通常是：
你們從哪裏來、Training 密度如何、玩了多久、你們多大 等等
又有一些人請教題目的算法
其中有部份更要求 code 的 soft copy
Well... 其實大會的電腦 block 了 USB drive
連我們自己也沒能把 code 帶走
可是有些參賽者很堅持，干脆直接列印 code 的 hard copy
被詢問的題目當中
包括較淺的題目，如 Problem A
我絕對不會輕視他們，反而詳細地解釋
因為我自己很明白，3年前的自己別說要一眼看出算法，可能連想出算法也沒可能
盼獎典禮我們拿著十個氫氣球坐得很前排位置
(下意識地覺得會得到大獎?)
最後 HKUST 及 NTU 都沒有 full-team show up
(Hong Kong ACM Local Contest 亦如是... 其實我認為這樣很不專重大會...)
宣佈頭二三名那後那一刻... 實在真的太感動了...
感受在前一篇 entry 提過，不再重覆了
然後我們在會場拿著汽球與獎盃瘋狂拍照
其實好像太招搖了...
但那刻心情實在太輕奮...
又有很多人找我們拍照、聊天，又或者借用我們的獎盃拍照
最後想說幾句話：
- 這次獲得 Champion 部份原因是實力
但亦有一半原因是沒有超強的 team 來臨
(當然，即使是超強的 team 亦未必能 solve 掉 Problem E) - 期望愈大... 失望愈大?
回想自己在新竹2009一戰，Intuition 在眾人期望以及對自身的期望下，落得慘敗的下場
相反，在寧波2009一戰，Intuition 完全沒有壓力，在失誤連連的情況下得到季軍
又有，在杭州2008一戰，++Zz; 在自知無論怎樣都沒可能出線的情況下，得到第四
難道要得到極佳成績的條件，是完全不要有任何期望？(按：輕鬆 != 不認真) - 我們的隊名 - ManiAC 有 Many-AC 的意思
這次 Regional 我們一共獲得 11 個 AC，我成功兌然承諾：
「我喺正式比賽會一條交多過一次，以實踐我地隊名既意思...
到時你地 (Joe+CTLi) 唔洗旨意阻到我!」 - 下一站──埃及，是我們三個人生最後一場 ACM Contest
題目將會更難、更煩、更陰險 (Joe不同意第三點)
剩下的兩個半月時間... 暫時個人目標有二：
1) 練成極高的準繩：找麻煩題目，盡可能降低debug時間；先練準繩，再練速度
2) 繼續做更難的幾何練習 - 以題數衡量 contribution 其實沒太大意義
(據 training 經驗) 很多時候 regional 淺題目由誰做都可以
但 World Finals 就不是了... 每一道題都是難題...
So... Joe is correct：以往 training 同 regional 的難題都是 CTLi KO... "咁樣好斃"
要加油嘗試做難題 - 馬來西亞的 Escort 非常 helpful
在我們預到麻煩時，她們甚至表現得比我們還更煩惱
又一些小事... 例如 我們跟飯堂的收銀員溝通時有語言障礙
但她們還是很有心地慢慢解釋
總括而言，我對當地人留下一個很好的印象
待更新/refine...
沒有留言:
發佈留言