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(log²n) bit, 不過因為可以做到 O(log n), 現在仍未想到
  
  
• CodeForces 第一次第一 (雖然是 D2, 而且題目都很 standard)

• NCPC 得到 KTH ACM coach 的注意, 以後應該會參加他們的 training
  

• 這個週末終於有太陽了! (連續三星期都陰天)

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 會很累, 是時侯訓練體能嗎?

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:

(S_A → T_A) with flow at least 2C_A
(S_B → T_B) with flow at least 2C_B

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

Flow 1: Add edge (S, S_A, 2C_A), (S, S_B, 2C_B), (T_A, T, 2C_A), (T_B, T, 2C_B)
Flow 2: Add edge (S, S_A, 2C_A), (S, T_B, 2C_B), (T_A, T, 2C_A), (S_B, T, 2C_B)

如果 F₁, F₂ 的 S-T maxflow 都至少有 2(C_A+C_B), 就 output Yes, 否則 No
不難看出這是 necessary condition, 但這是 sufficient condition 就很不明顯

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

Let F_A = (F₁ + F₂) / 2
在 F_A 中, S_A 的流入量為 2C_A, T_A 的流出量為 2C_A; S_B, T_B 的剩流為 0
而且滿足流量限制, 所以滿足第一個 flow
相似地, F_B  = (F₁ - F₂) / 2 滿足第二個 flow

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

|Flow(e)| = |Flow(F_A(e))| + |Flow(F_B(e))|
= |F₁(e) + F₂(e)| / 2 + |F₁(e) - F₂(e)| / 2
≤ max(|F₁(e)|, |F₂(e)|)
≤ Capacity(e)

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

KTH Exchange 7: 回收

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