algorithm - 如何应对 Vertical Sticks 挑战？

Question

这个问题摘自interviewstreet.com

Given array of integers Y=y1,...,yn, we have n line segments such that endpoints of segment i are (i, 0) and (i, yi). Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, v1, ..., vn, where vi is equal to length of ray shot from the top of segment i. We define V(y1, ..., yn) = v1 + ... + vn.

For example, if we have Y=[3,2,5,3,3,4,1,2], then v1, ..., v8 = [1,1,3,1,1,3,1,2], as shown in the picture below:

For each permutation p of [1,...,n], we can calculate V(yp1, ..., ypn). If we choose a uniformly random permutation p of [1,...,n], what is the expected value of V(yp1, ..., ypn)?

Input Format

First line of input contains a single integer T (1 <= T <= 100). T test cases follow.

First line of each test-case is a single integer N (1 <= N <= 50). Next line contains positive integer numbers y1, ..., yN separated by a single space (0 < yi <= 1000).

Output Format

For each test-case output expected value of V(yp1, ..., ypn), rounded to two digits after the decimal point.

Sample Input

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

Sample Output

4.33
3.00
4.00
6.00
5.80
11.15

Explanation

Case 1: We have 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. Average of these values is 4.33.

Case 2: No matter what the permutation is, V(yp1, yp2, yp3) = 1+1+1 = 3, so the answer is 3.00.

Case 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, and average of these values is 4.00.

对于 N=50 的问题，一个天真的解决方案将永远运行。我相信这个问题可以通过为每根棍子独立计算一个值来解决。我仍然需要知道是否有任何其他有效的方法来解决这个问题。我们必须在什么基础上独立计算每根棍子的值(value)？

Answer 1

我们可以解决这个问题，方法是:

if the k th stick is put in i th position, what is the expected ray-length of this stick.

那么问题可以通过将所有位置的所有棍子的所有预期长度相加来解决。

设 expected[k][i] 是第 k 个棍子放在第 i 个位置的预期射线长度，令 num[k][i][length] 是第 k 个棍子放在第 i 个位置且光线长度等于的排列数长度，然后

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 个木棍的木棍数量到第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