網頁

Saturday 31 December 2011

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(N2+M)

Monday 26 December 2011

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 的感覺

Sunday 18 December 2011

COCI Contest 3 + SRM 527

COCI 2011/12 Contest 3: 10pm - 1am
SRM 527: 1am - 2.30am

就係咁, 連續打左 4 小時 code..

COCI:
除了 q6 其它基本上都立即想到做法
q2 題目寫得很差, 最後要靠估的
q3 第一次做 dice 題, 沒有經驗 hard code 這些東西, 寫得不是太好
q4 用 lower_bound 解決之
q5 很 standard, 做法是 pre-order traverse 一次, 然後每個 operation 便可以轉化成 1D 的 range update, 再用 BIT 做之, 由於 N 很大所以用 iterative 的 DFS
q6 其實是要找最大的 'gap', 即最長的等待時間, 不過想不到怎樣很快找 gap, 最後嘗試水分不成功


SRM:
今次打得挺順利的.. 基本上很快便想到做法
275: 用 dp[x][y] = 處理了 node 1..x, cover 了 node 1..y 的 maximum score
475: 上至下, 左至右試 '?', 再用 bipartite matching verify 之

Rating: 21322241 :D

Saturday 17 December 2011

URAL 1128 - Partition into Groups

由於想不到, 所以看 solution

做法很簡單, 先隨便 partition
然後 while child x has ≥ 2 enemies in his group, move child x to another group

Let badness = | { (x, y): x, y are enemies and lies in same group } |
可見 badness 在一次 operation 後會下降至少 1
而 initial badness ≤ 3N, 及 0 ≤ badness
所以一定有 solution, 而且 O(N) 找到

Monday 12 December 2011

Sem 3 Final + HKOI Final

終於過了這個 sem 最辛苦的 2 天 (3 個 final + 第 3 天 = HKOI final)
雖然還有 1 個 final + 2 份 asg, 但開始有心情渣灘了..

今年終於可以在 final 食花生, 原來食花生是很開心的
雖然現在打 code 己經沒有了當年那種膽戰心驚的感覺, 但終於覺得這年的 training 自己還是有進步的
結果我已經知道了, 可以說的是, 多打 code 一定沒有壞處

目前來說沒有一個 final 是滿意的, 完全沒有 midterm 那種輕鬆高分的感覺
希望出來結果不會太差吧..

Wednesday 7 December 2011

stl 中 vector 的 resize

溫 315 溫到 memory 的部份, 突然想起很久以前就想知道 stl::vector (下稱 vector) 是怎樣寫
為甚麼 vector 可以這麼神奇, 能不受限制地 push_back, 又可以快速地 random access?

最合理的解釋便是一開始預留了 memory 給那條 vector, 當不夠用時便 malloc 更多的空間
然後當然很好奇想知道每次預留多少空間 (估計是 4K), 一於寫個 program 試下

vector<int> a;
int *expect, *real;
a.push_back(0);

for (int i=1; i<1000; i++){
   expect = &a[i-1] + 1;
   a.push_back(0);
   real = &a[i];
   if (expect != real) printf("Reallocated at %d\n", i);
}

expect 是下一個 push_back 後預計的 address, 照理說如果 reallocate 了的話 real 和 expect 便應該不一樣
run 得到以下 output:

Reallocated at 1
Reallocated at 2
Reallocated at 4
Reallocated at 8
Reallocated at 16
Reallocated at 32
Reallocated at 64
Reallocated at 128
Reallocated at 256
Reallocated at 512

即是說, 每次 push_back 空間不足, 便會resize 成自身長度 2 倍的空間
假設 resize 的時間是線性, push_back N 次後的時間 = O(N) + O(N/2) + O(N/4) + ... = O(2N) = O(N)
所以 vector 的 push_back 平攤後是 O(1)

Saturday 3 December 2011

VC → HAMPATH

今天看了 VC → HAMPATH, 覺得個 construct 非常巧妙

VC(G, k): exists a k-vertex cover in G?
HAMPATH(G): exists hamilton path in G?

而要做的是, 把 HAMPATH model 去做 VC

由 "cover all edge" 變成 "pass all vertex", 很自然地想到 edge, vertex 互換
想法1: G 的 edge 是 G' 的 node, G 的 node 是 G' 的 edge

問題: 1 個 node 可以連著很多 edge, 但 1 條 edge 只能連著 2 個 node
解決: 每個 node 是 1 條 chain, 即多條 edge




明顯地未完成, 右圖輕易存在 Hamilton path, 但原圖的 VC 最少選 2 個 vertex
最大問題是, 不想條 path 走到一半可以換顏色
現在要加入 VC 中的變數 k: 選取 k 個 vertex, 即要 traverse k 種顏色的路
換句話說, 可以選取 k 條 disjoint path 去 visit 所有 vertex, 而每條 path 的 edge 是同顏色

這時就是最巧妙的一步
目標是把每個點 v 拆成一堆點 v', 並且符合:
1. 只對外連著 2 種顏色的 edge
2. 要走遍 v' 只能是: 選取了顏色1 / 選取了顏色2 / 選取了顏色1, 2

千呼萬喚:




要 visit 圖中的所有點, 有以下方法:




左至右: 只選藍色, 只選紅色, 兩種都選
分別對應一條 edge(u, v), 在 VC 中選取了 {u}, {v}, {u, v}

而且有一點很重要的是, 不能走到一半換顏色
因為若換了的話便一定不能走遍 v'

最後會得到類似以下的東西:




選 1 種顏色 (即選一個 vertex), 就可以走遍它連著的 edge
接下來這步就很簡單了, 因為選 k 個 vertex, 即可 traverse 此 graph component k 次
只要添加 k 個新 node 便可以解決之

References: http://valis.cs.uiuc.edu/~sariel/teach/notes/algos/lec/03_npc_III.pdf