Team Training 31/8/2010 - NEERC 2003

據說很難的一個 site..
不過也沒有想像中難
joe+kn+ctli solve剩一題!

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

---

A - Alternative Scale of Notation

Solution: Solve by yym

---

B - Bring Them There

Solution: Binary search (optional) + Flow

當時想不到, 不過joe一說分層圖便明白了
binary search 完成時間T, 再將每個 node split 開 T 層, 第 i-1 層的連去第 i 層
做 max flow 睇下做唔做到

也可以先設 T=1, 做唔到再一層層加上去
呢個方法較快, 但感覺上較難code

---

C - Code Formatting

Solution: 同 parsing 有關, solve by danny

---

D - Data Mining
E - Entropy

當時都沒想到的2題, 聽完solution也只是半明, 題型完全不是我的type..

---

F - Farmer Bill's Problem

Solution: 不斷把正方形合併

由於每次搵有無touch/overlap要 O(N²), 而最多合併 N-1 次
所以總時間為 O(N³)

---

G - Game

Solution: 不斷刪去可能性

分析為甚麼會 "I don't know the answer", 可以知道每說一次, 就知道一定不是 sum/product 唯一的 pair
然後不斷重覆此過程就是了

---

H - Hypertransmission

Solution: Sorting + Update

先把所有距離對 sort by distance, 然後逐條加上去, 再即時 update 那些值就可以了

---

I - Illumination

Solution: 未有人識做

---

J - Jurassic Remains

Solution: 試哂所有可能性

不過都要試得有技巧, 要做到純O(2ⁿ), 要用到bitwise operation

---

K - King's Quest

Solution: SCC

Given 一個 bipartite graph, 要 output 所有在其中一個 perfect matching 的 edge
|V| = 2000
|E| = 200000
題目已 given 一個 perfect matching


首先佢 given 一個 perfect matching 一定有意思, 因為就咁做一次都要 O(VE)
應該係用佢個 perfect matching 去搵其它 perfect matching 出黎

第一個諗到方法是試一條 edge 時, 看看能不能以最小的改動去維持 perfect matching
但這個方法最差是 O(E²)

之後想到用 augmenting cycle 的概念
for 每個 node, 搵哂所有由佢出發的 cycle, 途中所走的 edge 就是可選的 edge
但這個方法是O(VE), 也過不到

最後想到, 要搵所有 cycle 出黎可以用 SCC!
首先對個圖 (只走 augmenting path) 做 SCC
然後 check 所有由左連去右的 edge, 如果佢地係同一個 SCC, 咁 implies 佢地係一個 augmenting cycle 入面, 咁即係可以用
KO!

很優美的一條:D
估唔到SCC都可以同flow類扯上關係..