KTH Exchange 0: 北歐 exchange 去

將會去 KTH - 瑞典皇家工學院 exchange 一年

注意是瑞典, 不是瑞士

簡單來說就是 IKEA 的發源地, 而瑞士就是瑞士糖的產地 (好似唔係)

又或者就是 AOC 也有地圖 - 斯堪地那維亞, 即是北歐半島

Persistent Data Structure

其中一種 implement partially persistence binary tree (或 constant degree tree) 的方法結合了 fat node + path copying
可以做到
Time slowdown = O(1) (+ O(log N) for finding root)
Additional memory = O(1) per modification (amortized)

做法是, 原本的 node 變成可以儲著 2 個 version 的 fat node (多出的稱為 modification box)
Access 時, 比較想 access 的 version 和 modification box (如有) 的 time stamp 來決定使用哪一個
所以 access slowdown = O(1)

Modify 時, 如果未使用 modification box, 則把新 version 寫在 modification box
否則, 把新 version 寫在 branch 開的新 node 中, 然後使用 path copy 一路 cascade 上去

Memory complexity analysis:
設 d =最新 version 的 tree 中用了 modification box 的 node 的數量
每次 modify 時, 必定是最底的 k 個 node branch 開了新 node, 然後上面一個 node 寫了 modification box, 再上面的不變
即 d' = d - k + 1

由於 d 不可能小於 0, 每次 branch new node 會使 d 減 1
而每次 modify 會使 d 增加 1
即 M 次 modify 後, 最多只會 branch 開 M + O(1) 個 new node
均攤每次為 O(1)

References: http://en.wikipedia.org/wiki/Persistent_data_structure

Linear time Suffix Array Construction: DC3 算法

如果說 string matching 可以在 linear time 完成有點反直觀,
我覺得可以在 linear time construct Suffix Array 更加神奇

雖然很久以前已經有 linear time 做法, 不過好像都是先 build suffix tree 再 traverse
DC3 algorithm 是個簡單, 優美的算法, 而且還挺新的 (2003)
如果投票「十大最喜歡的算法」應該會有一席位

Step 1: 目標是對 suffix[x] 排序, x mod 3 = 1 or 2

設 s1 = suffix[1], s2 = suffix[2] (0 based)
如果 s1, s2 的長度不是 3 的倍數, 在最後補 0

然後每 3 個 character merge 成一個 tuple
使用 radix sort 計算它們的 rank (有機會相同)
假設沒有 ties 的情況出現, 則它們的 rank 便是這個 step 的目標

如果有 ties 出現, construct s' = r1 + 0 + r2
r1 和 r2 為那些 tuple 的 rank
然後 recursive 找出 s' 的 suffix array, 留意 s' 的長度為 2N/3

經過 step 1 後, 已有 information = suffix[x] 之間的相對排序 (x mod 3 = 1 or 2), 記為 R

Step 2: 目標是對 suffix[x] 排序, x mod 3 = 0

只要對每個 suffix[3i] construct tuple(s[3i], R[3i+1])
再使用 radix sort 便可

Step 3: merge step 1, 2 的結果!

最後一個 step
難處是比較 suffix[3i] 和 suffix[3j+1] 之類
但其實做法很簡單, 只要寫成

suffix[3i] = tuple(s[3i], R[3i+1])
suffix[3j+1] = tuple(s[3j+1], R[3j+2])

由於 R[3i+1] 和  R[3j+2] 可以直接比較, 問題迎刃而解
和 suffix[3j+2] compare 時方法相似, 不過是 3-tuple

DC3 算法的 time complexity:

T(N) = O(N) + T(2N/3)
T(N) = O(N)

References: Linear Work Suffix Array Construction

SRM 551

很久沒有打比賽後感

250 - code 完後才發現只能 swap adjacent pairs, 一直以為可以任意 swap
基本上整個做法完全不同, 浪費了 5 mins
最後得出 O(N⁵) 的做法, 可以加速至 O(n⁴) , 不過為了減低出錯機會選擇了前者
submit 後再試 case, 發現 for loop 的 bound 寫錯了, 要 resubmit

450 - 很明顯的 shortest path, 輕鬆解決

1000 - 只有 tourist 和 wata solve 到
假設數有多少種不同 count fruit 的可能性也不容易, 2ⁿ 太慢, dp 也不行
只能 split 開兩邊做 D&C, O(2^n/2 * n)
問題是要數 spanning tree 的數目, 而且有很多限制
想了很多方法戳式, 花了很多時間

臨完場 10mins 想到, 根本不用戳式, 而是可以 precompute 所有組合的 spanning tree 數目!
而且最多只有 n 個組合
連計算 determinant, 只要 O(n⁴)
剩下的便是 standard 的 slide pointer

250 太慢加上沒有 challenge, 不過 450 的高速挽回不少
rating 微升

VK Cup 2012

Day -2

整個下午在飛機上, 由於昨晚沒有睡, 大部份時間都睡了由於第二程是內陸機, 要先入境再 check in
然後按照 screen 上顯示的 gate number 等, 在某個時刻突然有一半的人起身走到別的地方, 不過沒有為意
平常起飛前 30 分鐘應該開始上機, 不過到了這個時間還未開始登機, 心想可能是 delay 吧 (網上說俄羅斯經常 delay)
差不多到了起飛的時間, 覺得有點不安於是到處看看, 結果就是發現錯失掉航班了

