如何应对Vertical Sticks挑战？

Question

这个问题来自interviewstreet.com

给定整数数组Y = y1,...,yn,我们有n个线段,使得段i的端点是(i,0)和(i,yi).想象一下,从每个片段的顶部向左侧拍摄水平光线,当该光线接触到另一个片段或者它到达y轴时,该光线停止.我们构造一个n个整数的数组,v1,...,vn,其中vi等于从段i顶部射出的射线的长度.我们定义V(y1,...,yn)= v1 + ... + vn.

例如,如果我们有Y = [3,2,5,3,3,4,1,2],那么v1,...,v8 = [1,1,3,1,1,3,1, 2],如下图所示:

对于[1,...,n]的每个置换p,我们可以计算V(yp1,...,ypn).如果我们选择[1,...,n]的均匀随机置换p,V(yp1,...,ypn)的期望值是多少？

输入格式

第一行输入包含单个整数T(1 <= T <= 100).T测试案例如下.

每个测试用例的第一行是单个整数N(1 <= N <= 50).下一行包含由单个空格(0 <yi <= 1000)分隔的正整数y1,...,yN.

输出格式

对于每个测试用例输出预期值V(yp1,...,ypn),四舍五入到小数点后的两位数.

样本输入

6
3
1 2 3
3
3 3 3
3
2 2 3
4
10 2 4 4
5
10 10 10 5 10
6
1 2 3 4 5 6

样本输出

4.33
3.00
4.00
6.00
5.80
11.15

说明

情况1:我们有V(1,2,3)= 1 + 2 + 3 = 6,V(1,3,2)= 1 + 2 + 1 = 4,V(2,1,3)= 1+ 1 + 3 = 5,V(2,3,1)= 1 + 2 + 1 = 4,V(3,1,2)= 1 + 1 + 2 = 4,V(3,2,1)= 1 + 1 + 1 = 3.这些值的平均值为4.33.

情况2:无论排列是什么,V(yp1,yp2,yp3)= 1 + 1 + 1 = 3,所以答案是3.00.

情况3:V(y1,y2,y3)= V(y2,y1,y3)= 5,V(y1,y3,y2)= V(y2,y3,y1)= 4,V(y3,y1,y2) )= V(y3,y2,y1)= 3,这些值的平均值为4.00.

对于N = 50,问题的天真解决方案将永远运行.我相信可以通过独立计算每根棒的值来解决问题.我仍然需要知道是否有任何其他有效的方法来解决这个问题.我们在什么基础上独立计算每根棒的价值？

Answer 1

通过弄清楚我们可以解决这个问题:

如果将第k个棒放在第i个位置,那么该棒的预期射线长度是多少.

然后可以通过将所有位置的所有棒的所有预期长度相加来解决问题.

我们expected[k][i]是预期的射线长度ķ个棒放在我个位置,让num[k][i][length]是排列数ķ个棒放在我个位置与线长度等于length,则

expected[k][i] = sum( num[k][i][length] * length ) / N!

如何计算num[k][i][length]？例如,对于length=3,请考虑以下图表:

... ... GxxxI

哪里I是位置,3"X"意味着我们需要3支是严格然后较低I,而G意味着我们需要一个棍子至少高达I.让s_i是更小,则枝数k个棍子,和g_i可以是大于或等于枝数k个棒,那么我们可以选择任何一个 g_i摆在G位置,我们可以选择任何length的s_i填写这个x位置,所以我们有:

num[k][i][length] = P(s_i, length) * g_i * P(n-length-1-1)

如果之前I的所有位置都小于那么I,我们不需要更大的支持G,即xxxI....,我们有:

num[k][i][length] = P(s_i, length) * P(n-length-1)

这是一段可以解决这个问题的Python代码:

def solve(n, ys):
    ret = 0
    for y_i in ys:
        s_i = len(filter(lambda x: x < y_i, ys))
        g_i = len(filter(lambda x: x >= y_i, ys)) - 1

        for i in range(n):
            for length in range(1, i+1):
                if length == i:
                    t_ret = combination[s_i][length] * factorial[length] * factorial[ n - length - 1 ] 
                else:
                    t_ret = combination[s_i][length] * factorial[length] * g_i * factorial[ n - length - 1 - 1 ]
                ret += t_ret * length

    return ret * 1.0 / factorial[n] + n

Answer 2

这是与https://cs.stackexchange.com/questions/1076/how-to-approach-vertical-sticks-challenge相同的问题,我在那里的回答(这比前面给出的那些简单一点)是:

想象一个不同的问题:如果你必须k在n插槽中放置相同高度的杆,那么杆之间的预期距离(以及第一个杆和一个名义槽0之间的预期距离,以及最后一个杆和一个名义槽之间的预期距离n+1)是(n+1)/(k+1)因为k+1在长度上有空隙n+1.

回到这个问题,一个特定的棒感兴趣的是多少棒(包括它自身)高或高.如果是这样k,那么之前的预期差距也是如此 (n+1)/(k+1).

所以算法只是为每个棒找到这个值并加上期望值.例如,从高度开始,3,2,5,3,3,4,1,2具有更大或相等高度的棒的数量是5,7,1,5,5,2,8,7预期的9/6+9/8+9/2+9/6+9/6+9/3+9/9+9/8 = 15.25.

这很容易编程:例如R中的单行

V <- function(Y){(length(Y) + 1) * sum(1 / (rowSums(outer(Y, Y, "<=")) + 1) )}

给出原始问题中样本输出中的值

> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15