SRM 491 ※ Codeforces 47

[這篇 Entry 怨言居多... 慎入]

前排 ACM ICPC Regional 忙了一排... 現在還是很忙...-_-
── 最近我才意識到... 我只剩下不到兩個半月時間完成下一份 Research Project
但有 online contest 的話，我還是會盡力抽空去打
(縱使狀態不好, 仍盡量堅持打... 要習慣在狀態不好時 code...)

近來的 Online contest 都很不順利...

---

先是星期六晚 (1am) 的 SRM 491...
這場賽事題目很有意思... 我意思是題目對我來說很難...
雖然很多人提交 600 跟 900，但 sample 比較弱...
最後不少人被 Cha 或 Fail System Test
System Test 時有 "Problem"，本來說約有 10% 的 submission judge 錯了
後來等了兩三小時還未完成...

至Test 終於完成時
才聞說 Challenge Phase 臨近最後幾分鐘 Server 有事故
以致某些人的 Challenge 有問題...
至今(都兩三天了) Admin 還未做更新 Rating 與否的決定
(看來 Un-rated 的機會較大...)

>The match will be rated.
GOOD!!

---

剛才又 (12:20~2:20am) 參與了 Codeforces #47
這場比賽... 是比速度吧?

Register 的時候，要按下確認的單行訊息寫道(大意)：
「這次是 Alpha，請作出現問題的心理預備」

果然 Server 非常有問題... (# Registrants ~1000)
兩度延遲了開始時間 (15 min → 20 min)
題目也相當有問題... 比以往淺了很多...

A 和 B 跟以往不同... 不消五秒便會想出算法的題
貌似一些陰位也沒有 (以往題目起碼有一至兩個地方需要小心)
而 C 也很簡單... 稍為一想... 便能判斷可以用 Convex Hull 解...
(把 p[i] 上下左右的點 grid point 進去，做一次 convex hull，再貪心求最短的 length)
不過此題存在線性算法，詳見 rng_58 的 code (參下)
D 也是簡單... Binary Search + 概率 DP
不過做 D 時我白痴了... 自動 filter 了 "Fail" 這個字眼...
誤意為輸入是 Success 的 Probability，以致無意義地 "Debug" 了 15 分鐘...

Coding 中途 Server 亦一再 down...
最後是 E... 想了一會... 想出了一個很慢的算法...
在未有足夠優化的情況下通過 sample 並提交... 的時候
驚見比賽時間只剩下 17 second
按下 submit... 眼見 counter 倒數至 0 秒... 還在 loading
然後 webpage 上出現 "Contest is over" 的訊息
沒多半秒，終於 redirect 到下一頁，不過那是 "Server Down" 的訊息

(有點惱火... 不過後來氣也下了... 因為那段 source 是完全會 TLE 的)

這場 Codeforces 是以 "Codeforces format" 進行
賽後會有 System test, 才決定真正的 Rating...
不過也算了... 現時 Codeforces 主頁還是 "Server too busy"...
System Test... 大概在我睡之前還未完成吧...
System Test 極速完成... 看來又有機會是一場 unrated match......-.-

>So we decided to do it unrated.
OTZ....

按１：我居然被分配跟 Petr 同房
按２：同房中有一名參賽者題數比我少，但憑藉 15 Successful Hack 位高於我
以後我會注意：Hack 對於分數來說非常重要... 甚至比起速度還更加重要

---

最後貼下 rng_58 題C 的解 (不 highlight syntax了)：

int main(void){
    int N,i;
    
    scanf("%d",&N);
    REP(i,N) scanf("%d%d",&x[i],&y[i]);
    
    int maxx = -INF, maxy = -INF, maxs = -INF, maxd = -INF;
    int minx = INF, miny = INF, mins = INF, mind = INF;
    
    REP(i,N){
        maxx = max(maxx,x[i]+1);
        maxy = max(maxy,y[i]+1);
        maxs = max(maxs,x[i]+y[i]+1);
        maxd = max(maxd,x[i]-y[i]+1);
        minx = min(minx,x[i]-1);
        miny = min(miny,y[i]-1);
        mins = min(mins,x[i]+y[i]-1);
        mind = min(mind,x[i]-y[i]-1);
    }
    
    int ans = (maxx - minx + maxy - miny) * 2 - (maxx + maxy - maxs)
            - (mins - minx - miny) - (maxx - miny - maxd)
            - (mind - minx + maxy);
    cout << ans << endl;
    
    return 0;
}