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, 汽水機又有啤酒賣, 而且價錢也不算貴, 很不錯的機場

榨汁機

控制重力 - And Yet It Moves

最近玩了一幾有趣的 PC遊戲 - And Yet It Moves

基本上是 2D 的解謎遊戲, 特別之處在於可以控制重力方向 (上下左右)
(不禁想起那些經典的 BFS 練習題)

不難玩, 用了數個小時便玩完
不過每關也有新的元素, 所以不悶的

Trailer:

Sem 4 之後: 516 Project

由於去 world final 的關係, 逼不得而把 516 project 的 deadline 延後數日
topic 是 Graph Sparsifiers
一開始會選這個 topic 是覺得個 result 很強勁很神奇, 大約就是說
Given 一個任意的 weighted graph G, 可以 produce 一個 O(n/ε²) 條 edge 的 graph H, 而 H 是 G 的 ε-approximation

由於時間關係, 基本上只看了一篇 paper
一開始被整頁的運算, 公式嚇到
不過後來發現那些運算大多都是移項, 加加減減
真正難的地方在於對整個 proof 流程的理解
閉關了數個下午總算大致明白

做完後的感覺:
首先覺得個 proof 很神奇, 很多步都很有出 cheat 的感覺
對 linear algebra 又熟了一點
「知道 result」和「知道 proof」的分別就像睇戲和睇 behind the scene

CERC 2010 J - Justice for All

題目: Construct a bipartite graph with at most 200 vertex at each side that has exactly N (1 ≤ N ≤ 10⁶) perfect matching

如果想要一個有 k 個 perfect matching 的 graph, 可以使用 k 個 vertex construct 到
方法是 l[1] 連到 r[1], r[2].. r[k], 然後 l[i] 連到 r[1] 和 r[i]
fix 了 l[1] 的 match vertex 便 fix 了整個 matching

想要一個有 N 個 perfect matching 的 graph, 可以把 N factorize, 然後把上述的 subgraph disjoint union 一起
當然如果 N 有很大的 prime factor 便會使得 vertex 數目超出限制
既然 x 不足夠, 就要想方法去 implement + operation

例如, 把 N 分解成 Sum{2^m}
首先要 construct 一個有 2^m 個 perfect matching 的 connected subgraph
使用 m+1 個 vertex, 加上 edge {(l[i], r[j]): i ≤ m, j ≤ i+1}

為了做到 +, 我們希望每個 subgraph 都有兩種 'mode': 1 個 matching 以及 2^m 個 matching
並且每次有 exactly 一個 subgraph 是使用後者的 mode
因此, 便想到再新增一個 'control vertex'
一個 subgraph 的第 m+1 個 node match 到這個 control vertex 的話, 便可以有 2^m 個 matching
否則只有一種

因此, 只要在每個 subgraph 的 l[m+1] 連到 r[1] 及 control vertex
如果連到 control vertex 的話便可以有 2^m 個 matching
否則 l[i] 的 matching 數目便會 reduce 為 1 個
就可以砌到任意數目的 perfect matching

WF 2009 K - Suffix-Replacement Grammars

有趣的題目, 雖然其實不難不過挺 inspiring
Link: http://livearchive.onlinejudge.org/external/44/4455.pdf

解法

猜想: 只需考慮把 S 的 suffix 替換成某一條 rule 中的 string 的 string
一開始覺得每次做 replacement 前, current string 必定為 starting string 的 prefix + 某條 rule 為 suffix
但是很想便找到反例, 因為使用 production rule 的次序不一定按 increasing length order
例如
Goal: ABC → DEF
Rule:
BC → GH
H → I
AGI → DEF

於是, 便想到要把 string S transform 成 string T, 主要有兩種方法:
1. S → I₁ → I₂ → .. → T  (same length)
2. 對於每一個 S 與 T 的 common prefix, transform 餘下的 suffix

方法1 只要 shortest path 便可輕鬆解決
方法2 把問題 reduce 成 length 更小的 case, 所以只要由 length=1 開始便可以遞推上去

由於 constrains 不大加上已經是早上七時, 所以隨便寫了 Floyd-Warshall 和很多地方都沒 optimize
Execute 了差不多 30s (time limit = 36s)

答案上限

由於以前聽聞過, 答案是會 exceeds 32-bit integer 的所以避免了 (可能的) overflow 錯棍
但是上限是多少呢 ?
一開始以為是 100²⁰, 當然不是 tight 的

假設對 length 為 k 的 transform 的 rule 有 r_k 條 ( Sum{r_i} ≤ 100 )
假設 X, Y 為 length k 的 string, 若 X 能 transform 成 Y, 最多要做 MAX_k 次

所以, 得 MAX_k = MAX_k-1 * r_k
而且 MAX₁ = r₁
所以答案上限 = Product{r_i}

但也不是一眼看出即是多少, 2⁵⁰? 3³³?
使用 dp 可得最大約為 7.4 * 10¹⁵ (3³² * 4)