網頁

Tuesday 28 August 2012

KTH Exchange 1: 抵步

好像做了很多事情的一天

瑞典用的貨幣是 kr, 1 kr ~= 1.16 hkd
不過為了心理著想, 當然會無條件捨棄 .16
高物價加上和 hkd 差不多是 1:1, 後果就是出現很多觸目驚心的數字

研究怎樣去市中心
Airport express, 4XX
找到最平的巴士也要 100
車程半小時, 不過有 WIFI, 很好

在 google map 的幫助下找到 hostel
很順利地 check-in
渣攤了一會便出發去 KTH

處理各種手續竟然異常地順利, 總覺得應該甚麼地方出錯了
拿到類似 CUSIS 的 acc 後, 發現下午有一課 Applied Linear Optimization
於是趕去上堂, 不過低估了找課室的難度

這不是 CS 而是數學的 course
幸好讀過 516 的強勁洗滌, 對了 linear algebra 半年
雖然今天的題目是 LP, 但內容大部份都未聽過, 不過也大致跟得上

下課後到超市視察
發現其實有很多東西都不貴, 和香港差不多 (pasta 等)
甚至比香港便宜 (薯仔, 牛奶等)
豬牛羊肉的價格就貴得驚人
不過網上推介去瑞典應該吃魚, 發現魚的價格相對便宜很多

今天活動的地方好像都是商業區一帶, 事實上沒有甚麼"瑞典"的感覺
計劃明天到更南的地方去

Sunday 26 August 2012

KTH Exchange 0: 北歐 exchange 去

將會去 KTH - 瑞典皇家工學院 exchange 一年
注意是瑞典, 不是瑞士
簡單來說就是 IKEA 的發源地, 而瑞士就是瑞士糖的產地 (好似唔係)

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

Monday 20 August 2012

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

Wednesday 8 August 2012

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

Sunday 5 August 2012

SRM 551

很久沒有打比賽後感

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

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

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

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

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