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 小時以上

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

巨大的貨倉