如何解決垂直棒挑戰？

Question

此問題是從interviewstreet.com

採取鑑於整數數組Y = Y1，...，YN，我們有N線段，使得段的端點 我是（i，0）和（i，義）。想象一下，從每個段的頂部 水平射線被射到左側，並且這條射線接觸另一個段或它碰到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,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] ，3,1,2]，如示於下圖：

對於每個排列p [1，...，N]，我們可以計算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

正如您所說的，注意到我們可以獨立解決每個棒的問題。假設F（i，len）是排列的數量，那麼來自棍子i的射線恰好是len。
然後回答是

（總和（由我，LEN）F（I，LEN）* LEN）/（N！）

所有剩下的就是數F（I，LEN ）。令a（i）爲棒數j，即y_j < = y_i。 b（i） - 棒的數量，即b_j> b_i。

爲了得到長度爲len的光線，我們需要有這樣的情況。

B, l...l, O 
    len-1 times 

其中O - 是棍子#i。乙 - 是堅持更大的長度，或開始。 l - 堅持heigth，小於iith。

這給了我們2種情況：
1）B是開頭，這個可以通過P(a(i), len-1) * (b(i)+a(i)-(len-1))!的方式實現。
2）B更大的棒，這可以通過P(a(i), len-1)*b(i)*(b(i)+a(i)-len)!*(n-len)的方式實現。

編輯：校正的B（i）如（MUL）代替（ⅰ）的情況下，第二項2.

Answer 2

我們可以解決這個問題，通過弄明白：

如果這個棒的預期射線長度是多少？這個棒的預期射線長度是多少？

那麼問題可以通過將所有位置的所有棒的所有預期長度相加來解決。

讓​​是ķ個棒的預期射線長度放入我個位置，讓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位置枝的數量，我們可以選擇任何s_ilength填補x位置，所以我們有：

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

在情況下之前所有的位置0都較小然後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 3

這是同樣的問題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))} 

一行給出了sample output in the original problem

> 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