網頁

Thursday 26 July 2012

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

榨汁機