CMU MSIT-SE 2015的青蛙题 FrogPond，求解

这道题是2015年CMU软件工程专业申请考的编程题之一，求大神给出O(n)的解法。
关于这次考试题的讨论在这里。

编程渣渣表示，只能做到用O(n^2)的时间复杂度来解

这题其实和Leetcode上的"Maximum Gap"很像。比如考虑X = 8, D = 3的情况，一开始pond是这样的：

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

我们把D = 3当作bin宽来分割这个序列，得到

1 0 0 || 0 0 0 || 0 1
0 1 2    3 4 5     6 7

现在我们得到以下规律：

A. 如果某一个bin中没有1，那么青蛙一定不可能过河。因为从第i-1个bin到第i+1个bin，至少要跳过D+1距离。
B. 在一个bin内部可以从任意一片叶子跳到任意另一片叶子。

由A，B可得推论C:
C. 当且仅当从任意第 i 个bin都能够跳到第 i + 1个bin时，青蛙才能过河。推论C是本算法的直接理论依据

另外还有一种情况就是：
D. 如果相邻两个bin中都有1，那么当且仅当bin[ i-1 ]中的最后一个1和bin[ i ]中的第一个1的距离<=D时，这两个bin直接才算“可以跳过”。这是本算法要解决的核心问题。

------

我们在程序中维护一个长为X/D+1的数组ranges，这个ranges中的每一个对象是一个[min max]范围，代表"本range中的[第1个1的位置，最后一个1的位置]”。另外维护一个nImpassableGaps变量，其中记录了“无法逾越的间隔数”。比如一开始pond中有4个bin，那么从0无法到1，从1无法到2，从2无法到3, 所以nImpassableGaps = 3.

然后，每加入一片叶子，得到这片叶子所在的bin位置 i 。我们看是否因为这片叶子的加入，使得

1. 之前本来无法从 i 跳到 i + 1（即range[ i+1 ].min - range[ i ].max > D），但是现在可以了。
2. 之前本来无法从  i - 1 跳到 i，但是现在可以了。

如果1 和/或 2 成立，那么nImpassableGaps--;

如果此时nImpassableGaps降为0，则“现在”就是青蛙能跳过河的最初时刻。返回之即可。

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

将一个值加入到一个范围之内，以及判断1，2都只需要O(1)时间，所以总时间是O(N)。耗费的内存是bin的个数，即O(X/D)。

代码大概是这个样子的，其中有一个自定义的Range对象，我就不贴出来了，它的实现并不困难：

1. 
   
2. class Range {
   
3. ...
   
4. }
   
5. int solution(vector<int>& A, int X, int D)
   
6. {
   
7.         if (D >= X-1) return true;
   
8. 
   
9.         int nBins = X / D + 1;
   
10.         vector<Range> ranges(nBins);
    
11.         ranges[0].insert(0);
    
12.         ranges[nBins-1].insert(X-1);
    
13. 
    
14.         int nImpassableGaps = nBins-1;
    
15. 
    
16.         for (int i = 0; i < A.size(); ++i) {
    
17.                 int iBin = A[i]/D;        // index of the current bin
    
18. 
    
19.                 // If the new element does not increase range, then it has no impact on result.
    
20.                 if (ranges[iBin].contains(A[i]))
    
21.                         continue;
    
22. 
    
23.                 // Get MIN of the next range, and MAX of the previous range
    
24.                 // Special treatment for 0 and N-1th bin
    
25.                 int nextMin = (iBin == nBins-1)?INT_MAX:ranges[iBin+1].getMin();
    
26.                 int prevMax = (iBin == 0)?INT_MIN:ranges[iBin-1].getMax();
    
27. 
    
28.                 // Decide if the current bin is reachable from the next and previous range.
    
29.                 bool cannotReachNext = (ranges[iBin].isEmpty())?true:ranges[iBin].getMin() - prevMax > D;
    
30.                 bool cannotReachPrev = (ranges[iBin].isEmpty())?true:nextMin - ranges[iBin].getMax() > D;
    
31. 
    
32.                 // If iBin-1 and iBin were not connected previously
    
33.                 // but now they are (because of the newly added
    
34.                 // element), reduce nImpassbleGap
    
35.                 if (cannotReachNext && A[i] - prevMax <= D) {
    
36.                         nImpassableGaps--;
    
37.                 }
    
38. 
    
39.                 if (cannotReachPrev && nextMin - A[i] <= D) {
    
40.                         nImpassableGaps--;
    
41.                 }
    
42.                 ranges[iBin].insert(A[i]);
    
43.                 if (nImpassableGaps == 0) return i;
    
44.         }
    
45.         return -1;
    
46. }
    

