做男人不容易系列:是男人就过8题
1737 Problem A Connected Graph
1738 Problem B An old Stone Game
1739 Problem C Tony's Tour
1740 Problem D A New Stone Game
1741 Problem E Tree
1742 Problem F Coins
1743 Problem G Musical Theme
1744 Problem H Elevator Stopping Plan
=========================
男人們努力了
2008年9月20日 星期六
反斗奇兵: 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)
總結: 做這些題目要夠狠心，要令那些格沒有「反不反」的選擇餘地
2008年9月18日 星期四
談匈牙利算法 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
由 中國餘數定理 到 PKU 1006 Biorhythms
PKU 1006 Biorhythms
http://acm.pku.edu.cn/JudgeOnline/problem?id=1006
題意是，給定 n 除以 23,28,33 的餘數及 d，現在要求 n-d 的最小值。
----------------------------------------------------------
說起中國餘數定理，就必定會想起"韓信點兵"。
用日常生活例子來說，你不知你朋友的年紀 y ，但問他 (y mod 3) --> r3, (y mod 5) --> r5 及 (y mod 7) --> r7 三個數可以輕易快速地計算 y。
y = (r3*70+r5*21+r7*15) mod 105
For example, 你朋友年紀 29 , r3 = 2, r5 = 4 , r7 = 1,
(r3*70+r5*21+r7*15) mod (3*5*7) = (140+84+15) mod 105 = 29。
原理是 :
70 除以 3 餘 1 ，並是其他兩數的倍數 ;
21 除以 5 餘 1 ，並是其他兩數的倍數 ;
15 除以 7 餘 1 ，並是其他兩數的倍數 ;
因此 15 無論加多少次都不會影響除以 3 及 5 的餘數。
而把 15 乘以 r7 便可以控制到除以 7 的餘數。
如此類推......
不妨稱 70 是 3 的"好數"，21 是 5 的"好數"，15 是 7 的"好數"。
現在問題是如何找出給定除數的"好數"。
例如新的一個系統給定除數 5,11,13,17， (除數最好要互質，否則有機會出現茅盾，如除4餘1，同時除2除0)
又給出 y,r5,r11,r13,r17，如何求 y 呢?
問題即是如何找出 r5,r11,r13,r17，
利用上述原理寫個程序，
for (i=1;i<5;++i) 5="=" y="(r5*2431+r11*9945+13*11220+17*715)" style="font-weight: bold;">一般化後的式子為，除數是 x1,x2,....xn，兩兩互質。
y = sum(rxi*xi的好數) mod product(xi) , for 1<= i <=n
--------------------------------------------
回到 PKU 1006，解決方法是找出 23,28,33 的"好數"，然後一條式子......
用以上方法代替暴力法，時間複雜度即可由 O(21252) 降至 O(1)。
輕鬆解決。
--------------------------------------------
題外話 :
若果這題的除數也是變量的話，則把預先計好的 rx1,rx2 .... rxn 的過程包含在程序中。
用這個方法代替暴力法，時間複雜度由 O(rx1 * rx2 * ... * rxn) 降至 O(rx1 + rx2 + ... rxn)。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1006
題意是，給定 n 除以 23,28,33 的餘數及 d，現在要求 n-d 的最小值。
----------------------------------------------------------
說起中國餘數定理，就必定會想起"韓信點兵"。
用日常生活例子來說，你不知你朋友的年紀 y ，但問他 (y mod 3) --> r3, (y mod 5) --> r5 及 (y mod 7) --> r7 三個數可以輕易快速地計算 y。
y = (r3*70+r5*21+r7*15) mod 105
For example, 你朋友年紀 29 , r3 = 2, r5 = 4 , r7 = 1,
(r3*70+r5*21+r7*15) mod (3*5*7) = (140+84+15) mod 105 = 29。
原理是 :
70 除以 3 餘 1 ，並是其他兩數的倍數 ;
21 除以 5 餘 1 ，並是其他兩數的倍數 ;
15 除以 7 餘 1 ，並是其他兩數的倍數 ;
因此 15 無論加多少次都不會影響除以 3 及 5 的餘數。
而把 15 乘以 r7 便可以控制到除以 7 的餘數。
如此類推......
不妨稱 70 是 3 的"好數"，21 是 5 的"好數"，15 是 7 的"好數"。
現在問題是如何找出給定除數的"好數"。
例如新的一個系統給定除數 5,11,13,17， (除數最好要互質，否則有機會出現茅盾，如除4餘1，同時除2除0)
又給出 y,r5,r11,r13,r17，如何求 y 呢?
問題即是如何找出 r5,r11,r13,r17，
利用上述原理寫個程序，
for (i=1;i<5;++i) 5="=" y="(r5*2431+r11*9945+13*11220+17*715)" style="font-weight: bold;">一般化後的式子為，除數是 x1,x2,....xn，兩兩互質。
y = sum(rxi*xi的好數) mod product(xi) , for 1<= i <=n
--------------------------------------------
回到 PKU 1006，解決方法是找出 23,28,33 的"好數"，然後一條式子......
用以上方法代替暴力法，時間複雜度即可由 O(21252) 降至 O(1)。
輕鬆解決。
--------------------------------------------
題外話 :
若果這題的除數也是變量的話，則把預先計好的 rx1,rx2 .... rxn 的過程包含在程序中。
用這個方法代替暴力法，時間複雜度由 O(rx1 * rx2 * ... * rxn) 降至 O(rx1 + rx2 + ... rxn)。
2008年9月17日 星期三
基因改造優化粟米
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 * *事實上，把max matrix和min matrix都pre compute後，每次query只是
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)
scanf("%d%d",&x,&y);
printf("%d\n",max[x][y]-min[x][y]);
連記錄答案都不用...
monotone queue，繼BIT又一屈機之作
有左monotone，打code好輕鬆
訂閱：
文章 (Atom)