COCI Contest 3 + SRM 527

COCI 2011/12 Contest 3: 10pm - 1am
SRM 527: 1am - 2.30am

就係咁, 連續打左 4 小時 code..

COCI:
除了 q6 其它基本上都立即想到做法
q2 題目寫得很差, 最後要靠估的
q3 第一次做 dice 題, 沒有經驗 hard code 這些東西, 寫得不是太好
q4 用 lower_bound 解決之
q5 很 standard, 做法是 pre-order traverse 一次, 然後每個 operation 便可以轉化成 1D 的 range update, 再用 BIT 做之, 由於 N 很大所以用 iterative 的 DFS
q6 其實是要找最大的 'gap', 即最長的等待時間, 不過想不到怎樣很快找 gap, 最後嘗試水分不成功


SRM:
今次打得挺順利的.. 基本上很快便想到做法
275: 用 dp[x][y] = 處理了 node 1..x, cover 了 node 1..y 的 maximum score
475: 上至下, 左至右試 '?', 再用 bipartite matching verify 之

Rating: 2132 → 2241 :D

COCI 2010/2011 Contest 7

Q4 是給一個 N x N map, 每一格有高度
現在由起點出發, 經過所有 checkpoint(s) 並回到起點。目標是最小化沿途中 最高點 與 最低點 之差
N ≤ 50

雖然是 path, 但其實不用真的找條 "path" 出來, 只要想成找一棵 spanning tree
先枚舉 path 上允許的最低點, O(N²)
然後二分 path 上允許的最高點, O(lg N)
做 flood fill 檢查可行性, O(N²)


Q5 given 一個有向圖, 每個頂點的 out degree 不大於 1
然後有 Q 個操作, 每次可以
remove(x): 移除 x 的 outgoing edge
query(x): 問由 x 開始走, 最終會到達邊個 vertex, 如果是 cycle 就 report 有 cycle


看下去十分像 disjoint set, 但 disjoint set 不支援 delete, 不過支援就是 dynamic tree 了
個 trick 就是可以倒著做, 那 delete 就變成了 union
所以先把所有 operation 讀入, delete 的照 delete
然後以 operation 倒序 process, 就變成一般的 disjoint set 了

COCI 2010/2011 Contest 3

香港時間2200-0100..!
十分合適我的生理時鐘

Q1-Q4: 頹
Q5: 望下去很有趣, 直覺會想到
最後還是做到了, 方法大概是

計算的次序:
1: [1,1]
2: [1,2],[2,2]
3: [1,3],[2,3],[3,3]
4: [1,4],[2,4],[3,4],[4,4]
..

首先想到的是每一個range都儲著max和min
做到第i步時, 把a[i]和每一個range的max和min比較和update, 再把每一個range的(max-min)加落answer

但續個range計和update是O(N²), 所以運用了一個很trivial的fact:
(max[1]-min[1])+(max[2]-min[2])+...+(max[n]-min[n]) = (max[1]+max[2]+...+max[n])-(min[1]+min[2]+...+min[n])

即是, 每一步儲著兩條list: max list 和 min list
而這條list要support以下operation
1. Push(x) - change all elements smaller than x to x
2. Sum() - sum of all elements

然後就想到條list其實就是一條類似stack的東西, 而每一個entry儲著frequency和value, 其中value是increasing/decreasing的
每一次Push(x)就一直pop走大於x/小於x的entry, 並累計frequency, 最後push返落條list度, 途中maintain Sum
由於每一個entry只會入/出條stack一次, 所以整個算法為O(N)

Q6: 未想到, 暉好像想到, 其實這樣挺好的, 因為如果我們一隊的話便可以把所有題目solve了(想像)