CodeForces Contest #75

近來幾次 Codeforces 都出現 D 和 E 一樣分數的情況, 其實是對我有利的, 因為有機會懂得做的題目多了 -> 做到 D 或 E 的機會大了

E - 有 N 個 igloo, 在時間 = t 時, 第 i 個 igloo 的高度為 a_i + b_i * t . Queiries: 在時間 = t 時, output 第 x 個至第 y 個中最高的那個

看完題目, 最先想到的是:
1. 90% 可以用 segment tree
2. 可以把 queiries 按 t_i sort 好
3. 高度那 part 想起 Best Plan[1]

由於想要知道 [x..y] 中最高的那個, 因此 segment tree 上的每個 node 都儲著一條 queue, queue front 就是當前最高的那個 igloo
現在目標是對 [x..y] 中, 找出 sequence S, 使得一開始 S₁ 最高, 過一段時間後變成 S₂, 如此類推

一開始我按 b[i] 由小至大排, 再 remove 那些 a_i 比後面小的, 之後每次 query 只要睇下使唔使 pop queue front 便成, 不過過不到 pretest
之後發現假如有 3 個 igloo A, B, C, 會有機會出現以下情況:

(A > B > C) -> (C > A > B) -> (C > B > A)

即是, 在 B 超前 A 之前, C 已經超前 B
解法方法: 像做斜率優化 dp [2] 那樣, 要計算超前時間, 即是對於 A, B, C , 在 push C 入去時, 除了 check 是否好過 B, 也要 check 超前時間, 即 Cross(C, B) > Cross(B, A)




C - 一個 Graph, 每次 add 一條 edge, 問有多少種方法選取 edge set S, 使得 S 能拆分為數個 edge disjoint cycles

很多人做到 (雖然聽說和某 TC 題目相近 [3]), 不過又想不到怎樣做, 看完題解覺得很有趣

做法: 每次 add edge 時, check 條 edge 的兩端是否已經 connect (用 disjoint set), 如果是, 則把答案 x 2

不過最精彩的還是證明, 大約是這樣的:


把每一條 edge 寫成一支 1 x N 的 vector, 連接的點 = 1, 否則 = 0
例如 N = 5, 則把 edge (2, 5) 寫成 <0, 1, 0, 0, 1>

[Propeties] 如果有一 set vector 把它們 XOR 起來的結果是 0, 則乎合選取方法, 反之亦然
[Proof] 把它們 XOR 起來為 0 <==> 每個 node 的 degree 為偶數 <==> 存在 euler cycles

問題變為, 現在我們有一 set vector S, 有多少種選取 S 的 subset 方法使得 XOR 起來 = 0 ?
答案是 2^{|S| - rank(S)}

解釋: 先任意找出 S 的 basis, 對於不是在 basis 中的 vector, 可以任意選取 (2^{|S| - rank(S)} 種方法), 然後有 exactly 1 種方法在 basis 中選一些 edge 去補上乎合條件

所以, 每次 add 一條 edge, 只需看它的 vector 是不是和 S linear independent, 可以證明, 如果這 vector 和 S 是 linear dependent <==> 這條 edge 的兩端已經 connect



References:
[1] HKOI 2007 Junior
[2] http://www.topcoder.com/stat?c=problem_statement&pm=6779&rd=10002&rm=249950&cr=13358640
[3] POJ 3709

Official solution: http://www.codeforces.com/blog/entry/2179