IOI 2012

又一年 IOI, 今年的 scoreboard interface 挺不錯, 不過不能即時看題目, 增加了預測的難度 / 減低了食花生的趣味

- 香港隊取得 2 銀 2 銅, 雖然 rank 最高的只有 61, 不過整體計算的話是 2006 年後最好的一次

- tourist 只取得 588 分, 敗於另一位 600 分的選手, 有些可惜..

- 今年的題目難度回升, cutting 與 08' 相若 ~(350/250/150), 不知為甚麼這 3 個數字在很多年都差不多 (除了 09' - 11'). 在 09', 10' 變成了每 day 4 題, 但有 2 題是水的, 目的好像是為了減少 0 分的人數, 不過我覺得要這樣每天 1 條就夠了.. 尤其是 10', 不是水題的題目分辨性又不夠, 導致分數相當接近; 不過去年終於取消了這個設定

- Subtask 模式第 3 年使用, 雖然會增加同分的情況, 但是看來影響不大; 而且加上 full feedback, 不用擔心因 minor 的失誤損失大量分數, 可以 focus 在 algorithm 上, 在 IOI 程度的題目上大大提升了比賽的質素

- 題目的類型多樣化了, 很有趣, 今年的題目 6 條都很不錯

CodeForces Contest #138E - Planar Graph

Problem:
Given a simple biconnected planar graph G(V, E) with vertex position (x, y)
Process queries: given simple cycle C, answer how many vertices is inside C?

比賽時沒有人 solve
雖然好像有點過難, 但真是一道好題

解法和 flow 有關, 不過不是要搵 maxflow

任意選一個在 boundary 的 vertex s
由 s 向每個 vertex 都 send 一個 unit flow, 用 DFS 可以輕鬆做到

可以看出, C 入面 vertex 的數目 = (Flow entering C) - (Flow leaving C)
計算時, 只要對每個 vertex 的 neighbors sort by polar, 就可以用 partial sum 搵 flow value

一直看不出這題和 flow 有關, 真的大開眼界了

KTH Exchange 6

雖然 course 名是 communication complexity, 但是又會涉及其它 topic

例如昨天就講了經典的 Bipartite Testing
其精彩之處在於證明 G ε-far from bipartite → G_S detects it with high probability, S = random subset of vertex with size O~(1/ε)

愈來愈有味道了!

KTH Exchange 5: Farsta 宿舍

由於 Stockholm 市中心土地供不應求, 學校安排的宿舍位於離市中心 10km 的 Farsta
雖然到 KTH 差不多要 1 小時, 不過環境 cover 了這個問題

房間

Roomate 的房間, 波蘭人

窗外的景色

外面的海灘

步行 3 mins 就到的地方, 太誇張了..

整棟都被 KTH 租了

巴士站

KTH Exchange 4: IKEA

今天和兩個 CU 的同學到了全世界最大的 IKEA
此行除了購買必需品, 還有點朝聖的味道

位於市中心西南面的 IKEA, 面積差不多是香港最大那間 (@Megabox) 的 4 倍 !
入面餐廳的數量也有 4 間

本來只是想買被, 但不知不覺就買很多野了..
在入面待了 4 小時以上

開始明白家居佈置會影響心情和工作效率
生活在漫長的冬天的瑞典人想必深明此道理呢

巨大的貨倉

KTH Exchange 3: Farsta 購物

終於搬入真正的宿舍, 雖然離學校很遠但是環境一流
窗口出面只看見一大片樹, 一座建築也看不到
不過代價就是到 Farsta 市中心坐巴士也要 10mins

今天沒有堂上, 去了購買各種必需品
花了很多時間行超市, 發現真的很多東西都比香港便宜
看來瑞典物價高主要都是要人力的產品

今天的收獲

KTH Exchange 2

差不多來了 5 天, 不過還要在 hostel 待多 3 晚才有正式住所
7 晚 hostel 的費用幾乎 = 租 1 個月的宿舍費用
中途有一晚在不同的 hostel, 要把行李搬來搬去
不過這間 hostel 很強, 有 breakfast, kitchen, 很快的 wifi, 而且 share 的地方也很多

目前只上過 Applied linear optimization 和 Communication Complexity
前者應該會 drop, 經常和其它 course crash, 而且不是太有趣
後者是 PG course, 很刺激, 頭 2 堂的內容很容易明白, 不知後面會怎樣
lecturer 好像打算讓每個人負責打一週的 notes 作為其中一份功課, um...
這個 sem (這裏有 4 個 sem) 應該會上的 course 還有 Swedish 和 Photography
不知道和 326 是不是一樣, 所以可能 1 個 credit 也 trans 不到

簡單起見, 這幾天基本上都是三文治, 薯仔, 香腸等
去了超市數次, 其實有很多東西真的很便宜, 例如:

1L盒裝橙汁, 15SEK, 而且不是糖水的味道
1L盒裝牛奶, 12SEK
薯仔, 一袋也不用 10SEK

還有最棒的, 急凍三文魚柳 4 塊也只是 50SEK!
煙三文魚和魚子醬也好像也挻便宜

這幾天放學後都徒步在 stockholm 走, 好像主要的遊客區都已經 cover 了
最大的感想是如果來旅遊的話一定要夏天來, 要有藍天白雲才靚的
這兩天又多雲又下雨, 不適合觀光之餘又大風