Range Minimum(Maximum) Query, RMQ

• Input：array A[0, N]
• Output： the index of minimum(maximum) value between two given indices.

RMQ的功能是若有一群資料放在array中，在經過preprocessing後，可在O(1)的時間內找出index i~j之間的最小(大)的元素。目前preprocessing最快是O(n)，也就是只需要O(n)的時間就可以處理完成。

以下介紹O(nlog(n))的preprocessing方法，O(n)的方法是由此法去改進，所以先了解此法相當重要且因程式碼容易撰寫，所以也相當適合在ACM中使用。

1. 假設array的長度2的n次方。
2. 建立一個大小為n x log(n)的矩陣M，用來存放RMQ的結果，其中M[i][j]是指以index i開頭，長度為2^j次方內最小元素的index。
3. 使用dynamic programming方法建立M，需O(nlogn) time。

 

1. //time complexity: O(nlogn)
2. void preprocess(int M[MAXN][LOGMAXN], int A[MAXN], int N)
3. {
4.     int i, j;
5.  
6.     //initialize M for the intervals with length 1
7.     for (i = 0; i < N; i++)
8.         M[i][0] = i;
9.     //compute values from smaller to bigger intervals
10.     for (j = 1; 1 << j <= N; j++)
11.         for (i = 0; i + (1 << j) - 1 < N; i++)
12.             if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
13.                 M[i][j] = M[i][j - 1];
14.             else
15.                 M[i][j] = M[i + (1 << (j - 1))][j - 1];
16. }

 

1. //output: the index of the minimum value between index i and j
2. int RMQ(int i, int j, int M[MAXN][LOGMAXN], int A[MAXN], int N)
3. {
4.     if(i<0 || i>=N || j<0 || j>=N)
5.         return -1;
6.  
7.     if(i > j) //swap i, j
8.         i ^= j, j ^= i, i ^= j;
9.  
10.     int k   = (int)(log(j-i)/log(2.0)),
11.         rem = j-(1<<k) + 1;
12.     return (A[M[i][k]] > A[M[rem][k]] ? M[rem][k] : M[i][k]);
13. }

Reference：

• Range Minimum Query and Lowest Common Ancestor

One dimension minimum Hausdorff distance

Hausdorff distance可以用來量測兩個sets之間的距離，如果將其中一個set的元素全部加(減)上t個單位，則兩個sets之間的Hausdorff distance可能會變小或變大。實際的應用，假設我們要做影像的比對，有一張影像為template，而另一張影像是準備要和template比對的圖片，若能夠讓兩張圖片儘量對齊，則能夠提高辨識的淮確度。

my meeting report

我在IPL Vol 106(2008)第一次看到這一篇A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation時，看了很久還是不懂演算法實際上是如何運作的，於是追蹤下去追到了源頭的兩篇論文。

源頭是Huttenlocher在1990年發表的Computing the Mimimum Hausdorff Distance for Point Sets Under Translation，這一篇提出的算法提供最初的想法，把sets中每一個元素移動t單位的軌跡的圖形找出來，再找出所有軌跡極大值中的最小值即為所求，時間複雜度是O(mnlog(mn))。

第二篇論文是Rote在1991年發表的Computing the mimimum Hausdorff distance between two point sets on a line under translation也是沿用了Huttenlocker的概念，只是他使用了一個lower bound來減少搜尋解答時所要檢查的解答數量，這個演算法的時間複雜度已經是Optimal (O(m+n)log(m+n))，所以一直以來大家都使用這個算法。

2008年的這一篇論文也是Optimal algorithm，但是所需要檢查的解答數量又更少了，時間複雜度仍然是O((m+n)log(m+n))，但實驗的結果比Rote’s algorithm快了將近15倍。

以下是我用來畫軌跡圖的Scilab script：

1. //one dimensional Hausdorff distance
2. clear;
3. function [dist] = hausdorff(A, B)
4.   if(size(A, 'r') ~= 1 | size(B, 'r') ~= 1)
5.     warning("must be one dimension array");
6.     dist = [];
7.     return;
8.   end
9.  
10.   dist = max(compute_dist(A, B), compute_dist(B, A));
11. endfunction
12.  
13. //compute distance from point to set
14. function [dist] = compute_dist(A, B)
15.   m = size(A, 'c');
16.   n = size(B, 'c');
17.    
18.   for k=1:m
19.     D = abs(B - A(k));
20.     dist(k) = min(D);
21.   end
22.   dist = max(dist);
23. endfunction
24.  
25. function [dist,dist2] = minHausdorff(A, B, t)
26.     if (size(A, 'r') ~=1 | size(B, 'r') ~= 1 | size(t, 'r') ~=1)
27.         warning("must be one dimension array");
28.         dist=[];
29.         return;
30.     end
31.  
32.     m = size(A,'c');
33.     n = size(B,'c');
34.     len = size(t,'c');
35.    
36.     for i=1:m
37.         for j=1:len
38.             dist(i, j) = compute_dist(A(i)+t(j), B);
39.         end
40.     end
41.     subplot(1, 2, 1);
42.     xlabel("t");
43.     plot(t, dist);
44.    
45.     for i=1:n
46.         for j=1:len
47.             dist2(i, j) = compute_dist(B(i), A+t(j));
48.         end
49.     end
50.     subplot(1, 2, 2);
51.     xlabel("t");
52.     plot(t, dist2);
53. endfunction
54.  
55.  
56. A=[0, 0.5, 2, 3];
57. B=[0 0.3 1];
58. t=linspace(-3, 3, 500);
59. minHausdorff(A, B, t);

Coin Change

在寫ACM的時候，碰到了兩題(Q674, Q357)是關於這類型的題目，題目的大意如下：
假設我們有一些硬幣的幣值是1元，5元，10元，25元，50元，而我手中有n元，請問n可為幾種硬幣的組成方式。

Ex：n=11
11個1元硬幣=1個1元+2個5元硬幣=6個1元+1個5 元硬幣=1個1元+1個10元硬幣。
所以有4種組成的方式。
輸入值為隨意的n(0<=n<=max)，輸出為組成n的方式。 我解這一題的方式是用DP： 令coin[i]為硬幣的幣值，way[i]為i元時，有way[i]種組成的方式，

1. for (i=0; i<coin.size(); i++)
2. { 
3.     for(j=0;j<way.size();j++)       
4.         way[coin[i]+j] += way[j];     
5. } 

一開始的時候先計算用1元硬幣時有幾種組成的方式，然後再計算用5元硬幣時有幾種組成方式，以此類推，計算完畢後就是所求的解答。