到瑞典當然要看瑞典小說
在瑞典文中書名是「憎恨女人的男人」, 似乎更貼合主題
劇情一早就在電影看過, 不過小說有很多有趣的地方, 我在其它書沒有見過的
小說經常會描寫一些日常起居生活, 例如八點起床, 工作至中午, 吃了甚麼, 下午到咖啡店, 超市關門前去購物等等, 而且不止一次
有點像小學生的日記記錄一個平常天的起居飲食
可能因為現在要自己煮食, 看的時侯會留意小說中出現的食物.. 發現單是食物就佔這本書不少篇幅, 很有趣
其實把這些刪去都不會影響劇情, 不過作者把它們寫了下來是為甚麼呢? 是因為瑞典人著重起居生活嗎?
這個 blog 因此而研究開面三文治呢
Wednesday, 3 October 2012
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), (TB, T, 2CB)
Flow 2: Add edge (S, SA, 2CA), (S, TB, 2CB), (TA, T, 2CA), (SB, T, 2CB)
如果 F1, F2 的 S-T maxflow 都至少有 2(CA+CB), 就 output Yes, 否則 No
不難看出這是 necessary condition, 但這是 sufficient condition 就很不明顯
首先, 由於所有 capacity 都是雙數, 必存在其中一個 maxflow 所有 edge 的流量都是雙數
Let FA = (F1 + F2) / 2
在 FA 中, SA 的流入量為 2CA, TA 的流出量為 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
(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), (TB, T, 2CB)
Flow 2: Add edge (S, SA, 2CA), (S, TB, 2CB), (TA, T, 2CA), (SB, T, 2CB)
如果 F1, F2 的 S-T maxflow 都至少有 2(CA+CB), 就 output Yes, 否則 No
不難看出這是 necessary condition, 但這是 sufficient condition 就很不明顯
首先, 由於所有 capacity 都是雙數, 必存在其中一個 maxflow 所有 edge 的流量都是雙數
Let FA = (F1 + F2) / 2
在 FA 中, SA 的流入量為 2CA, TA 的流出量為 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%
其實這個設計概念不錯, 可以鼓勵人變得環保
Friday, 28 September 2012
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 條都很不錯
Friday, 21 September 2012
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 有關, 真的大開眼界了
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 有關, 真的大開眼界了
Subscribe to:
Posts (Atom)