Dijkstra, less查

今天做一題dijkstra時，第一次submit TLE，然後加了一句優化再submit就變15ms了
其實那句平時都有打，只是剛好這次懶沒打... 想不到影響這麼大

假設用pair作為heap的index，first=path length，second=node number ; dis[x] 為 dis[start] 到 x 暫時的shortest path

while (!q.empty())
     t=q.top();
     q.pop();
     if (t.first>dis[goal]) break;
     for all v visit by t.second
          if (e[t.second][v]+t.first<dis[v])
                dis[v]=e[t.second][v]+t.first;                
                push v into q;

加了紅色那句後，原理是如果heap頂的shortest path distance己經大於己找到去終點的shortest path distance，由於沒有negative edge，之後找到的path都不會比現有的更短，因此可以查少幾條path

所以 Dijkstra 又名 less查 是有道理的

swap 比一比

以下有三種把 x 和 y 數值交換的方法及交換 400000000 次的時間 :

1 : t = x; x = y; y = t; ==> 2.55s
2 : swap(x,y); ==> 3.40s
3 : x^=y^=x^=y; ==> 4.20s

第一句最基本，最快
第二句是方便 C++ 人的東西，中速
第三句是型人專用，竟然最慢 .....

結論，想快用第一句，但我會用第二句，因為方便一點又清楚一點

反斗奇兵: 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

由 中國餘數定理 到 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=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好輕鬆

各大 ONLINE JUDGE 連結

已放在各大戰場連結上，分別是:

PCOJ
http://pcoi.no-ip.org/~pcoijc/

POJ
http://acm.pku.edu.cn/JudgeOnline/

UVa
http://icpcres.ecs.baylor.edu/onlinejudge/index.php

ACMWORLD
http://acmicpc-live-archive.uva.es/nuevoportal/

USACO
http://ace.delos.com/usacogate

VIJOS
http://www.vijos.cn/Index.asp

TimusOJ
http://acm.timus.ru/

SGU
http://acm.sgu.ru/index.php

ZOJ
http://acm.zju.edu.cn/