立志：見你地頭四題solve得咁順，我仲諗住你地會做到六題。如果第五同六題都順啲，如果whh諗到漏左check呢個case，如果ctli條f都搞掂埋，咁就有六題lu。
ctli：冇咁多「如果」。。。
話遺憾
我又唔係真係覺得極度遺憾
今日既表現
如果同過去training去比較
都差唔多係平時水準
講下戰況
一開始我開機set野 (VIM, INDENT of gedit...)
然後大家發散睇題
whh：A，D，G，J
kn：B，E，H
ctli：C，F，I
發現 G 有grid，疑似 Geom，就用 H 同 whh swap
whh䏲到 J，好快講左題意我地聽
一時間唔係咁諗到點做。。。只係feel到係暴力搜索
（但可惜地，J 呢題睇漏左一句好重要既句子。。。後續）
ctli 講出左 C 既題意
佢一講，望望 input 既 range
就即刻諗起座標離散化，再bfs／dfs
但ctli就話諗一諗先
然後，我同大家講 G 既題意
因為 input 既 X 係distinct
有強烈既 DP感覺
whh 好快想出 DP 既輪廓
大家都覺得好 make sense，就決定第一條上呢題
交由隊伍之中最擅長DP既 ctli refine whh 既 idea, 寫recurrence同核心
而我就先 code住食input，同埋計 all-pair-distance 等等立雜野
（誰不知，就連呢一題都睇漏左兩樣野。。。）
當我寫曬啲無謂野既時候
ctli 寫好 recurrence，上得
whh 呢個時候同我講 E
聽佢講左兩至三次佢既想法
佢既表情話我知佢好肯定算法既正確性
不過為保險計，我地點都要做到 "每條題至少兩個人䏲過"
睇完題目一次
見佢好肯定咁
聽落個 Algo 又覺得好啱
就決定第二條上呢題
冇耐，我地見到打對台既 Cornell 揚起 G 既氣球...
（btw，佢地好勁...orz）
立一立scoreboard
有成排隊伍 solve 到 J 。。。
但我地又暫時諗唔到
有少少frustrated
但我又咁諗，turns out 我地應該會做到的 =]
ctli code code下
指住題目入面 0 < b1, b2 < n, b1 != b2 問我
....發現我䏲錯左題目。。原來佢input係順x次序入
慶幸我只係code多左一句無謂既sorting
對段code整體冇位何影響
好似係呢個時候，我同whh講
不如再睇多一次 J
佢話覺得好似好浪費時間
之後，ctli 又指出一個問題。。。
答案好似有兩個喎。。。
睇真啲，原來題目 fix左，第一步一定係由０->1
orz...同一條題目睇漏左兩樣野。。。！
呢個時候whh不時望 ctli code成點
我就同佢講，先唔好俾壓力佢
ctli 終於過sample
佢話：我唔想再試喇
就決定交，一棍！！
62 - Problem G AC (ctli, DP)
whh 上 D
因為做左充份既 offline coding
好快手地就搞掂, very good!
80 - Problem D AC (whh, DFS+Greedy)
然後我再次同ctli討論 C
我同佢講，應該係座標離散化
再做一次bfs
我話, 應該做兩次bfs搵intersection
佢更正：做一次就足夠
而同一時候
ctli 想開條 F 黎做
佢話應該幾易做
大約係for每個三角形，戳式計 contour line 既長度
我：嗯...聽落好有道理...
確定C既算法之後，我就上機 code C
code下code下
點知code落好長。。。
我原先仲同大家講 40 行左右可以code好
所以有些少急躁...
跟住... code code極都有bug...
都灰左幾下
搵ctli黎幫一幫手
終於過左 sample
交... RTE!!
103 - Problem C RTE
我地收到第一個紅色既 response......
呢下搞到我好驚
有理冇理... 即刻print份code出黎先...
ctli循例問我：你用dfs定bfs
我：dfs
ctli：會唔會爆stack？
我：嗯...
ctli：1000 x 1000 喎
我：（寒左一寒。。。）係喎...好似係
ctli：wawawa，等陣先，（stack size）應該只係 O(1000)
呢個時候, print左出黎既code回來了
望一望... ... 心裏 X 左一聲
原來我犯左一個低級錯誤：array開細左！
因為怕蝕 penalty
改一改... 都係chk真啲先交
懷住好唔肯定既心情, 皺著眉 submit...
110 - Problem C AC (Kn, Discretization+DFS)
呢個時候我心情有點激動
我忍唔住抱住頭同大家講：
我差啲累到大家浪費好多時間！
（原來呢個時候，立志望到我抱住頭呢個pose...
（佢一直喺上邊觀察我地...
（佢後來問我果時係咪 WA）
睇睇個scoreboard
排頭十幾！
大家心情都好興奮
個心好定
咁最正路
下一題理應開 J
同whh一齊傾
（ctli code 緊 F）
大家都向 15 呢個數字去諗
我點都傾向於暴力搜索
初步諗法係：由上至下，由左至右填充
但有一個問題... 點儲 visited？？
whh 提出用 BIT 記 Visited
而我又覺得冇咁複雜
因為頭果啲 team solve得好快
跟住。。。一路諗，一路睇題目
發覺睇漏野！！orz
每次切割一定係沿住直線/橫線切！
不過還好
叫做發現得早（相對解題進度而言）
我第一反應係
諗起前排先做過既 棋盤分割...
繼續諗... 其實係只係狀態 top-down DP
同whh傾
發現同佢同我諗出 一模一樣既 DP
加左兩個好正路既optimization
（後來發現呢兩個 optimization 同 ACRush 既一樣, 我估大部份隊伍都係咁做吧....）
做左一陣offline coding, 就上機趕走 ctli
（呢個時候發現，佢條 F code得好長）
code... 過sample
但有少少慢
問大家set唔 set visited好
因為 N 細
而且又試左一個大 test case ok快
所以覺得唔洗...
交...
Refresh... Refresh... 幾次都仲係 "Running"
170 - Problem J TLE
第二次紅色response...
又係我...
灰...
於是... 就好快咁開左個
bool vis[100][100][1<<15]
儲visited
但係...
我：memset 令到個 program run得更加慢！
ctli：嗯...你每次只係set０同１咋可
我：係呀
ctli：有幾多個test case呀？
我：佢冇講
ctli：well... 好啦，用integer啦...
ctli：嗯...俾黎吖
(啪啪，啪，啪啪..（打字聲）)
172 - Problem J AC (Kn, 狀態DP+Cut)
邊個話佢果招用 test-case set visited 冇用！
喺 World Finals 都用得著囉！
Refresh scoreboard
Rank 10th!!!!
去到呢個光景
我地覺得前路一片光明
心情極為開朗
（但係。。。。我地冇諗過。。。 我地之後兩個小時就再收唔到一個 AC...）
ctli 繼續 code F
（呢個時候有一隊 AC F了...）
我同whh繼續睇其它題目
形勢：
A... 算啦，唔會開黎做...
B... 望scoreboard，最正路一下題應該做
但睇完problem stmt，同埋見到 scoreboard 上面好多錯棍...
覺得呢題好陰
E... 估計係狀態DP... 但真係好絕望...
whh 有嘗試過寫下個DP, 但最後大家都係唔敢郁手code佢
F... 我問ctli洗唔洗re-read problem stmt, ctli話唔洗
同時地, 發覺呢條題目好難幫到佢
H... 3D-Geom... 好變態... 感覺就係... 無從入手
I... 同 E好似... 認定係一o的好難諗得出既DP
K... 好唔肯定，但覺得做到
whh睇完 Problem B
笑住咁同我講 原來 B係頹題
聽佢講落，又係喎
於是乎，接下來既一個鐘
ctli 同 whh 交替上機code F 同 B
我就不睇其它題目
聽下 whh 同 ctli 既算法
同埋戳下ctli 一兩野 (比較少理whh條 B)
ctli 既 F 段code
好難明
但冇計, 呢條比較煩
另外即使要 trace 佢既 logic 都ok難
ctli 開始 submit F
whh 都開始 submit B
不過 return 番黎同樣係連續既 WA...
我有睇其它題...
認定 K 有機會做得到
時間過得好快...封board
一個小時... 我地冇收到任何 AC...
跟住 ctli 條 F 又卡住左...
我地靠 ctli 食糊架!!
呢個時候
我做左一個好奇怪既決定：開 Problem K
到左而家，我都唔sure 當時呢個決定有冇錯
雖然 B 好多隊過
但係有隊甚至係交左 17 次都依然過唔到
但另一方面
K 既算法好顯然
同 whh 同 ctli 傾過
都認定係咁樣做
而自己又覺得可以30 min內 code 得出
所以我決定上 K
時間一分一秒地過
到左最後 30 min左右
ctli覺得，F 陰既case，諗到既都幾乎諗曬
而whh先後上左幾次去改
被WA不斷折磨...
（因為我code緊K，所以print code佢睇）
ctli 後來索性過黎睇我 code K
code既過程搵到一啲打錯既地方...
時間不斷倒數。。
想必大家心情都好緊張
到左最後
我code 既 K 過唔到 sample
ctli 頹交左幾次依然 WA
whh 搵左好幾個有機會錯既地方，改，都係WA
就係咁
比賽最後既兩個小時
我地一個AC都收唔到
結束果一剎
真係灰左...
(待續...)
沒有留言:
發佈留言