網頁

Monday 29 October 2012

KTH Exchange 19: Vaxholm

夏令時間結束, 4pm 不到便日落
今天像是秋天最後的陽光, 難得地放晴, 據預報未來一星期都下雨
Vaxholm, 位於市中心東北方的小島






戲院
一天只放一場
在地上撿了個蘋果吃, 雖然沒有清洗但鮮甜到不得了


住在這裏真是爽
總有一間係附近

Sunday 28 October 2012

KTH Exchange 18: Drottningholm

Stockholm 有一個國王島, 亦有一個皇后島
後者有個皇宫, 其花園對公眾開放
交通很方便, 在 brommaplan 轉巴士很快便到達

碼頭
瑞典的好處就是只要一開離市區就是大自然

皇宮
皇宮全貌
前天的殘雪
冬天來了

結了一層冰的河, 大約 1cm 厚
不知道全條河結冰後牠們怎辦..
回程時剛好交接
Album: Click me

Saturday 27 October 2012

KTH Exchange 17: Systembolaget

在瑞典, 超市最高只能賣 3.5% alc 的啤酒
其它就要去國營的 Systembolaget 買, 而且要 20 歲
飲了兩個月的啤酒, 很想念紅白酒, 今左終於去了 Systembolaget



星期五的傍晚 Systembolaget 可用人山人海去形容, 平時在超市都沒有這麼多人..
人人都推著整車的酒, 很誇張
價錢方面, 以啤酒為例
同一牌子 500ml 啤酒, 2.8% 3kr 一罐, 3.5% 6kr 一罐, 5% 12kr 一罐
最平的啤酒也要 10kr, 很貴
但紅酒和白酒就很正常, 70-100kr 一支
由於不懂揀, 所以就花了 10mins 觀察哪些比較多人買, 然後跟風
和這裏的名海產凍蝦真是完美配合 :D

Friday 26 October 2012

KTH Exchange 16: 初雪

下雪了!
因為 CF 的關係, 差不多 9pm 才離開 KTH
一踏出室外, 立即有一陣白色小片灑下來, 因為光線不足, 一開始還不確定是雪
由於趕車的關係, 沒有留下來慢慢欣賞
不過在 Gamla stan 轉車的時侯, 月台有一部份沒有遮蓋
發現有幾個人也拿出手機拍照, 一臉興奮的樣子 (好像都不是本地人)


回到 Farsta 發現雪停了, 雖然只下了短短一小時, 風景看上去卻截然不同

想不到初雪在十月呢

Wednesday 24 October 2012

KTH Exchange 15

終於開了銀行户口, 據聞是少數給留不夠 1 年的人開户口的銀行
這間銀行每天只開到 3pm, 很早關門吧
遲了出門口, 然後 Murphy's law 又一次出現, tunnelbana red line 有一部份停駛, 而且我想去的站又剛好在那條線上
於是只好搭到 Hötorget 下車跑過去, 剛好趕上

趁著好天, 到處走走
Stockholm library
很壯觀的圓形書架
音樂廳
頒發諾貝爾獎的地方, 很平民化吧
門前是市集, 有些人坐在音樂廳門口喝啤酒

Kungsgården
回到 Farsta, 到 coop 一看, 發現很平的鮭魚


1kg 大約 90hkd
可以連續吃幾天北歐鮭魚了

Monday 22 October 2012

KTH Exchange 14

為了打 CF, 史無前例地 9am 前就起身了, 不過最後炒了
有一題用 suffix array TLE 了, 用了一個下午把 DC3 寫好, 即使有 source 還是搞了一大輪.. 太多細節了
雖然用了 DC3 還是 TLE (因為之後還有一步 n lg n, 而題目有 linear 的做法), 不過 DC3 真是小明的速度

看起來很完美的校園, 但其實..


自從九月開始有這種景色的日子少得不能再少, 大部份都是陰天或下雨, 這種圖片根本就像用來騙人的 demo 版
不過據預報本週放晴, 是時侯 plan trip 了

Sunday 21 October 2012

KTH Exchange 13

氣溫回暖至 10°C, 有十位數字已經算是溫暖
不過整個星期都是陰天 + 下雨, 十分頹廢
雖然是 exam week, 不過 take 的 course 都沒有 exam, 這個星期主要都是做 comm cplx 的 asg
今次的 asg 不少是關於 information theory 的題.. entropy, mutual information 等等, 之前完全沒有學過, 花了不少時間參透, 不過總算完成大部份的題目
據天氣預報下個週末終於有太陽! 終於明白為甚麼說瑞典人喜歡夏天..

