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 到)