一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4402|回复: 46
收起左侧

[算法题] CMU MSIT-SE 2015的青蛙题 FrogPond,求解

[复制链接] |试试Instant~ |关注本帖
albusshin 发表于 2015-7-1 11:56:39 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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


QQ图片20150622120954.jpg QQ图片20150622121153.jpg




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

stellari 发表于 2015-7-1 21:37:12 | 显示全部楼层
本帖最后由 stellari 于 2015-7-1 21:59 编辑

这题其实和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. class Range {
  2. ...
  3. }
  4. int solution(vector<int>& A, int X, int D)
  5. {
  6.         if (D >= X-1) return true;

  7.         int nBins = X / D + 1;
  8.         vector<Range> ranges(nBins);
  9.         ranges[0].insert(0);
  10.         ranges[nBins-1].insert(X-1);

  11.         int nImpassableGaps = nBins-1;

  12.         for (int i = 0; i < A.size(); ++i) {
  13.                 int iBin = A[i]/D;        // index of the current bin

  14.                 // If the new element does not increase range, then it has no impact on result.
  15.                 if (ranges[iBin].contains(A[i]))
  16.                         continue;

  17.                 // Get MIN of the next range, and MAX of the previous range
  18.                 // Special treatment for 0 and N-1th bin
  19.                 int nextMin = (iBin == nBins-1)?INT_MAX:ranges[iBin+1].getMin();
  20.                 int prevMax = (iBin == 0)?INT_MIN:ranges[iBin-1].getMax();

  21.                 // Decide if the current bin is reachable from the next and previous range.
  22.                 bool cannotReachNext = (ranges[iBin].isEmpty())?true:ranges[iBin].getMin() - prevMax > D;
  23.                 bool cannotReachPrev = (ranges[iBin].isEmpty())?true:nextMin - ranges[iBin].getMax() > D;

  24.                 // If iBin-1 and iBin were not connected previously
  25.                 // but now they are (because of the newly added
  26.                 // element), reduce nImpassbleGap
  27.                 if (cannotReachNext && A[i] - prevMax <= D) {
  28.                         nImpassableGaps--;
  29.                 }

  30.                 if (cannotReachPrev && nextMin - A[i] <= D) {
  31.                         nImpassableGaps--;
  32.                 }
  33.                 ranges[iBin].insert(A[i]);
  34.                 if (nImpassableGaps == 0) return i;
  35.         }
  36.         return -1;
  37. }
复制代码
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.

评分

2

查看全部评分

回复 支持 2 反对 0

使用道具 举报

zhuli19901106 发表于 2015-7-1 16:04:12 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-1 16:44 编辑