Tuesday 16 October 2012

KTH Exchange 12: 玩火的女孩

<龍紋身的女孩>的續集 (一共三集)
今集的背景主要都是在 Stockholm, 不少小說中出現的地方都是熟悉地方
有一次在 metro 看的時侯故事剛好提及身處的那個站, 很有趣

愈來愈多食物的細節.. 根本是作者自己的日常習慣吧!!!
節錄其中兩段:
莎蘭德順道去7-11買了一個星期的食物:一包超大包裝的比利牌厚皮比薩、三份冷凍煙烤魚肉、三塊培根派、一公斤蘋果、兩條麵包、半公斤奶酪、牛奶、咖啡、一條萬寶路淡煙和晚報。
冰箱裡有一罐開過的牛奶、一些乾酪、奶油、魚子醬和剩下半罐的醃小黃瓜。廚房櫥櫃內放了四瓶半空的維他命、茶包、普通咖啡機用的咖啡、兩條麵包和一包薄脆餅乾。廚房餐桌上擺了一缽蘋果。冷凍庫裡有三塊火腿派和一份煙烤魚肉。

Sunday 14 October 2012

KTH Exchange 11: Sigtuna

終於等到好天氣, 上次好天氣又剛好是 NCPC..
Sigtuna, 據聞是瑞典最古老的小鎮, 位於 Stockholm 以北 50km
不過可以搭 commuter train 到達, 即是用 monthly pass 就可以, 不用額外付錢
轉了三次車, 花了兩小時終於來到這個小鎮


可是到達不久便下雨, 不過只下了一段短時間, 還出現了彩虹


小鎮不大, 但風景優美, 環境寧靜
大街
Cafe





小型圖書館



Album link: Click me

Thursday 11 October 2012

KTH Exchange 10: Raggmunk

說到瑞典的食物, 很多人都會想起肉丸吧
的確, 以 重量/價錢 的話, 肉丸好像是肉類之中很平的
從超市買回來隨便弄熱就可以吃, 所以我現在都叫它做「頹廢肉丸」

無意中發現另一樣「瑞典食物」— Raggmunk, 其實也就是薯餅
材料主要是薯仔, 牛奶, 麵粉等, 基本上就是在瑞典特別平的東西 (比香港還要平)

製成品:






















味道雖平淡, 不過實在適合在天寒地凍時吃, 非常飽肚

Wednesday 10 October 2012

KTH Exchange 9

近來發生了不少興奮的事:
  • Communication Complexity 的 assignment 2 grade 了, 竟然得到 180/200! 扣分竟然是來自本來很有信心的一題:
    假設 Alice 和 Bob 各自有一 n bit binary integer, 求一個 randomized communication protocol 去比較誰的 integer 比較大, fail probability < 1/2
    我做到需要 communicate O(log2n) bit, 不過因為可以做到 O(log n), 現在仍未想到

  • CodeForces 第一次第一 (雖然是 D2, 而且題目都很 standard)
  • NCPC 得到 KTH ACM coach 的注意, 以後應該會參加他們的 training
  • 這個週末終於有太陽了! (連續三星期都陰天)

Monday 8 October 2012

NCPC 2012


NCPC - Nordic Collegiate Programming Contest, 北歐四國之間的比賽, 亦是 NWERC 的預賽
這個比賽任何人都可以參加, 即使不是 KTH 學生也可以
雖然是 team match, 不過因為未認識其它人, 加上可以挑戰一下, 所以決定單挑

Scoreboard: https://ncpc12.contest.scrool.se/standings/?filter=1

=== 比賽過程 ===

A - compare 2 條 string 的 length, 超級大水題
D - 我用 dp 做, 其實有更簡單的做法, 不過沒有時間想得深入, 反正 coding 的時間不會差太多
J - dp on tree, 錯了一棍; 又其實有簡單的 greedy, 不過不明顯
C - maintain median, HKOJ 做過
B - 試了幾個 case 確定和 inversions 有關, 果斷 code
G - geometry, 看下去有點難, 不過仔細想後便看出重點, 錯了一棍
K - 2-SAT

之後看 F, 有點像 undirected postman 的變種, |V| 很小
比賽提供午餐, 到出面的 corridor 一邊吃一邊想
undirected chinese postman 可以用 weighted general graph matching 解之, 不過 |V| 很小, 應該可以用暴力做這一步
覺得這個方向正確, 吃完後便開始寫

