網頁

Wednesday 28 September 2011

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(N2 * K) 的 dp, 之後再做使用 2 個 dp array 可以降到 O(N2)

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 的限制

Monday 26 September 2011

Petrozavodsk Summer 2011. USU Contest

好像是俄羅斯 IOI camp 的比賽 (好似係), 據聞難度十分高
見在 URAL 上舉行, 忍不住去玩

開始後不久見到有人過 J
首先想到 f(n) 可寫成一堆連續數的 Fibonacci 次方
如果有 f(n) 的質因數分解 form, 可以輕易找到答案

算法1 - 把 1~n 分解, 把每個數的質數加進 primes[] 中, N * sqrt(N)
submit test case 5 便 TLE..

算法2 - precompute 1~n 的質數, 分解時只試質數
submit - 還是 TLE..

算法3 - 分解一個數時, 只試質數, 再加上如果剩下的數是質數便 break
加上這個優化後 (%mod 變成 -mod 那些應該是一定要的) 終於過了..

之後做 D
如果 n = a*a*b, 那麼 a3 ≤ n 或 b3 ≤ n
所以只要試 n1/3 以內的數


K - KMP + DP
狀態是 dp[i][j] = 前 i 個 character, prefix 為 j 可以 match 到多少次
但 '?' 轉移時有些麻煩, 因為不能 greedy 地 match 下一個, 我的做法是不斷走 fail 更新, 理論上好像會達到 N3, 不過還是過了

CodeForces Contest #88

A - 慢..

B - 不熟悉的 game 題, 一開始沒甚麼頭緒, 發現 mod 很小, 便想到 O(mod) 的做法

C - 見到是 graph theory 又放在 C, 便覺得一定要做到, 用了一個邊割分的做法
Find(S: set of vertex){
    x = S[0]
    P = {y : x->y & y in S}
    Q = {y : y->x & y in S}
    Search edges(w, z) : (w in P, z in Q)
    Find(P)
    Find(Q)
}

想完覺得很優美, 以為用 vector 會很慢, 便用 array 模擬一個個 list, 寫起上來有點麻煩和冗長, 後來見到有人用 vector 也過了..

後來發現另一個(較簡潔)的做法: 先找任意一個 cycle, 之後可以簡單地找到 triangle

Friday 23 September 2011

CUHK CS Sem 3

好像很久沒打blog, 不知不覺原來己經開學 3 星期
生活主要也是圍繞在讀書和 ACM, 目前最想的便是去 exchange 和 WF, 己經報了 IELTS,

今個 sem 一共 take 了 5 個 course, 比大部份 yr2 CSers 少, 希望可以多一點睡眠時間和做題目吧

CSC313: 最喜歡的 course, 感覺就像去年 211 (更強烈), 會有種振撼的感覺. 經過 intern 和幾堂 lecture, 發現自己還是對理論的興趣比較大..
CSC315: 由於對 OS 沒有認識, 所以可以說會學到很多新東西. 不過興趣不大, 只希望快快搞掂 assignment
CSC316: 由於前面的 topics 都有一定的認識, 加上九半的關係目前還沒有上過堂, 不過看免費的 textbook 也很好, 去到後期應該會去上堂吧
CSC317: 沒特別感覺的一個 course, 感覺有點頹, 不知為甚麼到現在還沒有 quiz
CSC323: 上堂完全不知道學到甚麼, 目前除了那個 project 好像頗有趣外其它東西都是莫明奇妙的

其實打 blog 的動機是因為今天的 training 太興奮
今天主要是立志講 graph, 他列出的問題有一半都是沒有看過的, 大開眼界
例如 odd length shortest path, 總覺得應該是很經典會看過但就是沒有看過
心裏有一種很強烈想知道怎麼解的想法

還有 bipartite graph edge coloring, 雖然最後的做法不難, 但是能一步步 prove 出來都是很興奮的, 特別是又用回 211 的東西.. 原來看一個 proof 和自己想一個 proof 的感覺是差很遠的
有時對一些明明很理性的事物會有很感性的感覺, 很奇妙

Saturday 3 September 2011

URAL 1580 - Dean's Debts

首先 N 個 unknowns 至少要有 N 條 equations
多過 N 條的話只保留 linear independent 的
之後便聯想到一個 |V| = |E| 的 Graph, 即頂環樹

有一個頂環樹, 一定是從環的部份開始解
但是不是每種環都有唯一解, 要 odd cycle 才可以 (用 determinant 可以證明)
所以每個 connected component 要至少有一個 odd cycle 才有機會有唯一解

環的解可以綫性計算, 然後順著邊計算 tree node 的解
之後多餘的 edge 只要 check 是否 consistent 便可以

總時間 O(N+M)

Thursday 1 September 2011

上海MS Intern 遊玩一覽

六月
8: 人民廣場, 東川路晚飯
11: 徐家匯, 豫園
12: 科技館, 明珠塔
18: 人民廣場, 小肥羊
19: 吳徑, 交大
25: 余山
26: 單車

七月
2: 單車
3: 交大, 江川東路
9: 蘇州
10: 歐尚
15: 徐家匯豆撈
16-17: 無錫
23: 蘇州
24: IOI Day 1
30: 美術館, 人民廣場
31: 單車

八月
6-7: 黃山
13: 數碼港上海一日遊
14: 閔行公園
20: 七寶
21: 朱家角
27: 自然博物館, 靜安寺
28: 動物園, 上海體育館

上海MS Intern VII

晚上就要走了, 雖然沒有想家的感覺, 但總有點期待三個月離開香港再回去的那種感覺
但相對地不捨的感覺更多, 在這裏認識的人, 以後可能不會再見

第一次在外地生活這麼長時間, 回到香港說不定還要適應一下
再見閔行, 再見上海