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 就這樣掛了...

PKU 3703 Intuition of Escape

題意：
二維場景內
給定一個 半徑 = R，位置 = (0,0) 的圓
及 N 個多邊形障礙物
問，是否在存一個移動方向，使得當圓形以直線前進時
不會觸碰這些障礙物

分析：
算法大約都是枚舉（離散的）移動方向/角度 - angle[M]
然後逐一判斷是否可行

有關「觸碰」的限制
雖然可以 ± Epsilon 處理
但這會令代碼變得噁心

Amritapuri 2009

今日係 Hussar (仲係成日唔記得點串) 第一次 training
(終於 sem 尾, 終於有時間 training!!)

turns out 結果唔錯 !!
喺俾題目「陰」
同埋冇武器 (其實今次唔洗用武器)
既情況下
做到 8 題
題數多過 on site champion (7 題)

---

約略講下 training
(我地冇詳細紀錄)

一開始 Joe (5 minute) 快速地 解決 F

佢 code 起後
我將 三條 題目講俾佢地聽
我又聽左 chin 一兩條題目

感覺 題目大部份都 do-able

(略吧.... 太支力了)

做到中途覺得題目既 range 好怪...
尤其係喺 Joe 提交 I 時 返回 Runtime Error...
嗯... N <= 105... Radius <= 109... 當 array 開大好多時... 冇更奇怪既係... 當你唔 assume radius <= 109 時, 先至過到 sample... 然後 Chin 做果條 H 又係咁... Answer must be <>= 1015...
甚至 >= 1000000...

好怪...

去到中段... 做左兩三左右...
卡左好耐...

對住 set 咁既題目... 又唔可以信佢啲 range...
好氣餒...

跟住無奈之下... 幫手 debug I...
ee? 搵到一個 bug : 三點共線, 但係兩點喺 center 既兩邊

(待續)

ICPC 4612 Fractal

[舊題重做]

題意：
給定 N 點定義 (上例 N = 4) 一條 polygonal line sequence
以此圖形作基礎作 D 層的分形
由起點至開始遍歷 d ( 0 <= d <= 1) 的部份 (d = 0: 起點; d = 1: 終點)

求終點座標

算法：
直接分治：
Point2D f(double d, int depth)

f ( d, depth ) --> f( d, depth + 1) ...

ACM ICPC World Finals 2010 - 大總結

這篇寫了很多天...

本來還想仔細 "執一執" 才發佈
可 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）