錯了一棍後發現 disconnected 的 case 有問題, 便想辦法 fix
搞了一大輪後還是過不到, 於是看其它題目:
E - shortest path, 同時要 minimize turining angle 之類
I - 有點煩膠的 searching
J - 行李帶

E 好像很難 (事後發現看錯重點, 原來是要 minimize max 而不是 minimize sum)
I, J 都有機會
開始寫 I, 有點煩, 幸好一棍過了, 剩下大半小時
然後想 J, 應該是把有問題的 time interval 起出來
不過寫來寫去也有問題, 到最後 15 mins 時放棄再去改改 F 的 code 怒隊, 最後也是 WA

=== 完場 ===

最後得到第二, 輸了給 Omogen Heap
發現原來第一和第三都是由 今年瑞典 IOI team 組成的 [Shock]
最勁那個今年 IOI 金獎, 又有玩 IMO, 今日比賽單挑第三
餘下三人組成一 team, 今日比賽第一
現在的中學生真屈機 [adore]

發現 E 看錯了, 很可惜, 如果沒看錯的話一定做到
單挑 5hr ICPC 好像還是第一次, 和 team 的打法很不同:
- 只有 1 個人看題目, 要快速選題, 最好是參巧 scoreboard
- Coding 準碓度要求高, 因為不能一邊 debug 一邊由 teammate 做另一條
- 卡題會很嚴重
- 看錯題目機會增加
- 最後 2hr 會很累, 是時侯訓練體能嗎?

Wednesday 3 October 2012

KTH Exchange 8: 龍紋身的女孩

到瑞典當然要看瑞典小說
在瑞典文中書名是「憎恨女人的男人」, 似乎更貼合主題
劇情一早就在電影看過, 不過小說有很多有趣的地方, 我在其它書沒有見過的
小說經常會描寫一些日常起居生活, 例如八點起床, 工作至中午, 吃了甚麼, 下午到咖啡店, 超市關門前去購物等等, 而且不止一次
有點像小學生的日記記錄一個平常天的起居飲食
可能因為現在要自己煮食, 看的時侯會留意小說中出現的食物.. 發現單是食物就佔這本書不少篇幅, 很有趣
其實把這些刪去都不會影響劇情, 不過作者把它們寫了下來是為甚麼呢? 是因為瑞典人著重起居生活嗎?
這個 blog 因此而研究開面三文治呢

SRM 556 - OldBridges

Problem: given undirected graph G, each edge has capacity 2 or INF, determine if there is a multi-commodity flow:

(SA → TA) with flow at least 2CA
(SB → TB) with flow at least 2CB

做法很簡單, 要求兩次 maxflow
Notation: (u, v, c) = edge from u to v with capacity c

Flow 1: Add edge (S, SA, 2CA), (S, SB, 2CB), (TA, T, 2CA), (TBT, 2CB)
Flow 2: Add edge (S, SA, 2CA), (S, TB, 2CB), (TA, T, 2CA), (SBT, 2CB)

如果 F1, F2 的 S-T maxflow 都至少有 2(CA+CB), 就 output Yes, 否則 No
不難看出這是 necessary condition, 但這是 sufficient condition 就很不明顯

首先, 由於所有 capacity 都是雙數, 必存在其中一個 maxflow 所有 edge 的流量都是雙數

Let FA = (F1 + F2) / 2
在 F中, S的流入量為 2CA, T的流出量為 2CA; SB, TB 的剩流為 0
而且滿足流量限制, 所以滿足第一個 flow
相似地, FB  = (F1 - F2) / 2 滿足第二個 flow

Let F = FA + FB
但 F 可能會有些 edge 的流量超出 capacity, 不滿足流量限制
可以證明是不會的
注意要對 flow value 加上 absolute value
因為在 F 中, 可以同時存在 (u, v) 及 (v, u) 的 flow, 而且不像一般 flow, 是不能 cancel out 的

|Flow(e)| = |Flow(FA(e))| + |Flow(FB(e))|
= |F1(e) + F2(e)| / 2 + |F1(e) - F2(e)| / 2
≤ max(|F1(e)|, |F2(e)|)
≤ Capacity(e)

原題解: http://apps.topcoder.com/wiki/display/tc/SRM+556

Monday 1 October 2012

KTH Exchange 7: 回收


在超市會有這些回收機, 把特定的空罐 / 膠樽放進去可以退回 1-2 kr
不過不是所有空罐 / 膠樽都可以, 估計是瑞典生產的才可以, 部機入面是有 barcode scanner 的
每天飲的頹啤酒 4kr 一罐, 但可以退回 1kr, 即是 25%
其實這個設計概念不錯, 可以鼓勵人變得環保