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), 佢應該唔預有人諗到..)