我用并查集写了个,目前还无法确认对错。
  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. int findRoot(int a[], int x)
  10. {
  11.     int r = x;
  12.     while (r != a[r]) {
  13.         r = a[r];
  14.     }
  15.     int k = x;
  16.     while (x != r) {
  17.         x = a[x];
  18.         a[k] = r;
  19.         k = x;
  20.     }
  21.     return r;
  22. }

  23. int solution(int A[], int N, int X, int D)
  24. {
  25.     int *dj;
  26.    
  27.     dj = new int[X + 1];
  28.     memset(dj, 0, (X + 1) * sizeof(int));
  29.    
  30.     int i;
  31.     for (i = 0; i <= X; ++i) {
  32.         dj[i] = i;
  33.     }
  34.    
  35.     for (i = 1; i <= D && i <= X; ++i) {
  36.         dj[i] = 0;
  37.     }
  38.     if (findRoot(dj, X) == 0) {
  39.         return 0;
  40.     }
  41.    
  42.     int ll, rr;
  43.     i = 0;
  44.     while (i < N && findRoot(dj, X) != 0) {
  45.         if (findRoot(dj, min(A[i] + D, X)) == findRoot(dj, A[i])) {
  46.                         ++i;
  47.             continue;
  48.         }
  49.         
  50.         ll = A[i] + 1;
  51.         rr = min(A[i] + D, X);
  52.         
  53.         if (dj[ll] == ll) {
  54.             while (ll <= rr && dj[ll] == ll) {
  55.                 dj[ll++] = dj[A[i]];
  56.             }
  57.         } else if (dj[rr] == rr) {
  58.             while (ll <= rr && dj[rr] == rr) {
  59.                 dj[rr--] = dj[A[i]];
  60.             }
  61.         } else {
  62.             while (ll <= rr && dj[ll] != ll) {
  63.                 ++ll;
  64.             }
  65.             while (ll <= rr && dj[rr] != rr) {
  66.                 --rr;
  67.             }
  68.             while (ll <= rr) {
  69.                 dj[ll++] = A[i];
  70.             }
  71.         }
  72.         
  73.                 if (findRoot(dj, X) == 0) {
  74.                         break;
  75.                 }
  76.                 ++i;
  77.     }
  78.     delete[] dj;
  79.    
  80.     return i < N ? i : -1;
  81. }

  82. int main()
  83. {
  84.     const int MAXN = 100005;
  85.     int *A, N, X, D;
  86.    
  87.     A = new int[MAXN];
  88.     scanf("%d%d%d", &N, &X, &D);
  89.     int i;
  90.     for (i = 0; i < N; ++i) {
  91.         scanf("%d", &A[i]);
  92.     }
  93.     printf("%d\n", solution(A, N, X, D));
  94.     delete[] A;
  95.    
  96.     return 0;
  97. }

  98. /*
  99. int main()
  100. {
  101.     const int MAXN = 100005;
  102.         const int M = 100000;
  103.     int *A, N, X, D;
  104.    
  105.     A = new int[MAXN];
  106.         N = M;
  107.         X = M;
  108.         D = M / 2;
  109.     int i;
  110.     for (i = 0; i < N; ++i) {
  111.                 A[i] = N - 1 - i;
  112.     }
  113.     printf("%d\n", solution(A, N, X, D));
  114.     delete[] A;
  115.    
  116.     return 0;
  117. }
  118. */
复制代码
因为写得太繁琐了。。所以代码里没有多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去即可。

谁给点测试用例?

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

zhuli19901106 发表于 2015-7-1 16:18:35 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-1 16:22 编辑

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


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

回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2015-7-1 20:15:48 | 显示全部楼层
O(N)的复杂度就是看第i秒所能到达的最远距离是多少。如果没看错题目的话。。。
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2015-7-1 20:59:49 | 显示全部楼层
第 i 秒所能到达的最远距离 = max(第 i-1 秒所能到达的最远距离, 考虑A[i]的情况下的最远距离)。
复杂度应该是O(N), 感觉是基本的dynamic programming
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-1 21:24:23 | 显示全部楼层
满城尽带黄金甲 发表于 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应该不对
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2015-7-1 21:36:51 | 显示全部楼层
zhuli19901106 发表于 2015-7-1 21:24
不对吧,比如X=7,D=2
A[0] = 1
A[1] = 5

是不能跳啊,没说能跳啊,这样的情况第一秒能到的最远距离就是1啊
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-1 21:55:34 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-1 21:58 编辑
满城尽带黄金甲 发表于 2015-7-1 21:36
是不能跳啊,没说能跳啊,这样的情况第一秒能到的最远距离就是1啊

第0秒能到达3
第1秒还是3
第2秒能到达7
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-1 21:55:39 | 显示全部楼层
满城尽带黄金甲 发表于 2015-7-1 20:59
第 i 秒所能到达的最远距离 = max(第 i-1 秒所能到达的最远距离, 考虑A[ i ]的情况下的最远距离)。
复杂度应该 ...


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

使用道具 举报

zhuli19901106 发表于 2015-7-1 22:02:00 | 显示全部楼层
stellari 发表于 2015-7-1 21:55
那这就要求能在O(1)时间内得到“考虑A[ i ]的情况下的最远距离”。请问这点该如何做到?我想了一下没有 ...

