本來還想仔細 "執一執" 才發佈
可 World Finals 正日事過已經超過10天... 所以還是先發佈吧~
（此 Entry 會不定期更新
（Last Update： 2:07am, 17/02/2010）
（Last Update： 5:05pm, 06/03/2010）
比賽現況：
起初：在 0~172分鐘 AC 4題, 位居第10：
62 - Problem G AC (ctli, DP)
80 - Problem D AC (whh, DFS+Greedy)
103 - Problem C RTE
110 - Problem C AC (Kn, Discretization+DFS)
170 - Problem J TLE
172 - Problem J AC (Kn, 狀態DP+Cut)
（特別一提的是： CT Li 在 大約 100 分時開始做 F）
中段： 在 172~240分鐘 一題也過不了：
Whh 開始做 題B (煩+Simulation)
CTLi 繼續替 題F 除錯 (煩+2D Geom)
他們兩人輪流上機
Kn 在看其它題目 及 幫忙 Debug
後段： 在 240~300分鐘 依然一題也過不了：
在和 CTLi 及 Whh 討論了一下後
Kn 決定開始攻算法顯然的 K (直接+3D Geom)
最後 Whh 的 題B 和 CTLi 的 題F 都沒有過
而自己的 題K 連樣例也沒過
（事後發現，題K 只差一點點
）就這樣... 4題，第36名
（5題就 第14）
坐在我們對面的 Cornell 很強
比賽整過程我們一直緊隨其後& lt;br>
（比賽詳細?述... 可參見 ACM-ICPC World Finals Day 5 - Contest!）
比賽的軟件及硬件：
軟件 － "Kattis"：
今年用了一套新(?)的 Judging System
放棄了 "PC^2"
現在可以在 Terminal 輸入 Command 提交題目了
（可我們還是傾向保守，使用 Web GUI 提交）
今年的 Judging 速度很快
從未見過 Waiting / Pending
但有一點麻煩就是
它不時會開啟新一頁通知 "Clarification"
而且視窗卻是從沒有閃動半下，或者即時 "置頂"
我們都沒有注意到...
這在我們比賽的後段... 添了不少麻煩...
硬件 － Team Notebook：
亦即所謂的 「武器」
我們精心製作了 24 版「武器」
當中包括了一些
由 CTLi 選擇的公式
（他認為不大可能記入腦 而且 推導會相當麻煩）
除了分頁有些奇怪以外
其實我覺得用起來挺方便...
所有要用的 variable 都有打進去
而且絕大部份都是隊員親手調試及驗證的
大多通過至少 3 至 4 條 OJ題目的 ...
不過，在比賽當天
除了 Whh 在思考 題J 能否應用 BIT set visited 時
翻了一下以外
我們就沒有碰過半下
硬件 － Keyboard：
我對這一環尤其不滿
按鍵很扁平
Orientation 當天首次使用是很不習慣
經常敲錯相鄰的鍵
雖然在 比賽當天算是比較習慣了
但用起來覺得依然很不舒服
另外一提：大會不肯讓選手自攜鍵盤
對比賽結果的感想：
在 World Finals 完結後起計的 1個小時
心情是異常正常的失落
不過過後又覺得沒有甚麼...
（跟 Whh 不約而同地）
愈來愈看淡比賽結果（像現今看待每一次 SRM 的結果）
縱使
未能在比賽中 solve 6題
是遺憾
但我不會因為這份遺憾而感到甚麼憂愁之類
（貌似說的很矛盾．．．
（總之就是我雖然在意結過，但是又不會很在意
）至關緊要的是
在今次比賽的過程和經歷中
能夠對自己（我不知能否對別人）證明 Intuition / 自己 的實力
每一次比賽...
都能自己的實力再提昇一點
又或者發現自己不足之處
跟別人的差距
然後推動自己要更加努力
至於檢討...
我想，還是要再小心點吧
Intuition 在 Coding 的準誠度方面已經愈來愈好
而在這次比賽中
我想大概不是 coding 方面出錯
應該是想 Case 時想漏了...
而 World Finals 的題目偏向比較陰險...
看起來貌似簡單的題目（像今次的題B）
很多時候暗藏殺機...（這... 容下一節再加詳細討論）
對 World Finals 題目的感想：
用 3句 去總結：
1) 算法傾向比較直接，很多時候好快就能想出來
2) 但是大多在在一些陰險的 Case，而且一不小心就會愈 Code 愈長
（包括在 Code 之前沒有仔細規劃，或者愈想愈多 Case...）
3) 有不少題目屬於「就是做」類別，只是寫起來很麻煩... 很長...
對於 1)，這是好的
因為比賽不是考核你的知識的量 (Quantity)
（想想，大陸賽區多年來一而再再而三出一些論文題...）
（又有些題目的 solution 是 某某算法的某某特殊 構作
（如果沒有聽過，想信沒有希望可以在比賽時間內想出來）
考驗參賽者 "大路" 的知識，我認為這樣比較公平
（很多 IOI / NOI 等等的題目... 我看完之後就只有絕望的感覺）
而 2)... 例子太多了
Intuition 做了 4 年的 World Finals 訓練
就已經見識過不少這樣的題目了...
* World Finals 2006 - Problem E: Bit Compressor
* World Finals 2009 - Problem C: Grand Prix
* World Finals 2010 - Problem B: Barcodes
可以做的，跟隊友有更多的討論，想清楚些，審慎些吧 -_-
對於 3)... 舉例說明吧（括號是本人程序的 LOC）：
* World Finals 2008 - Problem F: Marble Game (147)
* World Finals 2009 - Problem A: Air Conditioning Machinery (97)
** World Finals 2009 - Problem C: Conveyor Belt (176)
挑戰一下最後一題 就會明白了我的意思了...
對 Intuition 的感想：
我覺得 Intuition 這個組合很有趣
三個偏向數學能力較佳
但 coding 能力略為偏差（但已經明顯在進步中）
Intuition 中沒有哪一個特別是全能型
而且大家都是新人：
Whh 和 CTLi 的 ACM 年資尚淺
而自己則是才踏進 信息學競賽 的第 3 年...
Intuition 似乎是 臨時拼湊出來的隊伍
（今年太多人 正式/暫時 離隊...）
不過各人的長處在比賽時
能夠恰到好處地 互補不足
比如， Whh 和 CTLi 的洞察力特別強
而自己的 Coding 比較快
很多時候可以他們說算法，我就盡快實踐
（雖然這是一個很常見／基本的隊型）
又比如，有時可以據自己做過類似題目的一些經驗
Mechanically "戳" 出隊友可能遺漏了的 Case
而且在熟悉的 topic 方面
又貌似恰好各有不同...
其實，早在 往年寧波一戰
打出 第3名 的好成績
讓我（（估計）也讓大家）非常吃驚...
（而且那次是比賽表現是略為偏差... 犯了一些低級錯誤）
是以感到... Intuition 其實有相當大的潛力
在今次 World Finals
Intuition 幾乎把 6 題 解出來
（我堅信我們有足夠能力）
我覺得已經是奇跡了
冰天雪地：
是第一次置身於攝氏零度以下的城市
所以出門前不敢馬虎
特地（花錢 T_T）準備了 羽絨、雙層褲、手套、雪地鞋...
攝氏 -20 的氣溫
是要親身經歷過才會明白...
當你身處室外
不戴手套超過 30秒 後
你會感到手掌上的血液似乎要停止運行了...
如果沒有做好面部和頸部保暖
面部肌肉會被凍僵
繼而說話口齒不清... orz
（就像雪雕當天，長期位於室外）
哈爾濱的積雪似乎隨處可見
踏上雪地的感覺也是挺有趣的
天氣也很乾躁
不論室外還是室內
經常感到口渴
縱使手和臉已經塗了保濕和潤膚的
依然感到乾躁
不過... 始終有些遺憾最終沒能看見下雪
對該如何組隊的看法：
如果三位隊員都是全能型
（算法、數學厲害 + 小心 + 經驗豐富 + 實現能力強 + 打字快 + ... 暫時想不出）
當然最好
但這種情況比較難發生
所以如何配搭能力去組隊相當重要
最好能夠配搭出一支隊伍
各人的能力可以洽好覆蓋盡量多的
而且各項目深度要足夠
又或者可以這樣做：
在組隊後，每位隊員分別去深入鑽研某些 topic（往年就是如此）
我認為 理解的深度比廣度更重要
（因為有 "時間" / 學業功課 這限制，這裏 "深度 VS 廣度" 又是一個取捨的問題...）
打個比方：
一支team裏 有一個對 Max Flow 理解很深入 + 一個 Geom 很強
比起
一支team裏 有兩個對 Max Flow 及 Geom 半桶水
要好
比賽策略：
縱合各次訓練／比賽，再加上跟不同的人討論
歸納出，最基本要做到以下各點（除非你肯定你的隊屬於「三大高手型」）：
1) 每一條題目，>= 2個人看過
愈陰險的賽區，愈長的題目愈有需要這樣做
在 World Finals 的題 G 及 題 J ，及很多次訓練，我們就犯了閱題不夠仔細的錯誤...
有時候直覺告訴你「這題目陰險」時，就更加要審慎閱讀
盡可能想出更多的 Critical Test Case...
2) Offline Coding
記著，比賽最珍貴的資源是「Machine Time」
在「上機」之先一定做足夠準備
開甚麼 Variable，Array 的大小 都要想清楚....
尤其是一些明知道要花好一陣子才能想清楚的地方
如：一些 Index 的先後 Update 次序 （如：DP的狀態轉移方程）
這樣可以確保不要白白浪費寶貴的 Machine Time...
而且也能減低令 自己／隊友 心情緊張的機率
（對我而言，最好能夠先在紙上寫出跟程序 80% 相似的 notes）
3) 可做的保險都做
包括 Array 盡量開大一點
例如題目說 M <= 1000, N <= 10
可能你知道開 int dp[1000][10] 就足夠
但若果空間足夠，何不開 dp[1000][1000]，甚至 dp[2036][2036] 呢？
不過，這裏說的僅限於「做了也無傷大雅」的保險：
例如，在處理上整數時用 long long 無論如何會比 int 較為穩陣
可是使用 long long 某程度上會影響時間
而相反把陣列開大一點，只是改一兩個數字...
4) 跟至少一名隊友描術自己的算法
盡可能詳細至 Coding 的 Level，這樣做的好處包括：
A) 所謂百密一疏，很多時候可以看出自己的思維漏洞，或者再簡化算法 / 程序
B) 其後隊友幫忙你 Debug 時會更輕鬆
（甚至可以做到一邊看你 Code/Debug 一邊修正你的 Typo）
ACM ICPC 是 3位1體 的比賽
並不是個人能力的簡單湊合
成敗關鍵很多時就在乎團隊合作
展望：
個人而言
假使下年還有機會出戰（要看這年的研究進度.... OTZ）
會主攻加強自己的
Geom 、 數學 、 code煩題
的能力
... 吧
[最新加入：以下段落]
在一些算法較為不顯然 (或Ad-hoc) 的題目
尤其是那裏自己沒有見過的...
又需要幾個 observation 的
通常不能很快出來...
吾自知在算法構思上
遠沒有 Whh 及 CTLi 的強
而至於能夠 mechanical 的算法構造
似乎能夠憑經驗 在隊伍中作出貢獻... (像這次的題 C)
所以來年的目標
都是簡單題
以及學習那些較為麻煩
但是構作很 mechanical 的 topic
難的題目，留給隊友吧 =]
個人感想：
今年是第 3 年玩 ACM ICPC
自己沒有 OI 背景
中學時沒有唸 programming
（不過也算是自學過一點 ActionScript 和 C）
甚麼 BFS, DFS, 以至於 Graph
都從沒聽過
來到 ACM Team
追得很辛苦...-_-
但經過努力
還是可以做得到的！
（而且過程是刺激的，享受的）
當然，不會自滿
在思維和 coding上，還有很大進步空間
這 3 年內的能力提昇
絕對要感謝 CUHK ACMPROG 的各位隊員
尤其是各位師兄
你們用心 training，又肯跟我一塊討論算法
在你們身上學到太多東西了
（真的打從心裏感激 x 10000000000）
我覺得某人說的一句話特別好：
「認真做是只能把事情做對，用心做事才能把事情做好。」
這 3年來
對 ACM 的熱衷從未減退半分
愈來愈積極地參與每一場比賽
做每一道題...
Online Contest...
SRM...
總之... 讓自己愛上 Coding (Contest) 吧！
這篇 Entry 寫的很嘮叨...
（不能確定會不會存在一個人把整篇 Entry 看完一遍）
但容我最後一次感激 CUHK ACMPROG 的每一位
舊的師兄
新的隊員
讓我（們）在每一次訓練中燃燒起這把「火」
!!是你們把我（們）帶入了這次 World Finals Contest！
最後，特別鳴謝 某某先生的 RP++
沒有留言:
發佈留言