反斗奇兵: Exhausion & Patterning

小弟一直都不喜歡做剪枝的exhaustion題... 所以今次想介紹一些不是直接exhaustion的頹題但又不是用剪枝法的題型

還記得JOE神講過的 HKOI 2006 Senior - Toggle 嗎?

題目大意:

有一個N*N的matrix﹐初始時每一格的value都是0 or 1
每一步可以把一整列或一整欄的0變做1，1變做0
目標是找出一種方法使整個matrix所有value變做0
(N<=18)

Sample:
N=4
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0

解法: 反第3欄和第3列

這題是dp? greedy?
如果沒估錯的話，以上2種方法都做不到的... 那就只剩下exhausion了... 但 O(2^(2n)) 又會TLE

Observation 1: 反row/column的次序不影響結果 事實上，m[i][j] 的最終value 只是取決於反row i 與反column j 的次數之和

Observation 2:
每column/row不會反>1次
明顯地，反2次=白反(不是白飯)，反3次=反1次...

所以，正確解法就是
exhaustion反哪些column，之後對於每一row，若全部=0就不反，全部=1就反，部份=1就代表exhaustion出來的反column組合不正確

Time complexity: O(N^2 * 2^N)

做這些題目，重點就是觀察形狀和特性，甚至不用exhaustion也能solve到

例子:

pku 3363 - Annoying painting tool
pku 3279 - Fliptile

加多題，

pku 3600 - Subimage Recognition

下面是這2條的解法

-------------------------------------------------------

pku 3363 - Annoying painting tool

題目大意:
和 Toggle 差不多，不過每次反一個r*c的長方形

(反該點 = 以該點為r*c長方形左上角來反)

Observation:
照舊，同一點不會反>1次，反的順序沒關係...

解法:
由最左上方至最右下方的次序來做，如果該點=1就反
因為若「此時不反，時機己晚」，由於是"左至右，上至下"的做，做到此時只剩下反這點可以使這點變做0
當然，反這點的長方形不能出界...
若果最後不能把所有變做0，則是no solution

sample:
4 3 2 1
011
110
011
110

011 // 不用反
110
011
110

001 // 反!
100
011
110

000 // 反!
101
011
110

000
001 // 反!
111
110

000
001 // 不用反
111
110

000
000 // 反!
110
110

000
000
010 // 反!
010

000
000
000 // 反!
000

000
000
000 // 不反
000

最後一列也要做，check有沒有漏下'1'未反，若有，即no solution

至於反後怎樣update個matrix
若O(r*c) 的反，整個time complexity = O(N^2*M^2)，很慢

其實每次反可視為把那該長方形內每格的count[i][j]+1
做到(i,j)時，該格的最新數值 = (matrix[i][j]+count[i][j])%2

要做到[修改一堆，query 1點]...
當然是...
2D BIT!
當然segment tree也可...
[修改一堆，query 1點] 的細節另文再談或等BIT之神whh講...

Time complexity = O(N*M*lg(N)*lg(M))

-------------------------------------------------------

pku 3279 - Fliptile

也是和 toggle 差不多，不過每次是反一個十字 (可反出界)

解法:
exhaustion第一列的反pattern，之後由第2行往下做，每一行左至右的掃，反不反是"沒有選擇餘地的"

Time complexity = O(2^N*M*N)

總結: 做這些題目要夠狠心，要令那些格沒有「反不反」的選擇餘地

談匈牙利算法 Hungarian Algorithm

匈牙利算法是小弟今天放學剛剛學會的一種算法，其實以前都略略聽過 ......

那是像匈牙利輕騎兵一樣，強得很的東西。

它可以用來解決二分圖模型的問題，包括部份網絡流問題 !

我看過幾個網頁，嘗試理解，

根據 匈牙利算法@百度，

匈牙利算法是無比抽象的東西，

增廣路徑、匹配M、集合M，just to name a few，我郁悶了。

再看看 匈牙利算法@維基，

雖然沒有文字解釋，但用心去解讀後，相信比較易去明白，

也明白了這個算法的運作很難只用文字表達......

建議看百度大概理解這算法是什麽，再看維基了解詳細運作。

算法輪廓 : 若P是圖G中一條連通兩個未匹配頂點的路徑，並且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現，則稱P為相對於M的一條增廣路徑。
(1) 置M為空
(2) 找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M
(3) 重復(2)操作直到找不出增廣路徑為止

看不懂還是看 WIKI 的 pascal code 吧。

---------------------------------------

例題 :

1 : pku 1274 The Perfect Stall

問題是有 N 隻母牛，M個倉，每日，每隻牛只會去某幾個倉渣一單位奶。
當中一個倉只能容納一隻母牛，請問最多可以渣多少單位奶 ?

解法 : 把二分圖，左邊為母牛，右邊為倉，牛倉關係為頂點路徑，製成二分圖，
利用匈牙利算法便輕鬆可解決。
(用網絡流也可以做到)

2 : pku 3041 Asteroids

問題是有 N*N 的距陣，某些格子有小行星，
現在最強武器褶櫈，它可以剷除一行或一列的小行星，
問最少要多少最強武器才可以消滅所有小行星 ?