我感觉O(1)应该搞不到的,上面的例子举了
比如远处先掉一片叶子,这时太远你还不能跳过去
然后近处再落一片,这时你才能一口气从近处跳到远处
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2015-7-1 22:19:32 | 显示全部楼层
stellari 发表于 2015-7-1 21:55
那这就要求能在O(1)时间内得到“考虑A[ i ]的情况下的最远距离”。请问这点该如何做到?我想了一下没有 ...

题目中给了空间复杂度O(X), 暴力点就开个数组,记录每个位置是否是可达或联通的
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-1 22:21:51 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-1 22:22 编辑
满城尽带黄金甲 发表于 2015-7-1 22:19
题目中给了空间复杂度O(X), 暴力点就开个数组,记录每个位置是否是可达或联通的

要不动手写一个?恕我直言,基本一句话能讲完思路的人,代码写出来都不对。
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2015-7-1 22:25:39 | 显示全部楼层
zhuli19901106 发表于 2015-7-1 22:02
我感觉O(1)应该搞不到的,上面的例子举了
比如远处先掉一片叶子,这时太远你还不能跳过去
然后近处再落 ...

开一个长度X的数组,在循环体中:
{
    讲第i秒降落的叶子所联通的位置置为true;
    青蛙往前走,直到下一位置为false或到达重点为止;
}
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-1 22:29:33 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-1 22:32 编辑
满城尽带黄金甲 发表于 2015-7-1 22:25
开一个长度X的数组,在循环体中:
{
    讲第i秒降落的叶子所联通的位置置为true;

X = 100000 D = 50000

A[0] = 100000
A[1] = 99999
...
A[99999] = 1
于是在前几万次循环内青蛙不能前进,每次都刷50000级别的位置,TLE了
我考虑的第一个bad case就是这个,还可以有其他的bad case。所以说要用运行才知道,伪代码不打算用来面试吧。

其实还是那句话,讨论算法题感觉不上代码都是白搭,否则表面难度总会低于实际难度。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-1 22:32:09 | 显示全部楼层
zhuli19901106 发表于 2015-7-1 22:29
X = 100000 D = 50000

A[0] = 100000

请问一下是否有某个OJ可以刷这道题?
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2015-7-1 22:32:50 | 显示全部楼层
zhuli19901106 发表于 2015-7-1 21:24
不对吧,比如X=7,D=2
A[0] = 1
A[1] = 5

用你的例子好了, boolean[] bridge = new boolean[X];
第0秒,叶子降落在位置1, 那么bridge[0]~bridge[2]置为true, 青蛙可以走到位置3;
第1秒,叶子降落在位置5, 那么bridge[4]~bridge[6]置为true, 青蛙原地不动,因为bridge[3]是false;
第2秒,叶子降落在位置3, 那么bridge[2]~bridge[4]置为true, 青蛙可以走到位置7;到终点了
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-1 22:32:58 | 显示全部楼层
stellari 发表于 2015-7-1 22:32
请问一下是否有某个OJ可以刷这道题?

没有,但我印象中早年在POJ还是哪儿见过类似的青蛙跳问题,可能不大一样吧。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-1 22:35:57 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-1 22:37 编辑
满城尽带黄金甲 发表于 2015-7-1 22:32
用你的例子好了, boolean[] bridge = new boolean[X];
第0秒,叶子降落在位置1, 那么bridge[0]~bridge ...

除了保证算法正确性,还得考虑average case和worst case的效率。我觉得你的思路是对的,不过如果能够找到O(N * D)的worst case,那还是不能AC的。所以建议动手敲一个,然后想一些十万规模的测试数据,尽量追求worst case。
刚才写错了,应该是O(N * D),此处N和D都可以到10万,所以worst case如果到了这个程度就不可接受了。
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2015-7-1 22:38:11 | 显示全部楼层
zhuli19901106 发表于 2015-7-1 22:29
X = 100000 D = 50000

A[0] = 100000

A中的element不能超过X-1,A[0]是不能为100000的,不过没明白你的点在哪,如果是说有重复操作,那么碰到true的位置就停止置位好咯
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 01:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表