IOI 2011

今年 IOI 的 problem set 非常好, 難度適中又可以 split 開 top 的 contestant
在此打下題目的 brief solution, 其中 Elephant 是參巧 FHQ 的做法的

Updated - Elephant official solution
先把 N 隻大象分成 K 個區間, 每個區間儲著 N/K 隻大象
假設某區間有 p 隻大象 (0, 1, 2, .. p-1), 要儲存:
pos[i]: 大象 i 的位置
opt[i]: 對於這區間, cover 大象 {i, i+1, .., p-1} 最少用多少 camera
max[i]: 在 cover {i, i+1, .., p-1} 時, 最右的 camera cover 到最右的位置

有了這些 information, 可以在 O(K lg N) 搵到最少所需 camera, 做法是由最左的大象開始, 根據 max[i] 移動, 並 binary search 在下一個 (可以跳過幾個區間) 區間的位置, 再移動
每次 query 都要做, 總時間 O(MK lg N)

每次 update 最多只會影響 2 個區間, 可以用 binary search 找出是哪個區間
只要把受影響區間 O(N/K) recompute 就可以
方法是由右至左 construct, 總時間 O(M * (lg N + N/K))

但是, 區間的大象數目可能會變得不平均, 所以當一區間的大象數目跌至 0 或 升至 2N/K 就要把所有大象重新分區間
在整個 process 中最多只會重組 MK/N 次, 所以整個複雜度是 O(MK/N * N) = O(MK)

可以解得當 K = sqrt(N) 時達至最小值, 所以整個算法複雜度為 O(M * sqrt(N) * lg N)



Garden
用 edge 作為狀態, 建立一新 Graph. 由於行完每條 edge 後行下一條 edge 是固定的, 所以新 Graph 中的每一 vertex 都有一條 outgoing edge, 形成頂環樹
對於每一個 query, 計算每一個 node 對應的 start edge 走 G[i] 步後會到達哪條 edge, 一共是 O(M)
整個算法為 O(MQ)


Race
和 POJ 1741 頗相似, 做法是 Divide and Conquer on Tree
每次選 Center of Tree 作為 root, 用 O(N) 計算它所有 children 的距離和高度, 然後 O(N lg N) 考慮所有經過 root 的 path
Recursive 地計算它的 subtree, O(N lg N lg N)


Ricehub
首先注意到其中一個 center 一定是 hub 選址的其中一個 optimal solution
對於每一個 center, binary search 它可以 cover 的距離 (左右相同) 或 binary search 可以 cover 的 center 的數目

注意: 如果由左到右 sweep line 好像會有問題, 因為 left bound 並不是 monotonic increasing 的


Crocodile
由 exits 作為起點做 Dijkstra, 當一個 vertex 被第 2 條 edge reach 時才算是 visit 該 vertex


Parrots
81分做法: 原本的 array 可以看成一條長度為 8N 的 01 string, 只要傳送 1 的位置就可以
>81分: k 最小可以是多少? 其實傳送 kN 個 [0, 255] 的整數可以產生的可能性為 H(256, kN) = C(255+kN, 255)
Solve C(255+kN, 255) ≥ 255^N 可以解 k 約是 4.09 (N = 64)

這題的重點就是怎樣可以在有限時間, 空間內做 mapping.
我目前想到最好的方法是, 2 個數字為一組, 用 8 個數字, 傳送 14 次 (k = 7), 可以預先把所有可能性打表 ( H(8, 14) 個可能性 ), 就可以 efficient 做 mapping


Elephant
首先把問題變成一棵 Tree, 每一個 node 代表一個 position, 定義:
黑點: 每隻大象的位置都是一黑點, 它的 parent 為 position + L 的 node
白點: 它的 parent 為右面或同一位置中最近的 node
Root: 在 +INF 的地方

答案就是最左的 node 到 root 的 path 上黑點的數目
每一個 move 都可以拆分為 insert 和 delete

Delete(黑點): 把該 node 變成白點 (需要改 parent)
Insert(黑點): 在 position + L 建立一點白點, 作為它的 parent
Insert(白點): 把 parent 連到在它右面或同一位置最近的點, 黑點優先

注意: 一個 position 可以多於一點, 要避免白點形成 cycle

Implement 用到 2 個 data structure: 動態樹 (dynamic tree / link-cut tree) 和 Binary Search Tree

上海MS Intern V

無錫一日遊
第一次 5 個香港 intern 一起去玩, 選了個不遠而大家也沒去過的地方



早上七點出發, 九點抵達上海火車站, 買票比想像中複雜



高鐵, 買票的時侯要回鄉証, 幸好大家都帶了
買了企位 (其實是不是會搞到超載的..)



