SRM 537

緊接著 COCI 的一場 SRM, 不過 COCI 最有趣的 Q5 又沒有做, 只做了純打字的 Q6
分到了除我以外只有一個紅色的 room, 形勢不錯

275
想不到甚麼很數學的方法做, 見 input 很細, 於是便轉向想較暴力的做法
易見只需考慮 [0, A*B] 內的數字, 把範圍縮至 40000 個
猜想: 如果 Y 的 possible values 是 finite 的, 那麼 Y ≤ 200

接近得到了一個只需試 40000 * 200 次的 algorithm
但還要快速解決以下問題:
Given integers x, y, z, 是否存在 non negative integer i, j 使得 xi + yj = z ?

如果 i, j 可負的話就很簡單
我的做法是使用 egcd 找出任意一組 (i, j), 同時找出最小的 di, dj 使得 (i + di, j - dj) 也是 solution
就可以判斷是否有 non negative integer solution

由於平時少做 number theory, 種種細節寫了很久 (中途還去了做 500)
最後只得 116 分

500
很快便看出應該對每個 bit 獨立地計算 probability, 然後就是很 standard 的 dp 了
在狀態不錯的情況下 10 分鐘內完成

975
只剩下 20 分鐘時開了 975, 第一感覺是和 Euler path 有關 (近來經常遇到)
再看下去很有 flow 的味道, 很快便想到是 circulation
這時只剩下 15 分鐘, 有很多細節未想, 明知不夠時間寫但又沒有其它事做所以還是試著寫
最後當然是不夠時間完成

Challenge Phase
Room 中只有一個人 submit 975, 立即開來看, 明顯不是用 flow 做
但要找出 counter example 又很不確定, 最後很慢地截出了一個 case, Challenge Succeed
整個 phase 只有 3-4 個 challenge attempt, 很平靜地過去了

System Test
275 Failed
一開始還以為 algorithm 出錯, 原來再一次開細 array
不過還是升了 rating, 歸功於那個 challenge

975 Revisited
整個問題可轉化為:
Given a directed muitigraph, find the longest trail such that each edge is visited at least once (and cannot use more than its multiplicity)

如果有一條符合條件的 trail, 接下來只要不斷找 positive augmenting cycle 就可以
但是做 circulation 時, 使用從 Phuket09 中學到的方法可以很優美 + efficient 地解決
在這條題目中, 更可以同時結合 lower bound flow 的方法解決之

Flow model:
Lets A[i][j] be the multiplicity of edge (i, j), add flow arcs:
S → j, capacity = A[i][j], cost = 0
i → T, capacity = A[i][j], cost = 0
j → i, capacity = A[i][j] - 1, cost = 1

然後 SPFA 解決之
(不過應該沒有可能在 contest time solve 到)

CodeForces Contest #51 E

題目: Given an undirected simple graph, count the numbers of length-5 cycle
|V| ≤ 700, time limit = 10s

看規模應該可以用 O(V³) 的方法 solve
Compute A⁵, A 為 G 的 adjacency matrix
所以 tr(A⁵) 便是 G 的 length-5 closed walk 的數目
但是想要的是 cycle, 所以要減去不是 cycle 的 length-5 closed walk
可以在 O(V³) 內 count 到

但是 time limit 還是很緊, 所以還要繼續優化
首先注意到 A^k 是 symmetric 的, 可以減少約一半的乘法數目
以及因為只用到 A⁵ 的 trace, 所以只需做 2 次的 full matrix multiplication

其實我的做法不是最好的, 看到有些人 consider A⁴
好處是 A⁴ 不需要使用 long long

CodeForces Contest #110 D

題目: http://codeforces.com/contest/156/problem/D

不難看出是數 spanning trees 的數目
處理本身已有的 edge, 先把 G 看成是一個個的 component, 入面是怎樣連接並不重要
得到一個 |C| 個 component 的 complete graph, 但是每個 component 都是有 weight 的

使用 Prüfer's sequence 的變種可以解決
把每棵 spanning tree map 成一條 |V|^(|C|-2) 的 sequence
(不是 1 : 1 mapping)

Spanning Tree → Sequence:
先把每個 component label 1, 2, .., |C|
每次選取 label 最小的 leaf, 寫下它連接的 vertex label, 然後 remove leaf component
直至剩下 2 個 component

過程中有些 information 是 lost 了的
remove leaf component 時, 並沒有記錄 edge 在 leaf component 是連接哪個 vertex
以及最後剩下兩個 component 相連的 edge 的連接方法

所以每條 sequence 其實對應著 Π|c_i| 棵 spanning tree

Sequence → Spanning Tree:
雖然每條 sequence 並不對應唯一的 spanning tree, 但是使用原本的方法也必定可以還原出一棵 "不確定的" spanning tree
所謂的不確定就是上面所說的 Π|c_i|

所以答案是 |V|^(|C|-2) * Π|c_i|