VC 與 AOC

前幾天看到 matrix67 的 blog, 覺得很有趣, 便一直在想除了還有沒有其它做法
由於沒有打 SC (StarCraft), 不過應該和 AOC 差不多 (其實這些即時戰略遊戲應該都不大差別)
即是說, 給出一個 AOC 的局況, 判斷某一方是否能勝出

文中用的 NPC 問題是 PLANAR GRAPHS HAMILITON PATH, 把判斷 "圖 G 是否存在 HAMILITON PATH" 轉化成判斷 "此 SC 局況某方是否能勝出", 從而得出 SC 是 NP-HARD 的結論
類似的, 現在要選一個 NPC 問題, 把它轉化成 AOC 中的局況

想到的是 PLANAR GRAPHS VERTEX COVER
這個問題即使限制 degree 不大於 3 仍是 NPC 的 (見 Wikipedia)
即是說, 給出圖 G, 是否能選取不多於 k 個頂點覆蓋所有的邊

現假設有玩家 A 和 B
玩家 A 有 |E| 隻劍兵, 對應著 |E| 條邊, 而且是被困著的 (例如地圖是海, 劍兵在孤島)
玩家 B 則沒有村民和軍隊, 但有 |V| 座弓箭場 (在 |V| 個島上) 和剛好夠資源生產 k 隻茅兵

對於邊 (u, v), 要做到在島 u 生產的茅兵能射到這條邊的劍兵但又不能走到島 v
具體方法是



即是說, 在某個島生產茅兵能殺掉相鄰邊上的玩家 A 劍兵
玩家 B 能勝出的唯一方法是殺掉所有劍兵, 顯然的, 這對應著圖 G 有 size k 的 vertex cover
即是說, 如果懂得判定 AOC 的勝負問題, 則懂得判定 planar 的 VC 問題
得出 AOC 是 NP-HARD 的

ps0. 更多的遊戲
ps1. AOC 今年會更新! :D

ITCSC-INC Winter School 2012: Keywords

Network Coding
- Randomized coefficient matrix G: (i, j) : e[j] = G[i][j] * e[i]
- High Probability Det != 0
- Theorem: Cut(s, t) = Maximum information sent from s to t = #Linearly Independent vectors

Directed Graph connectivity
- F = H + GF, F = H * inv(I - G)
- High Probability: Min Cut = Matrix Rank
- Compute inv(I - G), Matrix for Cut(s, t) = extract submatrix from it

Single Source
- Topological sort, O(Δd²)
- Use Superconcentrators → O(Δd)

Expanders
- Sparse and highly connected
- Example: Bipartite Graph (n, 0.75n), left regular with constant number of edges
- High Probability: if |S| ≤ n/2 → |N(S)| ≥ |S|

Superconcentrators
- G(I, O): I, O = disjoint vertex sets
- For every k, choose k vertex from I, O and there exists k edge-disjoint path
- Construct: edge from I_i to O_i
- |I'| = 0.75|I|, |O'| = 0.75|O|, Expanders: (I, I'), (O', O)
- Recursively Superconcentrators G(I', O')

