解释这个O(n log n)算法用于猫/蛋投掷问题。

Question

解释这个O(n log n)算法用于猫/蛋投掷问题。

algorithm

10

这个问题（需要扔多少只猫出去才能确定猫最多能在哪一层楼活下来，其实很残忍），有一个O(n^3)的可接受答案。该问题等同于Google Code Jam，对于N=2000000000应该是可以解决的。

看起来O(n^3)的解决方案不足以解决它。从解决方案页面中看，jdmetz的解决方案(#2)似乎是O(n log n)。我不太理解这个算法。有人能解释一下吗？

编辑

- ripper234

10

我认为解释一个算法是适合在StackOverflow上提问的。 - Mark Byers

一旦上线，它可以迁移到算法：http://area51.stackexchange.com/proposals/5120/practical-algorithms-and-data-structures - ripper234

如果这个算法是 O(n*logn)（无论你用哪个变量表示 n），它仍然太慢了。n 的值高达 10^9。 - Nikita Rybak

如果您看到我对答案的最新更新，您会发现我可以做得比O(n lg n)更好。 - Peter Taylor

2个回答

2

考虑函数f(x,y)，它给出了在x次扔和y次死亡的限制下，您可以测试的楼层数。如果第一次扔结果为死亡，则您还剩下x-1次扔和y-1次死亡，因此您可以检查f(x-1，y-1)层。如果第一次扔不导致死亡，则您还有x-1次扔和y次死亡，因此您可以检查从您扔出的那一层楼上方的f(x-1，y)层楼。因此，我们有递归f(x,y)=f(x-1，y-1)+f(x-1，y)+1。基本条件是f(x，0)=0（因为如果您进行了一次扔，就会冒着死亡的风险，因此您不能进行任何扔，并且甚至无法检查第一层），以及f(1，x)=1，其中x>0（您必须从第一层楼扔出唯一的一次，因为如果您从更高的楼层扔出并死亡，您将没有结果）。

现在，考虑函数g(x，y)=SUM 1<=r<=y的^xC_r。（这是一个二项式系数，表示为x选择r。我不认为此网站支持TeX符号）。断言是f(x，y)=g(x，y)。要检查基本情况，请考虑g(x，0)是0个元素的总和，因此匹配；并且y>0时g(1，y)给出¹C₁=1。因此，只需检查g是否满足递归关系。

g(x-1，y-1)+g(x-1，y)+1=SUM 1<=r<=y-1 ^x-1C_r+SUM 1<=r<=y ^x-1C_r+1

g(x-1，y-1)+g(x-1，y)+1=SUM 2<=r<=y ^x-1C_r-1+SUM 1<=r<=y ^x-1C_r+1

g(x-1，y-1)+g(x-1，y)+1=SUM 2<=r<=y ^x-1C_r-1+SUM 1<=r<=y ^x-1C_r+^x-1C₀

g(x-1, y-1) + g(x-1, y) + 1 = SUM 1<=r<=y (^x-1C_r-1 + ^x-1C_r)

g(x-1, y-1) + g(x-1, y) + 1 = SUM 1<=r<=y (^xC_r)

g(x-1, y-1) + g(x-1, y) + 1 = g(x, y)

QED

实际上，这可以通过将其视为组合问题直接导出。如果我们充分利用获得的每个信息位，则每个可能的生存或死亡序列都对应于不同的最大楼层。例如，对于三次投掷，一个允许死亡，可能性是死亡；存活死亡；存活存活死亡；或存活存活存活。但是，我们必须削减没有死亡的情况，因为在这种情况下，我们还没有确定楼层。因此，如果我们有x次投掷和y次允许死亡，我们可以有实际死亡人数从1到y，对于每个死亡人数，我们有^xC_r种可能的序列。（如果r = y，则在第y次死亡后的任何“生还”实际上都是“没有投掷”）。

jdmetz对F的解决方案包括评估g（D，B）。由于该总和没有封闭的超几何形式（该事实可以使用Gosper算法证明），因此无法以比O（min（D，B））更好的时间完成。

补充说明：实际上，原问题的所有三个部分都可以在线性时间内完成（假设乘法和算术为常量时间操作，到目前为止我们一直是这样 - 虽然不是真的，但我们将其放在一边）。jdmetz解决方案中的O（n lg n）操作是查找最小的D，使得f（D，B）>= F。

如果我们将原始递归式f(D, B) = f(D-1, B-1) + f(D-1, B) + 1和g的差异组合起来，f(D, B) = f(D, B-1) + ^DC_B，我们得到f(D, B) = 2 * f(D-1, B) + 1 - ^D-1C_B。然后我们可以使用公式^aC_b = ^a-1C_b * a / (a - b)从1开始循环D。

    private static int d_opt(final long f, final int b)
    {
        int d = 0, dCb = 0;
        long f_db = 0;
        while (f_db < f)
        {
            dCb = (d == b) ? 1 : d * dCb / (d-b);
            f_db = 2 * f_db + 1 - dCb;
            d++;
        }
        return d;
    }

- Peter Taylor

抱歉，我看错了文件。看一下jdmetz的解决方案-它对于getMaxF()和getMinB()是O(n)，而getMinD()是使用二分查找getMaxF()实现的-总复杂度是O(n log n)。 - ripper234

我认为F可能与Pascal三角形有关，现在我看到我是正确的。还没有证明它，但这就是jdmetz代码所做的。第一个观察：如果j>i，则F[i][j]=F[i][i]，因为你不能有比扔出的猫更多的死亡。因此，我们只考虑i>=0，0<=j<=i形成的三角形。如果我们使i索引行，F[i][j]+1形成伯努利三角形（http://oeis.org/wiki/Bernoulli%27s_triangle），即Pascal三角形的行的部分和。 - Peter Taylor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nikita Rybak · Accepted Answer

最优解实际上是O(D*B)（使用问题的术语），但作者注意到对于大多数D和B，答案将大于2^32，因此可以返回-1。
因此，他引入了maxn等于1100-最大的D和F，这是有意义的计算。
对于D，B = 10000，他立即返回-1。对于D，B = 100，使用下面的递归公式。仅对于一些“边角值”，例如D = 10000，B = 2，才使用直接公式。（有关“直接公式”的详细信息，请参见他的评论）

对于D，B < maxn，作者在评论中提供了公式：f(d,b) = f(d-1,b)+f(d-1,b-1)+1。这里的函数f返回最大楼层数，在该楼层以下不能超过d次尝试并且不能超过b个鸡蛋确定“断点”。
公式本身应该是不言自明的：无论我们在哪一层扔第一个鸡蛋，都有两个结果。它可能会破裂，然后我们可以检查多达f(d-1，b-1)层楼下。或者它可以“存活”，然后我们可以检查多达f(d-1，b)层楼上。加上当前楼层，总共是f(d-1，b)+f(d-1，b-1)+1。
现在，它可以很容易地编码为DP（动态规划）。如果您将无限制（2^32）的检查排除在外，则会变得非常干净。

    for (int i = 1; i < maxn; ++i) {
        for (int j = 1; j < maxn; ++j) {
            f[i][j] = f[i - 1][j - 1] + f[i - 1][j] + 1;
        }
    }

当我们有数组f[D][B]存储这些结果时，查找D'和B'是进行二分查找的。（因为函数f在d和b方面都是单调增长的。）

附注：虽然我在回答“猫咪”问题时说有更快的解决方案，但实际上这比我想象中的还要酷哦！感谢您和sclo（作者）!