ChengDu 2007
D: simulation by whhJ: 簡單題 by whh
B: AP by gg
- 其實很早就寫完, 不過沒發現伏, 花了點時間把所有情況想清楚
H: 1999題 by faifai
A: partial sum by whh
C: dp on tree by gg
- 寫得很差, 想漏一些東西導至 code 得很複雜 -> debug 困難, 之後重做短了 40 多行
F: state dp by whh
- 好像是插頭 dp, 錯了很多次, 懷疑有比較簡單的做法
E: by gg + faifai
- 和 faifai 討論了一下, 發現原來看穿了就很簡單, 我負責 RMQ 的部份, TLE, 發現可以很簡單地用類似 histogram 的方法降至線性, WA 了幾次後發現是 LL 的問題, 最後 293 + 4 過了
I: 見此
G: 原來用 A* 就可以, check 的時侯只考慮有機會 intersect 的 rectangle
Kuala Lumpur 2010
很難得的接近full team打.. (3人出席時間加起來應該有13小時, 好像是開學以來最多的一次..)就扮真比賽記錄吧
開始 whh 負責打template, 我分題目, 發現把很多題目都分了給ff. 不久 ff 發現簡單的 B, 瞬切. 我看的 I 很像 Jakarta 的 B, 很快便推到式, 在 ff 做完後便接著做, 過不到 sample, 先給 whh 做 H (因為忘了 output test case number 錯了一棍), 很快找到 bug, 改之, WA 後發現把 test case 數目看成 input size 了.. 改好便過了第 3 題, 暫居榜首 (好像是). 此時 ff 寫 D, 我手上有 F (grid, 可能是 BFS), G + J (geom), 同時 whh 問我 C 是不是很熟面口, 一看發現竟是我 211 project 的題目! 不過由於有太多題目在手加上 whh 好像沒有其它題目做, 便把算法告訴他由他來想細節, 等自己可以專心做我負責的題目. 不久後 D 輕鬆 WA, 由於 debug 不能, ff 便改做好像較簡單的 A, 不過寫到一半又發現 trivial 的 greedy 好像有反例, 和他討論了一下又找不到方法解決. G 是 standard 的二分, 於是便搶先寫, 途中他們發現很多隊過 A, 便覺得應該可以頹做, 結果是可以的. 我的 G 也緊接著 A 過了. 之後好像是 whh 和 ff 交替寫 C 和 D, 突然發現 live archive 的題目和 official site 的 D 是不一樣的! (好似係minor difference), 改後仍是 WA, 而 C 就 AC 了, 便讓 whh 幫 ff 的 D debug, 我做 F (standard steiner tree, 比較麻煩的是 vertex 有 weight). 不久後成功過 D, 我的 F 則 WA, 不過可以用 machine 有效率地 debug, 很快便發現 vertex weight handle 錯了, 改+過之. 此時剩下一半時間和 2 題, 如果不是預先知道題目難度的話應該會覺得很大機會全清的. 分工是我做 J, whh 做 E, ff 則 2 邊協助, 和 ff 討論了一下, 很快便找到不是過 2 點的 case, 便想到一個很複雜的line rotate 算法. 不過 whh 好像對 E 沒有甚麼想法, 便問了一下他的意見, 他覺得過 1 點的話 line 是 fix 的, 我覺得合理, 也會易寫很多很多, 於是便開始寫. 不過也是寫得很差, rotation 的部份不長但花了很多時間, 過 sample 後好像己經是 260 了 (寫+debug 了一個時間..), WA 後發現 1 點的 case handle 錯了, 改後竟然得到 TLE, 便努力 opt rotation 的部份, 繼續 TLE, 最終發現 rotation 的 index 有點問題, 改之, 此時剩下數分鐘, 雖然只是 training 沒有緊張的感覺, 但在 297 時 AC 也是很興奮的
No comments:
Post a Comment