Matrix Rank
- Find linearly independent columns vectors for A_{m × n}
- Regular Bipartite Graph (n, 10m): left degree = 2, right degree = n/5m
- B[i] = Random Linear Combination of n/5m column vectors from A
- Done in O(#Non-zero entries in A)
- High Probability: Rank(B_{m × 10m}) = Rank(A_{m × n})
- Trace: at most n/5 vectors in A are candidate: reduce problem to A'_{m × n/5}

Sem 4 1/13: Begin

不知不覺間來到第 4 個 sem, 感覺還是一事無成
出了 GPA, 以數值來看總算可以很自然地告訴別人
該 A 的科都 A 了, A 不了的也沒有很失望

下年會不會去 exchange 還是未知數
今個 sem 還是讀書 + ACM (其實我都唔知仲可以有甚麼..)
繼續全部讀 major

CSC 310 - Software Engineering
十半堂當然不上, 也沒有一定要上的理由
為了吸引人答問題派 coupon ← dislike

CSC 318 - Principles of Programming Languages
感覺: 未讀過就唔叫讀過CS, 不過興趣不大

CSC 325 - Computers and Society
還在 waitlist, 計 attendance 的 tutorial 撞了 day-off, 極有可能 drop
不得不提這個 course = 浪費時間, 還要做 project, 莫明奇妙

CSC 342 - Computer Architecture
又是李健康, 又有 4 個 quiz + resubmit..
不過 project 用 C 做! 希望唔好咁痛苦..

CSC 443 - Data Communication and Computer Networks
mole神的 course! 由於 workload 很大所以沒有 take
不過如果不是很忙的話打算去 S 班食花生, 上 mole神堂學到很多野呢

CSC 506 - Topics in the theory of computing
被 chin 慫恿去上了一堂 Andrej 的 course, 感覺: 正
內容是 coding theory + boolean functions + expander
應該會繼續 sit 下去

CSC 516 - Spectrum Algorithms
這個 sem 最刺激的 course, 內容大部份都未聽過
據超超講 + 自己經驗: 每個星期要花數小時複習
目前感覺是 linear algebra 和 graph 的關係
未來幾個月應該要和 matrix 做朋友了

最後當然是 WF
不過感覺離 WF 還有很多時間, 又很久沒有 5hr 的 training, 完全未有應有的緊張感
目前還沒有一個很明確的 rank 目標, 所以還是專心做題目吧

URAL 1557 - Network Attack

題目一句講完:
給出一個無向圖 G (可以有重邊/自環), 問有多少種方法 remove 2 條 edge 使得 G 變成 disconnected

一開始從 build BCC 的方向想, 可分為兩個 case: remove 一條 bridge + 任意, 以及在同一個 BCC 內 remove 兩條
不過想不到怎樣做 case2, 所以放棄了
後來想到可以用 DFS tree, 因為 tree 比較容易處理

先找出 G 的任意一棵 DFS tree
首先, 要使得 G disconnect 的話至少要 remove 一條 tree edge, 這樣就限制了很多可能性
以及, DFS tree 的其中一個特性是沒有 cross edge

Case 1: remove tree edge + remove back edge

很簡單, 只要記錄 subtree 的連通性便可以
Compute dp[x][y] = x 的 subtree 中有多少條 back edge 連到 y
便可以知道 x 的 subtree 有沒有連到外面, 如果是 0 條 edge 或 1 條 edge 就有方法做成 disconnect

Case 2: remove tree edge + remove tree edge

首先再分成 2 個情況: 兩條 tree edge 有沒有 ancestor 關系
如果沒有就很簡單, 做法和 case 1 十分類似

如果有的話則比較麻煩, 如圖, 紅色是想 remove 的 edge, 現要判斷綠色部份是否有連到藍色部份
而且要在 O(1) 內判斷
其實可以改變一下 dp[][] 的定義, 利用沒有 cross edge 的特性, 可知 x 的 subtree 只會連到 x 的 ancestor
dp[x][y] = x 的 subtree 中有多少條 back edge 連到 x 的第 y 層 ancestor
再使用 partial sum, 則可快速判斷

總時間為 O(N²+M)

Sem 3 之後..

Sem 3 終於完了(不計315 asg4 的話), 就寫寫總結吧
基本上功課沒有想像中那麼多, 可能因為沒有 318 的關係, 不過也有數天是特別忙的, 只是通頂次數比想像中少
不過真正忙的是加上每星期 14+小時的 ACM training, 令到這個 sem 非常充實

CSCI3230 Fundamentals of Artificial Intelligence - 莫明奇妙, 無法解釋

上了第一個星期之後就沒再上過堂.. 因為發現 lecture 的水份成份特高, 難以 get 到佢想講咩
slides 也是一樣, 寫得難以理解~
功課也很少, 只有一份 written + prolog + nn project

Final 也是年年一樣, 用 NN 的說法, 就是不斷用 past paper 做 training set
總括來說這個 course 十分無聊 + 頹, 唯一的得著就是見識一下 prolog 吧


CSCI3170 Introduction to Database Systems - 頹廢上堂, 頹廢結尾

317 可說是最「沒特色」的一科: 難度, 功課量等都是平均的水平~
開頭是 ER/SQL 等, 因為 AL 教過的關係, midterm 輕鬆高分
後半段雖說不上十分有趣, 但也不會悶, 雖然因為種種原因而開始走堂
B+ tree, recovery, locking 等都沒有上堂, 不過溫 final 時也不用花很多時間便看明, 不過最後還是炒了

功課可算是輕鬆, 不過 317 跟 323 有點相似的地方就是 slides 都很莫明奇妙
317 的 slides 那些 point 給人感覺就是隨便放在某一個位置上, 看的時侯還要想像它們的順序
還有就是 Ada Fu 講書會愈講愈細聲, final 有 amendments 時我估有半數的人是聽不到的
總括來說這科還是頹頹的過去便算了


CSCI3150 Introduction to Operating System - 燃燒時間, 燃燒肝臟

如果 315 沒有功課的話我對這個 course 的評價一定大升
雖然其實功課也很有意義, 會學到很多, 但每次一趕 deadline 又做不到又要通頂就會很燥
雖然對 OS 沒有強烈的興趣, 但內容其實還是挺有趣的, 不得不說 mole神教得十分好~
不過每次聽完也是似明非明的 status, 到了做功課和 final 又會覺得自己一事無成

一共有 4(5) 份功課, 全部都是 kernel hacking, 每份功課要打的 code < 100 行, 但是每次都要花數天去做..
最過份的是最後一份在 1 月才 dead, 放假也要做功課
總括來說對我來說 315 快快完結就好了


CSCI3160 Design and Analysis of Algorithms - 自信十足

完全沒有上堂的一科, 原因也不完全是因為學過 (除了 FPT), 最主要的原因還是因為是在九半
所以到現在連蔡雷震的真人也未見過..
不過還是要強調, 玩了幾年 OI/ACM 其實真的可以不上堂, 只要看看 slides 便可以去應試~

功課對我來說不難, 不過有時會很長, 有一份功課做了足足 10 頁紙, proof 也不用 formal 地寫
聽聞以前是會 kill 的, 現在變得不會, 導致 midterm/final 十分頹, final 還有一小時 check 卷~
總括來說就是讀得十分輕鬆


CSCI3130 Formal languages and automata theory - Inspiring, Exciting, Interesting

這個 sem 最有趣的 course, 除了去比賽全部堂都有去上~
功課雖然要寫很多, 但是做起上來還是很有趣的, 也有挑戰性, 很久沒有認真地去做功課
由頭到尾等都十分精彩, 最尾的 zero knowledge 更是一個完尾的句號~
還有就是 Andrej 教得十分好~ 上完堂後唔使點準備都可以就咁去考 final (雖然又炒了)
目前是由 yr1 以來最喜歡的 course~

經過 intern 和這個 sem, 終於發現原來還是喜歡不用打 code
雖然每次做完 315 都很有成功感, 但沒有 313 那種 inspiring 的感覺