ICPC 2691 Evacuation Plan

本身在 poj 的「網絡流專項」見到的
不過 poj 近排的 special judge 成日死 (同一段 code 隊幾次會出現 AC 同 WA.. )..

Problem

given 一個 cost flow 的 graph (沒有 negative cycle), 及給出一個滿流的流方案 , 問這個方案是否已經是 min cost, 如果不是, 給出一個更好的方案 (不用 optimal)

|V| = 200, |E| = 10000

---

Solution

首先重新做一次 min cost flow 一定會超時..
注意到其實不用求出最 optimal 的 solution, 應該有其它方法

細心想, 如果它的方案不是 optimal, 咁應該可以行一些 augmenting path 去「調整」流量及流向
但由 source 出發已經滿流了

於是想到其實題目是找negative cycle
如果在 residual network 中沿著 augmenting path 搵到 negative cycle 即是存在更 optimal 的 solution
而且 negative cycle 上的 path = 要改流量的邊

Implement

由於只要搵到比佢個方案稍為 optimal 的便行, 所以流量有 1 就夠了
因此第一步找出 residual capacity > 0 的 edge

然後找 negative cycle
我用 SPFA 寫, 如果一個 node 被 update >= |V| 次就表示有 negative cycle..
效率比 bellman ford 好多了, worst case 也只是和 bellman ford 一樣

最後就是起返個 negative cycle 出黎..
呢步卡住左一陣!
一開始以為果個被 update >= |V| 次的 node 一定是在 negative cycle 上
不過其實可以係一些 negative cycle 指出去的 node

最後稍加修改, 不斷行 from[x] 直到走到 cycle 上的 node 便可以了 (一定會走到)

SRM 477

250

和六角型grid有關的題

速度一般般吧, 分基偶行來處理, 只得227.22

500

一看便想到是用 bipartile matching

第一個問題: 食input

先把string轉做array of char, 再用sscanf
不過寫的時侯也不太肯定, 花了少少時間去test這個寫法, 又損失了一些分數


第二個問題: Perfect square checking

想了想好像沒有甚麼標準又好的做法, 腦中想到有3個可用的寫法

1. sqrt + eps
2. sqrt 後掃前後5-10個數
3. 二分

最後在精確度和coding速度之間選了方法2

之後matching那part是貼武器的

過不到sample 2, 又花了很多時間去debug
浪費了超過10mins才發現題目中的 concencate 是就咁 concencate!
即係 "19", "5" 應看成195而不是19和5

又慢了一大截.. 終於可以submit

submit後睇下段code啦.. 突然發現由於改了為將d string concencate哂先轉為array of char, 又忘了開大array..!
逼不得已要resubmit..

得返 228.91

1000

疑似 dp on tree, 未諗到

---

system test 過了, rating 升了 ~100
500 浪費了很多時間又resubmit實在有很大影響, 尤其是找不到bug又不知為甚麼過不到sample那種心情, 還是要看清題目

---

條500原來因為有一個很重要性質才可用bipartile graph matching的, 之前一直無想過
原來我對 matching 的理解還是有不清楚的地方.. 不過也好, 經過今次後終於明白了

Team Training 27/7/2010 - CEPC 2003

今次的題目比上次的還要難..
上次還有2條可以有機會過的, 今次過完做到的就渣灘了..

最後 我+bill+danny 共過了4題.. (onsite champion solve了6題)

題目: http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=ce&year=2003

---

A - Easy Task?

data processing, bill 做的

---

B - Bundling

題目長得很過份.. danny看明後跟我說題目大意, 判定為不想做

---

C - Shortcut

我的方法是先按 x->y 和 y->x 兩種方法排序..

然後找出每點的四個方向會最先碰到哪點, 用二分的lower bound和upper bound
但由於不懂用stl的, 所以還是寫了4個binary search

雖然similar code可以copy, code length還是爆了100
在戰略上不應做呢題先的..

---

D - Dice contest