先回到機場大堂再決定下一步, 到了 Aeroflot 的 counter, 用了每人 4100RUB 得到了一張 10pm 的航班
雖然機票的問題解決了, 但是連帶的問題就是原先打算搭 Metro 到 hostel, 但現在到 Saint Petersburg Metro 己經關掉
也不知道去到 SPb 的換錢店關了沒有, 所以只好在莫斯科的機場換, 出乎意料地好的匯率

早早入禁區等, 發現 gate number 轉了又轉, 而且轉的時侯沒有廣播 (或者只有 Russian), 而且竟然轉了兩次!
幸好這次早有準備, 每隔十五分鐘便走去 check gate number
然後又 delay 了一小時

終於上到往 SPb 的飛機, 鬆了一回氣
到達 SPb 的時侯雖然已經 12 點, 但天色還未完全黑, 有利於搵路
由於是內陸機而且沒有寄艙, 由落機至步出離境大堂過程只是數分鐘

到了外面, 發現有一架巴士便毫不猶豫地上車 (據資料, 所有機場開出的巴士都同方向)
基本上完全沒有英文, 雖然也在預料之中
這一刻很有冒險的感覺: 凌晨時分在一個不熟悉, 沒有英文的地方坐上一架奇怪的巴士
到了總站 (好似係, 因為全部人落車), 便跟著下車

聖彼得堡的街頭, 非常闊的街道, 很有東歐味道的建築, 兩旁的商店都關了, 很有百廢待興的感覺
下了車, 不可能在這種時間找巴士吧, 只好轉搭的士, 雖然有點貴但發現基本上沒有其它方法

到了目的地後向別人問路, 那個人很熱心地打電話到 hostel 問又帶我們到那棟大樓 (這時我才知道 hostel 在某大樓的 5/F)
乘搭只塞得下 2 個人的電梯, 終於到 hostel, 很有成功感

Day -1

今天主要是在 SPb 徒步遊, 最值得說的便是到了 SPbSU ITMO 吧

Day 0

Arrival Day, 到了酒店發現了一團中國選手和 tourist
check in 後到了基督復活教堂, 由於下雨的關係提早回酒店

晚上是 welcoming dinner, 原來 VK 的 CEO 都好後生
之後是遊船河, 見識到 rng_58 有趣的一面

Day 1

早上是 practice session, 發現好像是第一次和大部份都比自己勁的人比賽 (IOI / ACM-WF 雖然勁人的人數更多, 但是比例上少很多)

一共 3 條題目
A 是很簡單的 dp, 不過也寫得不快
然後看 B, 應該不能短時間內解決, 開 C - 和 Euler Cycle 有關的題目
立即想到 disconnect, isolated vertex 等伏, 有機會取得大量 hack!
不過也寫了一段時間, submit 後發現 tourist 等高手已經早早開始 hack 人
submit 後發現沒有 handle vertex 1 = isolated vertex 的 case, 打算改的時侯比人 hack 了..

然後做 B, 不過 algorithm 有問題, 比賽前數分鐘被 hack 了, 就此完場

今天的重點是 AI 比賽, 要控制賽車去搶旗得分
有大約 3 小時寫, 不過用了 1 小時才熟習個 interface
晚上一邊吃飯一邊看比賽, 我的 AI 輕鬆慘敗

 

Day 2

Contest day, 大家貌似都不緊張, 輕鬆的氣氛濃厚
題目是 random order, dynamic scoring

看 C, 有點像 shy tortoise (雖然題意不一樣), 不過一看便知道是 dp
寫到一半的時侯發現好像有很多地方需要 hard code, 又想不到辦法不 hard code
由於每個 case 都要人手做, 嚴重拖慢了速度, 但這時轉題目又很不 optimal
過不到 sample, 看到 scoreboard 很多人做了 E, 於是跟大家隊
code 完後發現 assume 了 network 一定要 connected, 其實可以不用, 幸好不用改太多
做完 E 後再修改 C, 終於過了 pretest, 不過很不確定

然後做 B, 是 string + bitmask 的題目
雖然寫得不是太快, 不過感覺方向是正確的
不過因為 MLE 和忘了 delete debug message,多了 2 個錯棍..
(後來 dolphinagle 嘗試 hack 我, 因為用了 stl::map, 最差情況會有 26000000 次 access)
後來發現 worst case 用了 3.5s, time limit = 4s, 很險.. (很多人 TLE 了)
 最後半小時做 D, 基本上算法己經確定,可惜不夠時間處理細節

下午 SPb 半日遊, 又因為下雨的關係提早收工
晚上的 judging 沿用 ICPC-WF 的模式, 很刺激
B 的分數由完場的 500 升到 1000, 所以如果過 B 的話 rank 將會上升不少
最後 3 題全過, rank 18
tourist 的 A fail 了, 很可惜
冠軍由 sevenkplus 奪得
頒獎後突然宣佈每人都會有一部 notebook, 大家立即很興奮
比賽就這樣告一段落

Day 3

整天都下雨, 頹廢, 大部份時間在 coffee shop 睇小說 

Day 4

冬宮 - 隱士博物館
忘了取地圖, 不斷迷路
展品十分多, 即使不是很仔細看也可以看上一整日

Day 5

夏宮花園 + 軍事博物館
下雨關係, 搭 metro 回去
聖彼得堡的班次很密, 據聞 peak 時可以 30s 一班, 太強了

Day 6

在聖彼得堡機場, 又突然轉 gate 了, 懷疑到底有多少人因此而 miss flight...
莫斯科機場有免費 WIFI, 汽水機又有啤酒賣, 而且價錢也不算貴, 很不錯的機場

榨汁機