复制代码

The above code was created by user stellari solely for private discussion on 1point3acres.com forum, and is not intended to be used as an answer in any coding test / competition.

我用并查集写了个，目前还无法确认对错。

1. /*
   
2. 6 7 3
   
3. 1 3 1 4 2 5
   
4. */
   
5. #include <algorithm>
   
6. #include <cstdio>
   
7. #include <cstring>
   
8. using namespace std;
   
9. 
   
10. int findRoot(int a[], int x)
    
11. {
    
12.     int r = x;
    
13.     while (r != a[r]) {
    
14.         r = a[r];
    
15.     }
    
16.     int k = x;
    
17.     while (x != r) {
    
18.         x = a[x];
    
19.         a[k] = r;
    
20.         k = x;
    
21.     }
    
22.     return r;
    
23. }
    
24. 
    
25. int solution(int A[], int N, int X, int D)
    
26. {
    
27.     int *dj;
    
28.    
    
29.     dj = new int[X + 1];
    
30.     memset(dj, 0, (X + 1) * sizeof(int));
    
31.    
    
32.     int i;
    
33.     for (i = 0; i <= X; ++i) {
    
34.         dj[i] = i;
    
35.     }
    
36.    
    
37.     for (i = 1; i <= D && i <= X; ++i) {
    
38.         dj[i] = 0;
    
39.     }
    
40.     if (findRoot(dj, X) == 0) {
    
41.         return 0;
    
42.     }
    
43.    
    
44.     int ll, rr;
    
45.     i = 0;
    
46.     while (i < N && findRoot(dj, X) != 0) {
    
47.         if (findRoot(dj, min(A[i] + D, X)) == findRoot(dj, A[i])) {
    
48.                         ++i;
    
49.             continue;
    
50.         }
    
51.         
    
52.         ll = A[i] + 1;
    
53.         rr = min(A[i] + D, X);
    
54.         
    
55.         if (dj[ll] == ll) {
    
56.             while (ll <= rr && dj[ll] == ll) {
    
57.                 dj[ll++] = dj[A[i]];
    
58.             }
    
59.         } else if (dj[rr] == rr) {
    
60.             while (ll <= rr && dj[rr] == rr) {
    
61.                 dj[rr--] = dj[A[i]];
    
62.             }
    
63.         } else {
    
64.             while (ll <= rr && dj[ll] != ll) {
    
65.                 ++ll;
    
66.             }
    
67.             while (ll <= rr && dj[rr] != rr) {
    
68.                 --rr;
    
69.             }
    
70.             while (ll <= rr) {
    
71.                 dj[ll++] = A[i];
    
72.             }
    
73.         }
    
74.         
    
75.                 if (findRoot(dj, X) == 0) {
    
76.                         break;
    
77.                 }
    
78.                 ++i;
    
79.     }
    
80.     delete[] dj;
    
81.    
    
82.     return i < N ? i : -1;
    
83. }
    
84. 
    
85. int main()
    
86. {
    
87.     const int MAXN = 100005;
    
88.     int *A, N, X, D;
    
89.    
    
90.     A = new int[MAXN];
    
91.     scanf("%d%d%d", &N, &X, &D);
    
92.     int i;
    
93.     for (i = 0; i < N; ++i) {
    
94.         scanf("%d", &A[i]);
    
95.     }
    
96.     printf("%d\n", solution(A, N, X, D));
    
97.     delete[] A;
    
98.    
    
99.     return 0;
    
100. }
     
101. 
     