後來大家一起討論.. 得出「局部shortest path」的猜想
不過 code 起上來好像很煩..

---

E - November rain

看到這類題最先想到segment tree
但發現很多地方唔work

於是想到由左做到右的方法
便可好好利用題目中的 "there are at most 100 segments placed above any point on the ground level"!

解法是先把所有點 sort by x
用一條 list keep 住每點 x 上 segment 的高低順序

每次 maintain (add, delete) 都可以用 linear 的方法去做
可以求出
1. 每條 segment 接收了多少由天來的雨水
2. 每條 segment 會流去邊條 segment

之後便很簡單了

WA 的幾棍都是在 sorting 上有誤
如果 x 值相同, 應該是「先入後出」的
如果同是先入, 則應該由下至上的入
如果同是先出, 則應該由上至下的出

code的時侯便會明白的了..

---

F - Football
G - Which is next?
H - Hang or not to hang

0 idea..

---

I - Minimizing Maximizer

一起做的, 我寫 segment tree 的部份, 其餘由 bill 和 danny 完成

Team Training 20/7/2010 - CEPC 2002

今次的題目都不易.. 做了3題

其中一題比較有趣

---

G - Timetable

題目是 given 一些 node 和一個火車時間表 (departure time, arrival time), 定義一條由 1 到 n 的 optimal connection 為在 A 時由 node 1 出發而在 B 時到達 node n, 並且沒有其它方法可以在 A' (A'>=A) 時出發而在 B' (B<=B') 到達

要list出所有optimal connection



首先想到的是對所有可能的出發時間做一次shortest path, 但可能會很慢

之後想到由decreasing的departure time開始不斷做shortest path
每次行過一條edge後便可以把那條edge delete!
因為是decreasing的departure time開始做, 所以如果在t=x出發行過某條edge, 咁對於出發時間早於x, 如果是optimal的話一定不會再用那條edge

實際implement應該先把edge sort好再加進edge linked list中
不過在training時由於覺得太麻煩而沒有做這步, 不過也run得很快

IOI 2004 Empodia

首先, for each i, 搵出由 i 開始且最短的 framed interval, 記完結位置為 p[i] (即 i..p[i] 為一 framed interval), 搵最短是因為一些更長的可以肯定不是 empodia


對每個 i, 可以在 O(N) 搵到
由於 framed interval 的特性, e[i..j] 滿足以下條件即為 framed interval

• e[i] < e[j]
  
• e[i] = min{e[k], i < k < j}
  
• e[j] = max{e[k], i < k < j}
  

很容易可以做到

之後就係delete一些不是 empodia 的 framed interval
方法就係 for each i, 睇下有冇 j>i 而且 p[j]<p[i]

總時間O(N²)


順帶一提, 解題報告話呢題有O(N)方法, 不過是論文來的.. (只有一個test case需要O(N), 佢應該唔預有人諗到..)

POJ 3493 Chessboard Puzzle

題目是說, 給出一個 n*n 的 grid, 每格有一個分數 (可以負), 現在要將每格染成白色或黑色, 總分計算的方法是:
----如果兩格相鄰而且異色, 把它們分數的乘積加到總分
問最大可能總分, n <= 16

---

做法是使用狀態DP
一開始是想用像炮兵陣地的方法DP, 即state是記一行的permutation, 但單是做一次transfer便要2²ⁿ了

後來聽超超說,
有一個很強的加速

考慮到每一格是黑/白最「遠」也只是影響到下面那格 (假設順序是一行行由左至右)
即 n 格後
可以順著做而且只記著前n步的狀態

即

......
......
......
......
......
......

做到紅色那格時, 只用記著藍色的排列, 每次transfer後只是把排列shift後一格 ->

......
......
......
......
......
......

把time complexity降至O(n²*2ⁿ)

Individual Training 13/07/2010

A - Adventure of Super Mario

