Team Training 19/9/2011, 21/9/2011, 26/9/2011

South America 2008

F: 極頹 by whh (6)
C: 頹 by whh (17)
G: 頹 by gg (41)
A: shortest path by gg (69)
- 起點做一次, 終點做一次, 然後再起點做一次
K: ad hoc by gg (85 + 3WA)
- 只試 Sum 的 factor, 可以 check remainder, 我的做法是 simulate 走圈的 process
E: 日期題 by whh (91 + 3WA)
I: euler path by gg (162 + 2WA)
- 顏色為 vertex, 城市為 edge, check 能否成為 starting edge 首先要連著 odd degree vertex (如有), 和 remove 後會不會做成 edge disconnection
J: simulation by whh (199 + 2WA)
D: dp by gg (195 + 1TLE + 1WA)
- 一開始使用 O(N² * K) 的 dp, 之後再做使用 2 個 dp array 可以降到 O(N²)

B: 數學題, 好像是做 factorizing by whh

Hangzhou 2010

H: 簡單題 by whh (17)
B: 二分 + 類似 TSP 的 dp by gg (67)
J: KMP + dp (94)
C: 唔知係咩題 by whh (114 + 1)
F: CG + convex hull by gg (130)
D: 五子棋(201 + 1)
- 做法是找+數 winning position

G: AP + LCA, 雖然上年聽 joe 講過, 但寫的時侯還是遇到很多問題, 最後做法是 tree node = BCC + AP

Seoul 2009

A: 簡單題 by whh (17)
F: 最遠點對, 但沒有看到題目中要來自不同正方形的限制, 水過的 by gg (71)
B: by whh (109 + 2)
D: maximum subsequence average by gg (141 + 7WA)
- 做法有很多, 二分/迭代/凸包, 一開始寫二分 WA, 應該是精度問題, 最後過的版本是迭代 + 沒有用 floating point
E: Josephus by whh (217)
H: disjoint set + BIT by gg (241 + 2WA)
C: greedy by faifai, implement by gg (273 + 7WA)
- 一開始覺得是簡單的 greedy, 但又想不到, 看明 faifai RE 的 code 後再寫
I: probability by whh, 題目 1999 又長 (284)

J: 竟然看漏了一重要部份, 之後可以輕鬆 dfs 解決, 處理同位置的點用了一個巧妙的方法, 把距離都是 d 的點加上距離為 2d 的限制