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
加上那時候疲累的狀態，結果起碼會打個七折吧

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

(待續)