Shortest Path
一開始以DFS來處理super run, 後來發現處理不到limit的情況
於是改用floyd-warshall preprocess, 改outer loop便巧妙地處理到castle不能經過的條件



B - Geometry with a ruler

geom題, 不過差不多要0誤差..
我用fraction + long long, 不斷取 gcd 約簡過了
理論上應該會有case搞到我 overflow..



C - Chessboard Puzzle

學到野的一題, 之後打篇entry詳細講..



D - Diamond Puzzle

簡單BFS



E - Discrete Square Roots

又係同mod有關的題目.. 未識做

IOI 2004 Hermes

一個很重要的 observation: 在 optimal case中, Hermes 每次移動都只會行一段直線 (即唔會行 x 再行 y )

由於傳完 message 去第 i 個點後, Hermes 的位置只有大約 4000 個可能性 (或2N), 所以諗到用 dp 做, transfer 時, 因為由上面的 observation, 所以可以 O(1) 完成每個 state 的 transfer, 總時間上限 O(N²)

IOI 2004 Artemis

O(N²) 時間可過! 但 memory 就唔得
做法也是用 inclusive-exclusive, 問題係點樣唔用 O(N²) memory 去 implement

先把點 sort by x
之後由左至右咁做, fix i for j, 每次都係 compute s[x_j][y_j]+s[x_i][y_i]-s[x_i][y_j]-s[x_j][y_i] 之類,
發現除了 s[x_j][y_j] 和 s[x_i][y_i], 其實都只係 depend on x_i, y_i

所以只要把和 i 有關的 2N 個「關鍵點」(共N²個「關鍵點」)計出, 即 s[x_i][*], s[*][y_i], 便可把 memory 降至 linear

IOI 2001 - 2003 小結

小結一這3年的IOI題..

2001: 這年得3題batch題, 3題題目都straight forward, 不過算法不易想到. BIT第一次出現, twofive code 起上來也不容易一次就成功

2002: 很多 ad-hoc (除了 batch), 不過真係諗唔到就諗唔到 (例如utopia, bus). 有一條要用凸完全單調性來優化DP, 很不 IOI feel..

2003: 也是只得3條batch, 算法不難想到, 只是3條實現起來都很煩, code length 很長

IOI 2003 Amazing Robots

題意很簡單, 就是BFS

注意到guard cycle是12, 所以有 20*20*20*20*12 個 state

簡單還簡單, 試左好幾次先過哂所有data.. (仲要睇住data來debug..)
有一個比較麻煩的位是要 check 係咪同個 guard 換位

過之前段code最後一個不能handle的問題 (G = guard, R = robot)

...    .G.
.G. -> .R.
GR.    .G.

我會當左係換位, 但其實唔係

IOI 2003 Seeing the Boundary

因為障礙物是 convex polygon, 省卻很多麻煩 (如果可以 concave 我都未諗到點 handle..)

每個 polygon 會遮蔽其中一段連續的點
所以只要找出遮蔽的範圍就好做了

我的做法是先對每個 polygon 的頂點做極角排序
由於那些頂點會縮在 180^o 的範圍內, 用cross product就可以找出紅色那兩點

由於不想handle precision, 我所有計算都用哂 integer
之後麻煩在要找出射線和 boarder 的交點

經過一輪數學運算, 終於截到式
有個tricky的位, 就係「開始遮蔽點」和「結束遮蔽點」做除法一個是 round up 和 round off

最後一個bug就係我無handle到有些障礙物一個點都無遮到

IOI 2003 Comparing Code

做法類似搵 maximum common substring

首先map哂佢d variable名做數字
之後fix其中一條sequence, 窮舉第2條sequence係佢上面的位置 (或者調轉)

不同於搵common substring, 判斷valid唔valid要睇埋之前的
方法就係用2支pointer做掃描線!

valid 就 tail++
invalid 就 head++

判斷valid的方法
一開始諗住2個sequence, 把variable一個對返對應的variable
不過唔work

例如

Seq 1:

A = B + C
A = B + B

