網頁

Wednesday 31 August 2011

SRM 516

悲劇呀..

250 很快便想到算法, 但寫了很久
500 看了兩次題目才明, 發現是很簡單的 greedy, 寫的速度還不錯
1000 由於 500 偏淺, 所以很有信心地把餘下的時間花在 1000, 交了個不覺得正確的解..

challenge phase, 1000 很快被 petr cha 了, 然後 petr 很強勢的從 rating 低至高逐個 cha 掉他們的 500..

之後便上不到網, 於是去睡覺

第二朝一早醒來, 上 profile 發現 rating 大跌, 心知不妙
入去看看, 發現 250 忘了 -'0', 500 greedy sort 的 < 寫成 > 了..

Sunday 28 August 2011

上海MS Intern VI

暑假駛入尾聲, 亦代表 intern 快要完結
下星期就要 final presentation 了, 不過現在還未整好 PowerPoint
總覺得之後會掛住 office, 雖然我也不知道為甚麼會有這種想法

繼無錫而後, 又去了蘇州, 黃山, 朱家角
本來想打遊記的不過因為太懶所以沒有打
上海市內則去了自然博物館, 美術館, 七寶, 還有數碼港安排的豪華一日遊
好像除了杭州以外, 應該要去的地方都去了

看了幾集 Star Trek 又覺得不及第一次看的好看, 於是便沒有看下去了
近排開始打機: 大航海時代4, 電車GO!
不過這個月晚上很多天都出去食晚飯, 回到酒店已經夜深

今天應該是這次 intern 最後一次到市區, 去了自然博物館, 行行了 N 次的南京路步行街
之後沿著南京西路到靜安寺
感覺上開始認得路了

還有數天就回香港, 其實我也沒有想家
在這裏住了快 3 個月總覺得有些不捨, 不過總覺得這想法很奇怪..

Tuesday 23 August 2011

SRM 515

250
一開始看錯了以為可以 rotate 任何角度, 到發現只能轉 30k 度時已經跌了>20分
最後 submit 時只剩下 18x

550
在 250 緩慢的情況下, 如果最後只做到 250 的話 ranking 一定很低
由於 550 估計只有大約 30% 機會做到, 所以開了 1000

1000
發現是 graph 題, 覺得有機會做到
做法是枚舉 F 和 R 的位置, 計算每一格到 F 和 R 的距離總和
然後再做一次 Dijkstra

結果 1000 過了, division 排第 6, 升了紅色
不過做到 1000 真的十分偶然, 首先題型要是自己擅長, 想到題解又要 code+debug 到
所以要長期保持紅色不能只靠這些偶然, 還是要穩定地做到 500

Monday 15 August 2011

URAL 1833 - Hopes of Rowing

題目可轉化為一堆 bonus[ai] + bonus[bi] ≥ k 的不等式
By 直覺, 一定存在一 optimal solution 其中 bonus[i] 為 k/2 的倍數 (0, k/2, k)
(其實好像可以 prove, 不過我不懂)

先假設上面的前題正確, 但是三種可能性很難處理, 所以先統一所有 bonus 都是 k/2, 那樣就只剩下兩種可能性
再轉化為 (其實這 step 不是這樣想出來的, 而是由 solution 推導出來):

bonus1[ai] + bonus2[bi] ≥ k/2
bonus1[bi] + bonus2[ai] ≥ k/2

其中 bonus1[i] 和 bonus2[i] 都是 0 或 k/2

把 (bonus1[ai], bonus2[bi]) 視為一條 edge, 會得到一 bipartite graph, 而且要做的其實就是 minimum vertex cover!

由 König's theorem 可知, 對於 bipartite graph, minimum vertex cover = maximum matching
所以之後只要做 matching 再找出 cut 便大功告成