解法 : 非常巧妙地把題目的距陣和小行星化成二分圖，
左邊為行，右邊為列，行星出現為路徑。
再利用輕騎戰術便解決了。

解釋 : 對於每一行 (橫向的row)，都會盡量去選除一粒小行星，分 A,B,C 三個 CASES :
A : 如果選到而小行星不是該行最後一個小行星，即代表最強武器會水平發射擊中該行所有小行星;
B : 如果小行星是該行最後一個小行星，即代表該行前部份的小行星已被上方的最強武器射中，最強武器會垂直射中該列所有小行星。
C : 如果沒有小行星被選中，即所有小行星被之前的最強武器的垂直攻擊打中。

3 : pku 2239 Selecting Courses

和 3041 相似的題目

4 : pku 2446 Chessboard

5 : pku 1466 Girls and Boys

6 : pku 1325 Machine Schedule

7 : pku 1469 COURSES

基因改造優化粟米

http://acm.pku.edu.cn/JudgeOnline/problem?id=2019

pku 2019 - 粟米田 (con-field)

這題的特別之處，是有很多不同的algo都可以AC，所以想分享一下不同algo的做法和效率

題目大意:
有個N*N的matrix，每格儲住一個integer
現有K個query，每次抽問一個B*B的範圍中的max-min

(B<=N<=250, K<=100000) ------------------------------------------------------------------------

Algorithm 1: 直接搜索

很直接，每次query就掃哂整個B*B的地方
Time complexity: O(K*N^2)
由於只有N*N種問法，而K>N*N，所以記錄己問過的結果可以加快少少 (呢個方法同樣適用於下面的algo, i.e. K=N^2)
記錄結果的Time complexity: O(N^4)
雖然time complexity仍是很高，但據聞pku的數據很虧，所以仍是過到的

------------------------------------------------------------------------

Algorithm 2: 2D segment tree/2D binary search tree

由於segment tree的強項就是能O(lg N)地找到一段數據中的max, min，因此把它拓展到2D，就能找出一個2D陣列中的max, min
Time complexity: O(N^2*lg N*lg N)
快了很多，但缺點是2D線段樹很惡code，又易有bug
還有，線段樹的特點是要query的range係幾多都得，但呢題一早俾左個range你，所以應存在比segment tree更簡單的方法

------------------------------------------------------------------------

Algorithm 3: pre-compute 所有水平B格中的max, min

以test case做例子 (B=3)

5 1 2 6 3                      
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9

假設先pre-compute 一個 max matrix

5 6 6 * *   // 5=max(5,1,2) ; 6=max(1,2,6) ; 6=max(2,6,3)
5 5 7 * *   // 5=max(1,3,5) ; 5=max(3,5,2) ; 7=max(5,2,7)
7 6 6 * *
9 9 8 * *
9 9 9 * *

這樣的話, 每次找一個正方形區域中的max和min時，只需垂直找一次就得了，因為水平的B格己經找了
例如query(1,2) [左上角為1,2的正方形]

5 1 2 6 3                      
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9

5 6 6 * *
5 5 7 * *
7 6 6 * *
9 9 8 * *
9 9 9 * *

最大值 = max(6,5,6) = 6
找min也同樣道理

每次query的time complexity: O(N)

問題是，要怎樣pre-compute?

方法一: 每一次都向右掃B格
Time complexity (pre-compute): O(N^3)

方法二: 用monotone queue (deque)

在找第一列的3個max時，
分別求了 max(5,1,2), max(1,2,6), max(2,6,3)

5 1 2 6 3
5 1 2 6 3
5 1 2 6 3

不難看出1,2,6都重覆求了
事實上，這正是sliding window問題
當要找的max/min的range是固定且在slide的時侯，
就可以用monotone queue找!
Time complexity (pre-compute): O(N^2)

query也有方法優化的
注意到每次query也是在max matrix中找一段的max

所以可以先把它轉化成1D segment tree
這樣，每次query的time只需O(lg N)
Time complexity: O(N^2*lg N)

真的不能再優化?
再看一次個max matrix

5 6 6 * *
5 5 7 * *
7 6 6 * *
9 9 8 * *
9 9 9 * *

其實每次query就是找垂直相連B個中的max和min
那可以把他們都pre compute!!!

把max matrix pre compute 後的樣子:

7 6 7 * *    //  7=max(5,5,7)   6=max(6,5,6)   7=max(6,7,6)
9 9 8 * *    //  9=max(5,7,9)   9=max(5,6,9)   8=max(7,6,8)
9 9 9 * *    //  9=max(7,9,9)   9=max(6,9,9)   9=max(6,8,9)
* * * * *
* * * * *

同樣地使用monotone queue去做，總時間O(N^2) compute完畢
每次query: O(1)

Time complexity: O(N^2)

事實上，把max matrix和min matrix都pre compute後，每次query只是

scanf("%d%d",&x,&y);
printf("%d\n",max[x][y]-min[x][y]);

連記錄答案都不用...

monotone queue，繼BIT又一屈機之作

有左monotone，打code好輕鬆