Seq 2:

X = W + Y
X = Y + Y


compare 第一句 statement 時, 對 X->A 無問題
但係 "W->B, Y->C" 和 "W->C, Y->B" 是有分別的, 而且要在之後先睇得出來


之後就想到了"記上一次出現的位置"的方法
位置指的是 第?句statement的左邉/右邊

即不再記 X->A, 而是記 "X對上一次出現是在第一句statement的左邊"
每次checking就係睇下這些 "位置" 是否吻合

就解決了問題

IOI 2002 Bus Terminals

做法離不開窮舉 2 個 terminal, 再計算 route distance

一開始以為剩返的 N-2 個 bus stop 會選擇連去離他最近的那個 terminal, 不過後來發現反例
解決方法有點像greedy (看contest report)

窮舉 terminal i,j
先把剩下的 N-2 個 bus stop 都連去 i
然後按 dist[k][i]的 decreasing order, 嘗試把 k 調到 j 看看能不能使最大距離下降

有點詭異的過了..
很直觀做法但又無prove過..

IOI 2002 Batch Scheduling

傳說中的凸完全單調性優化

要倒著做的
dp[i] = 處理 job i 到 job N 的 minimum cost

O(N²) 的做法是 dp[i] = min{dp[k] + (S+T_i+T_i+1+…+ T_k-1) * (F_i+F_i+1+…+F_N) | i < k < N+1}
(即是後面的 job 的 factor 在前面計)


優化到O(N) [照著contest report打]

在compute dp[i] 時, 例如有2個決策 k 和 l (k < l)
即 dp[i] = dp[k] + ... 還是 dp[i] = dp[l] + ...

k 不差於 l 的條件是

dp[l] + (S+T_i+T_i+1+…+ T_l-1) * (F_i+F_i+1+…+F_N) ≥ dp[k] + (S+T_i+T_i+1+…+ T_k-1) * (F_i+F_i+1+…+F_N)
dp[l] - dp[k] + (T_k+T_k+1+…+ T_l-1)*(F_i+F_i+1+…+F_N) ≥ 0
(dp[k] - dp[l]) / (T_k+T_k+1+…+ T_l-1) ≤ (F_i+F_i+1+…+F_N)

設 g(k,l) = (dp[k] - dp[l]) / (T_k+T_k+1+…+ T_l-1) ; f(i) =  (F_i+F_i+1+…+F_N)

會得出2個特性

Property 1: 如果 g(k,l) ≤ f(i) , 咁對 dp[i] 黎講, k 比 l 更好
Property 2: 如果 g(j,k) ≤ g(k,l) , 咁對於 dp[i] 黎講, j 比 k 好 或 l 比 k 好


property 2 implies 對於 g(j,k) ≤ g(k,l) , 計 dp[i] 的時侯可以不用試 k 這個 choice

整個 algorithm 就係由 dp[N] 做到 dp[1]
maintain 住一條 deque Q, 滿足

1. q[1] > q[2] > q[3] ... > q[r]
2. g(q[r],q[r-1]) > g(q[r-1],q[r-2]) > ... > g(q[2],q[1])


計 dp[i] 時, 由 property 1 得知如果 f(i) ≥ g(q[2],q[1]) 咁 q[2] 比 q[1] 好
由於 f 是 increasing 的 (因為倒著做), 所以知道 q[1] 之後都唔會再有用, 可以 pop 走
所以可以不斷 pop queue head 直至 g(q[2],q[1]) > f(i)


現在有 g(q[r],q[r-1]) > g(q[r-1],q[r-2]) > ... > g(q[2],q[1]) > f(i)
由 property 1 的相反得知.. 現在 q[1] 對 i 是最 optimal 的

就能計算出 dp[i] 了

下一步就是要把 i push 入 Q
方法是由尾開始 pop 走加左 i 落去會唔符合 g(q[i],q[r]) > g(q[r],q[r-1]) 的點 (類似做 convex hull)