Google Codejam 2010 - Round 2

當天剛剛從日本飛回香港
有點累
開機的時間大約是10:20pm

這次比賽... 炒粉了

身體及精神狀態都很差
不過表現未免太差了吧...

感覺 A 和 B 應該是 DP（我還沒有看題解或其它人的解）
D 沒有看
C 是能力範圍以外的題目 -_-

Google Codejam 2010 - Round 1C

289

real

76

2:35:58

8:53

11:00

1:57:36 2 wrong tries

2:27:58

1:48:04

--

有了昨天 Round 1B 的體驗
看完題目以後預期競爭勢必非常激烈
（雖然沒有昨天的嚴重）

比賽中途名次一度滑落至 800+ ...
中途超級絕望

慶幸還是很險地通過了

值得一提的是，題 B 的算法，我是分開兩個寫的：
Small input - 暴力 Exhaustion
Large input - 在最後 5 分鐘才想出算法，在最後 2分鐘 Submit...

在結果公佈的一刻... 終於放鬆下來...

再一次印證，能否堅持到最後一分鐘，結果可以非常不同
亦再次發現自己修練不足

• 題 A 是 Sub-Round 1A, 1B, 1C 之中最簡單，先傻了一會兒打 2DPoint 的 struct（汗），過了幾分鐘才發現不需，十多行 code 解決
• 看完 題B, C後 決定先攻 題B
• 對於 題 B，作了 Greedy+Search 的思維進路，但實踐後 "small set" 未能通過；然而相信自己的直觀：算法跟 "geometric ratio" 有關係；然後一直想了大約一個小時... ...
• 此時發現自己的排名滑落至 800+，難道今年的 GCJ 就此結束？
• 看見朋友們開始提交 C 的 "small set"；於是先寫 C 的 "small set"，寫代碼時卡了一會兒，憑藉 題目提供的 Illustration debug，提交並通過
• 深信 C 的 "large set" 不是自己能力範圍以內（不熟悉 data structure - Binary Indexed Tree... 汗），繼續向 searching 方向攻 題B
  ──後來發覺，利用 "small set" 的程序稍作修改（一句 staement），"large set" 可以在 130 sec 跑完
• 決定完全地暴力猛攻題 B，才發現對於 "small set" 而言，運行時間充足
• 題B 的真正算法... 時間一分一秒地過去... 依然想不出
• 至最後 5min，突然悟出 題B 的算法！（心跳加速，感覺腎上腺指數極速颮昇）
• 算法的方向大概是對了，大約是 log( log(L/P) /log(C) ) / log(2) ... ...不過有關 while loop 內應該用 < 還是 <= 很不清楚... 沒有時間冷靜下來想了... 心裏想著如果多給我 15min... 啊... 沒時間間了...！只好暴試！
• 在 cmd 狂打 I/O redirection 及 vimdiff... 調了一會... 終於通過了 small set... 在最後 2min 提交！
  

總觀今年 Round 1的題目
多數是不煩 code 的題
但考核的知識範圍挺廣

Binary Indexed Tree、DP + Counting、Nim、對數字的直觀感覺...

接下來的 Round 2... 將會是一場龍爭虎鬥
coding 一定要快（往年自己也是輸在間上...）
而且... 今次的比賽的場地，不是 自己家 或者 是 Lab 或 Office
加上那時候疲累的狀態，結果起碼會打個七折吧

所以，我決定先來一場預演...

(待續)

Google Codejam 2010 - Round 1B

雖然很不情願去記下今場賽事的慘況
未能入圍！

1242

real

56

2:06:19

16:22

-- 1 wrong try

--

--

1:35:29 1 wrong try

2:02:19

但，這年度的賽事還是應該記下來...

今場比賽 － 粗心 + 疲累

回顧整場比賽
0) 對，這場比賽的題目不太難
1) 如果 C 的 recurrence 沒有犯那個錯誤，多數能夠空出 >1 小時的時間去解決 B
（不過，以今場的狀態，大有可能在 Large case 栽在 overflow 手上...）
2) 如果 A 沒有犯那個低級錯誤，那這次比賽我就水過了...
（死了的原因，可能是 Submission Time 是 20:36 吧... 哈哈...）

1) + 2) 的「如果」都沒有發生... 可想而之今次的 粗心 或 狀態 都太差了...
就是題目都懂做，偏偏要犯的錯誤都犯了...

題A 做得比較笨
居然走去寫了樹
不過也不是寫了很久...
而且 small input 也通過了...

然後就趕快去下載 large input
在本機跑了一下... Runtime error ?
原來是 node 數目的上限想錯了...
debug了一下，消除了 RTE
看了頭 3 set data，貌似沒有問題
就 submit，趕快往下一題

── 但是，在 debug 時，我忘了在另一個相應的位置更改變數的值...
所以 large data set 就這樣掛了...