到達無錫, 經過多方洽談, 決定跟一些旅行社交易 (它提供交通和景點門票, 比正價平一點, 應該是從景點那裏抽佣)
一開始 whh, helic, tong 和我都很不行, 不過最後還是付了錢



三國城 - 為拍電影/電視劇而建的 (好似係)


坐船遊太湖, 架船下層冷氣的散熱口對正上層甲板, 咩設計來的 (o:


「水軍訓練營」- 途中 helic 跌左副眼鏡落去, 花左一番功夫先搵返


唔知做緊咩既演出



之後過隔離 - 水滸城, 其實都係差唔多



買了弓箭玩具



大家係度瘋狂買野(又幾抵), 最搞笑係入面檔檔賣既一樣 (o:


$5 騎馬影相



$10 玩射箭


根據計劃, 本來是去甚麼古鎮的, 不過被黑的司機說服了我們去甚麼動物園




動物園夜場 - 其實我地入去玩機動遊戲的
右圖的機動遊戲堅正
表演 - 無劇情可言, 不過有些 tricks 係第一次見


走既時侯大雨到hihi, 最後差唔多 11pm 先返到火車站, 發現無哂車
討論好唔好 book 間房過一晚, 最後決定搭 3am 的車回上海
找到間 24hr 麥當奴 hea, 玩超用腦 game & Italian





呢架火車由成都開來, 已經行左 30hr, 所以上到車成地垃圾



這算是中國「真正」的火車吧, 老老實實, 企個半鐘已經差示多是我的接受極限



回到上海, 搵左間中式快餐店食早餐




統計支出

項目	支出(RMB)
教師之家->上海火車站	7
早餐	10
高鐵	60
無錫火車站->三國城	2
三國城+水滸城+太湖遊船	120
7-up	4
午餐	19
木弓玩具	10
果粒橙	5
射箭	10
水滸城->動物園	15
動物園夜場	65
雨衣(share)	1
晚餐	36
動物園->無錫火車站	1.2
支裝紅茶	5
麥當奴(share)	4.8
K車 (無錫->上海)	20
早餐	10
上海火車站->教師之家	7

一共用了 412 RMB

上海MS Intern IV

先簡單說說工作: 在 team 上主要是做一些輔助的 tools, 差不多做好一個 project 了, 聽說做完後要 present 呢

近來都是星期六玩一整天, 然後星期日則睡到下午, 在黃昏踩單車去不同的餐館吃飯 (其實是因為來上海後每星期六晚上都有比賽, 所以都很遲睡)
上星期六跟團去了蘇州, 不過印象不是很深刻, 始終比較喜歡自己 plan 行程而不是跟團

然後就講下晚上娛樂啦

遊戲
其實Braid不是來上海才玩的, 不過也一拼記下吧
Braid: 和時間有關的遊戲, 破關的難度不亞於做題目! 故事很深奧, search 了幾個網站才明白, 絕對稱得上經典
World of Goo: 物理遊戲, 有點像起橋, 但很多變化, 也當是解謎遊戲, 另外 soundtrack 很好聽

書
由於不遠的交大有間書店, 又有85折, 於是養成定期去買書的習慣, 目前在看東野圭吾的書
時生: 和 Back to the future 差不多, 沒甚麼驚喜
殺人之門: 不錯
單恋: 很喜歡故事的發展速度

不過其實成篇 blog 既重點, 就係我開始睇 Star Trek !
其實是在看 The Big Bang Theory 時, 入面的角式都很迷 Star Trek, 於是便看看, 發現真的很好看
上 wiki 一看, 發現有 11 集電影, 七月底前看得完嗎?

上海MS Intern III

單車大冒險!

由教師之家出發, 沿著龍吳路, 踩到徐匯區吃午飯
然後轉向東面, 在陸家浜一帶乘渡輪到對岸

過了岸便是在拆卸的世博, 發現演藝中心館變成了一個商場的地方
途中經過一間一年前吃過的餐廳, 感覺很特別, 一年前這裏還是十分熱鬧的地方, 現在變得很冷清

轉向東北, 踩到世紀公園, 發現好像要錢 (上海很多公園都要錢的) 和好像快關門, 便到科學館附近吃晚飯
最後沿著和原路差不多回教師之家

粗略估計今天踩了>7 小時, 主要問題唔係攰, 而係個單車坐位會令到屎忽好痛
同埋這裏的天文台預測今天陰天, 但結果是, 「說好的雲呢?」

晚上 SRM, 又做不到 500 了 (連續幾次做不到了..), 不過 250 危機四伏, 順利地 cha 掉 3 個
第一次覺得 challenging phase 太短 :p