All-Ukrainian School Olympiad in Informatics 2011

ACM style, 以下是我做題的順序

E. Points

利用

可以快速計算, O(N) 時間, O(1) 空間

D. Plus and xor

考慮 B 的每一個 bit (由 MSB 到 LSB), 如果是 1, 則 X 和 Y 的那一個 bit 必定有一個是 1 另一個是 0, 那當然把 1 assign 給 X
如果 B 的那個 bit 是 0, 則計算如果 X 和 Y 的那一 bit 均為 0 的話 X+Y 是否能 ≥ A

留意

if (X + Y > A)

會 overflow

A. Gift

一開始以為對 gold 做 ternary search 可行, 但 WA 後便發現很容易作出反例..
之後想想有甚麼必定正確的做法:

首先 sort gold, silver 的可能值
然後用 2 支 pointer, 一支在 gold 的最前, 另一支在 silver 的最尾, 做 sliding
但是由於每次 check connectivity 要 O(E), 整個 algorithm 是 O(E²)

後來想到了 http://poj.org/problem?id=2838, 也就是 maintain 著一棵 tree, 而不是一個 graph
簡單來說, 每次 insert 一條 edge 時, 如果形成環的話, 可以 delete 環上的一條 edge 而不影響連通性
在這條題目中, delete 的便是 silver 最大的那條 edge 了

由於邊的數目最多為 V-1, 每次 check connectivity 只要 O(V), 於是 total time = O(VE)

B. Mice

這條理論上比 A 簡單
首先把只有一個選擇的 mice 所選的 cheese mark 上時間截
然後對於剩下的 mice, 可以 greedy 的決定去左邊還是右邊

F. Tourist

看到這類題目通常都是先把 equation 寫出來, 例如去完 event i 後能去 event j 的話, 必需滿足

T_i ≥ T_j + X_j - X_i (假設 X_j ≥ X_i)

然後移項, i 歸 i, j 歸 j

T_i + X_i ≥ T_j + X_j

然後, 可以證明到, 只要滿足 (1) 和 (2),

Ti + Xi ≥ Tj + Xj    (1)
Ti - Xi ≥ Tj - Xj    (2)

是去完 event i 後能去 event j 的充份條件
之後, 便可把問題轉化為在 2D plane 上找最長不下降線段

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 了

CodeForces Contest #70 D

題目要求 maintain 一 set 點的 convex hull, 有 2 種 operation:
1. add(x): 把 x 加進 S 中
2. query(x): 問 x 是否在 S 的 convex hull 內



如果一點在 convex hull中, 以後都會在 convex hull中
具題做法是, 先找一點 convex hull 內的點 (我用的是最初 3 點的 CG), 以該點為 pivot point P

然後用一個 set 去 store 住 convex hull 上的點, key 是與 P 的 polar angle
對於新的點 x, 先找 x 在 S 中的左右兩點, 用 cross product 便可判斷是否在 convex hull 中

如果要把 x 加進 S 中, 先判斷 x 是否在 convex hull中, 如果不是, 只要對 x 左面和右面不斷 erase 形成反角的點 ; 否則 convex hull 不會改變



容易錯的地方
1. 兩點一樣的點 (以為題目說 input 沒有 2 點重覆, 原來只是保證 convex hull 沒有)
2. polar angle 相同
3. 和上面兩點有關, 就是在 set 中 insert(x), 但原來 x 已經存在, 之後 erase(x) 會把原本的點都刪埋
4. add(x) 前沒有 check x 是否在 convex hull 中

URAL 1691 - Algorithm Complexity

題目:
給出一個有向圖, 設 F(N) 為由 S->T 長度為 N 的 walk 的數目, 問是否存在一非負整數 k 和常數 C 使得 F(N) <= CN^k
Input: Graph, S, T
Output: k 的最小可能值


題解:
題目十分technical, 其實是說 S->T 的 walk 的數目是否能寫成 N 的多項式 (有點像big-O 的定義), 即 F(N) = O(N^k)
仔細想, 如果不能的話其實就是指數式, 即 F(N) = O(c^N)

在甚麼情況下會變成exponential呢? 首先想到的是如果每步都有多於1種選擇, 咁就變左c^k, 如 sample 2
然後又想甚麼情況才是N², N³ 等, 就會發現就是把 N 步「分配」到不同的環中, 即 C(N,M) = O(N^M)

所以, 先對圖做SCC
每個SCC可以分為數類:
1. 只有一個node
2. 一個簡單cycle
3. 以上皆否

明顯地, 如果S->T 能路過 type 3 的SCC, F(N) 就即刻變左 exponential
剩下的, 便是在縮點後的DAG中找 S->T 路過最多 type 2 的 path, 做 memorization dp 即可

怎樣判斷是type 2 還是 type 3 呢? 只要在該SCC中比較一下 |V| 和 |E|

還有URAL的stack size很細, 100000 個 node 做一次 dfs 都 stack overflow
解決方法: 我將由 1->n 改為 n->1 就過了..

小記

近幾次的 CF 的 SRM 都打得很差..