102. /*
     
103. int main()
     
104. {
     
105.     const int MAXN = 100005;
     
106.         const int M = 100000;
     
107.     int *A, N, X, D;
     
108.    
     
109.     A = new int[MAXN];
     
110.         N = M;
     
111.         X = M;
     
112.         D = M / 2;
     
113.     int i;
     
114.     for (i = 0; i < N; ++i) {
     
115.                 A[i] = N - 1 - i;
     
116.     }
     
117.     printf("%d\n", solution(A, N, X, D));
     
118.     delete[] A;
     
119.    
     
120.     return 0;
     
121. }
     
122. */

复制代码

因为写得太繁琐了。。所以代码里没有多boundary cases考虑太多。
大致思路是这样：
比如从在K时刻有片树叶掉到了A[K]，那么从A[K] +1 到A[K] + D都可以从A[K]到达，然而你在不知道A[K]能不能到达的情况下，怎么记录这个事实呢，就得用并查集。把A[K] + 1 ~ A[K] + D全部连到A[K]上去
效率关键就在于这个连接的过程上，并查集的path compression不用说，肯定要用到。
我之前试着写了一版，看起来是O(n)复杂度，结果用10万的数据一跑就超时，说明一个问题：如果你碰见每个A[K]都把A[K] + 1 ~ A[K] + D的所有位置都检查一遍，那么复杂度其实是O(N * D) ，而不是O(N)。
所以要尽量避免重复扫描。

看下面这几个情况， 都是两个区间：
比如区间[a, b] [c, d] 表示[a, b]已经被确定为可到达，现在要从c出发，最远跳到d去

[1, 3] [2, 4]，由于相交得到[2, 3],那么只用处理[3, 4]即可
[3, 6] [2, 5]，[2, 5]被[3, 6]包含，所以如果[3, 6]可到达，那么[2, 5]就不需要处理了，直接跳过
[2, 4] [1, 3]，由于相交得到[2, 3],那么只用处理[1， 2]即可
[1, 4] [5, 7] ，不相交，所以[5, 7]全部都要处理

存在左边相交，右边相交，两边相交中间未知，完全不相交四种情况（第四种归到前两种中去）
分别处理即可。

总归，最终目的是判断位置X能否通过并查集一直关联到位置0去即可。

谁给点测试用例？

再补充一句：注册了codility之后就没在上面做过题。。感觉比hackerrank还难，基本没有简单题，纯打击人(x_x)
事实证明，当题目难度接近自己水平上限的时候，代码风格就开始变得乱七八糟。
想这题耗了一个小时，写好又花了一个钟头。感觉还是值。


所以能把代码写得正确、简洁易懂的人才最牛~

O(N)的复杂度就是看第i秒所能到达的最远距离是多少。如果没看错题目的话。。。

第 i 秒所能到达的最远距离 = max(第 i-1 秒所能到达的最远距离， 考虑A[i]的情况下的最远距离)。
复杂度应该是O(N)， 感觉是基本的dynamic programming

满城尽带黄金甲 发表于 2015-7-1 20:59
第 i 秒所能到达的最远距离 = max(第 i-1 秒所能到达的最远距离， 考虑A的情况下的最远距离)。
复杂度应该 ...

不对吧，比如X=7，D=2
A[0] = 1
A[1] = 5
A[2] = 3
那么第2秒就能到达X了
但第1秒的时候到不了5，所以那片叶子你暂时不能跳，得从3跳过去，所以直接O(n) DP应该不对

zhuli19901106 发表于 2015-7-1 21:24
不对吧，比如X=7，D=2
A[0] = 1
A[1] = 5

是不能跳啊，没说能跳啊，这样的情况第一秒能到的最远距离就是1啊

满城尽带黄金甲 发表于 2015-7-1 21:36
是不能跳啊，没说能跳啊，这样的情况第一秒能到的最远距离就是1啊

第0秒能到达3
第1秒还是3
第2秒能到达7

满城尽带黄金甲 发表于 2015-7-1 20:59
第 i 秒所能到达的最远距离 = max(第 i-1 秒所能到达的最远距离， 考虑A[ i ]的情况下的最远距离)。
复杂度应该 ...

那这就要求能在O(1)时间内得到“考虑A[ i ]的情况下的最远距离”。请问这点该如何做到？我想了一下没有想出什么好办法。