Как подойти к решению «Вертикальные палки»

Эта проблема взята из интервьюstreet.com

Нам дан массив целых чисел который представляет линейных сегментов, так что конечными точками сегмента являются и . Представьте, что от вершины каждого сегмента горизонтальный луч выстреливает влево, и этот луч останавливается, когда он касается другого сегмента или достигает оси y. Мы строим массив из n целых чисел, , где равна длине луча, снятого с вершины сегмента . Определим .$Y=\{y_1,...,y_n\}$$n$$i$$(i, 0)$$(i, y_i)$$v_1, ..., v_n$$v_i$$i$$V(y_1, ..., y_n) = v_1 + ... + v_n$

Например, если у нас есть , то , как показано на рисунке ниже:$Y=[3,2,5,3,3,4,1,2]$$[v_1, ..., v_8] = [1,1,3,1,1,3,1,2]$

Для каждой перестановки из мы можем вычислить . Если мы выберем равномерно случайную перестановку из , каково ожидаемое значение ?[ 1 , . , , , П ] V ( у р 1 , . . . , У п п ) р [ 1 , . , , , П ] V ( у р 1 , . . . , У п п$p$$[1,...,n]$$V(y_{p_1}, ..., y_{p_n})$$p$$[1,...,n]$$V(y_{p_1}, ..., y_{p_n})$

Если мы решим эту проблему, используя наивный подход, она не будет эффективной и будет работать практически всегда при . Я полагаю, что мы можем подойти к этой проблеме, самостоятельно рассчитав ожидаемое значение для каждой палки, но мне все еще нужно знать, есть ли другой эффективный подход к этой проблеме. На каком основании мы можем рассчитать ожидаемое значение для каждой палки независимо?v $n=50$$v_i$

Представьте себе другую проблему: если вам пришлось поместить палочек одинаковой высоты в слотов, то ожидаемое расстояние между палками (и ожидаемое расстояние между первой палкой и условной щелью , а также ожидаемое расстояние между последней палкой и условной слот ) равен поскольку есть промежутков, чтобы соответствовать длине .n 0 n + 1 n + $k$$n$$0$$n+1$ k+1n+$\frac{n+1}{k+1}$$k+1$$n+1$

Возвращаясь к этой проблеме, конкретный джойстик интересуется, сколько стиков (включая себя) имеют высоту или выше. Если это число равно , то ожидаемый разрыв слева от него также равен .н + $k$$\frac{n+1}{k+1}$

Таким образом, алгоритм состоит в том, чтобы просто найти это значение для каждой палки и сложить ожидание. Например, начиная с высоты , количество палочек с большей или равной высотой равно поэтому ожидание равно .[ 5 , 7 , 1 , 5 , 5 , 2 , 8 , 7 ] $[3,2,5,3,3,4,1,2]$$[5,7,1,5,5,2,8,7]$$\frac96+\frac98+\frac92+\frac96+\frac96+\frac93+\frac99+\frac98 = 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

Решение Генри более простое и общее, чем это!

---

$E[V]$ составляет примерно половину ожидаемого числа сравнений, выполненных рандомизированной быстрой сортировкой.

Предполагая, что палки имеют различную высоту , мы можем вывести решение в замкнутой форме следующим образом.$E[Y]$

Для любых индексов , пусть если и противном случае. (Если элементы являются не различны, то означает , что является строго больше , чем каждый элемент .)$i\le j$$X_{ij} = 1$X i j = 0 $Y_j = \max\{Y_i,...,Y_j\}$$X_{ij}=0$$Y$Y j { Y i , … , Y j - 1$X_{ij}=1$$Y_j$$\{Y_i, \dots, Y_{j-1}\}$

Тогда для любого индекса имеем (понимаете почему?) И, следовательно, v j = ∑ j i = 1 X i j V = n ∑ j = $j$$v_j = \sum_{i=1}^j X_{ij}$

$$V = \sum_{j=1}^n v_j = \sum_{j=1}^n \sum_{i=1}^j X_{ij}.$$

Линейность ожидания сразу подразумевает, что

$$E[V] = E\bigg[\sum_{1\le i\le j\le n} X_{ij}\bigg] = \sum_{1\le i\le j\le n} E[X_{ij}].$$

Поскольку равен или , мы имеем . 01E[ X i j ]=Pr[ X i j =1$X_{ij}$$0$$1$$E[X_{ij}] = \Pr[X_{ij}=1]$

Наконец-и это важно бит , поскольку значения в являются различными и переставляются равномерно, каждый элемент подмножества одинаково вероятно, будет крупнейшим элементом этого подмножества. Таким образом, . (Если элементы не различны, у нас все еще есть .)$Y$Pr [ X i j = 1 ] = $\{Y_i,...,Y_j\}$ YPr[Xij=1]≤$\Pr[X_{ij}=1] = \frac{1}{j-i+1}$$Y$$\Pr[X_{ij}=1] \le \frac{1}{j-i+1}$

А теперь у нас просто математика. где обозначает номер й гармоники . Hn

$$\begin{aligned} E[V] &= \sum_{j=1}^n \sum_{i=1}^j E[X_{ij}] & [\text{linearity}]\\ &= \sum_{j=1}^n \sum_{i=1}^j \frac{1}{j-i+1} & [\text{uniformity}]\\ &= \sum_{j=1}^n \sum_{h=1}^j \frac{1}{h} & [h = j-i+1]\\ &= \sum_{h=1}^n \sum_{j=h}^n \frac{1}{h} & [1\le h\le j\le n]\\ &= \sum_{h=1}^n \frac{n-h+1}{h}\\ &= \left((n+1)\sum_{h=1}^n \frac{1}{h}\right) - \left(\sum_{h=1}^n 1\right)\\ &= (n+1)H_n - n \end{aligned}$$ $H_n$$n$

Теперь должно быть тривиально вычислять (с точностью до плавающей запятой) за время.O ( n $E[V]$$O(n)$

Как уже упоминалось в комментариях, вы можете использовать линейность ожиданий.

Сортируйте : .y 1 ≤ y 2 ≤ ⋯ ≤ y $y$$y_1 \le y_2 \le \dots \le y_n$

Для каждого рассмотрим ожидаемое значение .$y_i$$v_i = E[v_i]$

Тогда$E[\sum_{i=1}^{n} v_i] = \sum_{i=1}^{n} E[v_i]$

Одним простым и наивным способом вычисления было бы сначала исправить позицию для . Скажи .$E[v_i]$$y_i$$j$

Теперь вычислите вероятность того, что в позиции вас есть значение .$j-1$$\ge y_i$

Тогда вероятность того, что в вас есть значение а в вас есть значение$j-1$$\lt y_i$$j-2$$\ge y_i$

и так далее, что позволит вам вычислить .$E[v_i]$

Вы, вероятно, можете сделать это быстрее, фактически выполнив математику и получив формулу (хотя я сам не пробовал).

Надеюсь, это поможет.

Расширяя ответ @Aryabhata:

Зафиксируем и предположим, что элемент находится в позиции . Точное значение высоты не имеет значения, имеет значение, являются ли элементы больше или равны или нет. Поэтому рассмотрим набор элементов , где равен 1, если , и равен 0 в противном случае.y i j y i Z ( i ) z ( i ) k y k$i$$y_i$$j$$y_i$$Z^{(i)}$$z_k^{(i)}$$y_k\geq y_i$$z_k^{(i)}$

Перестановка на множестве индуцирует соответствующую перестановку на множестве . Рассмотрим, например, следующую перестановку множества : «01000 (1) ». Элемент в скобках находится в позиции , а элементы, обозначенные " ", не имеют значения. Y Z ( i ) … $Z^{(i)}$$Y$$Z^{(i)}$$\dots$$z_i^{(i)}$$j$$\dots$

Тогда значение равно 1 плюс длина серии последовательных нулей слева от . Отсюда следует, что на самом деле равно 1 плюс ожидаемая длина последовательных нулей, пока не будет встречено первое «1», если мы выберем не более бит из набора (без замены). Это напоминает геометрическое распределение, за исключением того, что оно будет без замены (и ограниченного числа розыгрышей). Ожидание должно быть принято на , а также , как равномерный выбор на множестве позиций .z ( i ) i E $v_i$$z_i^{(i)}$$\mathbb{E}\left(v_i\right)$$j-1$$Z^{(i)} \setminus \\{z_i^{(i)} \\}${ 1 , … , n $j$ $\{1,\dots,n \}$

Как только это вычислено (по этим линиям ), мы можем следовать строкам ответа @ Aryabhata.

Я не очень понимаю, что вы требуете, из тегов кажется, что вы ищете алгоритм.

если да, какова ожидаемая сложность времени? говоря: «Если мы решим эту проблему, используя наивный подход, она не будет эффективной и будет работать практически всегда для n = 50». мне кажется, что ваш наивный подход решает это в экспоненциальном времени.

Я имею в виду алгоритм O (N ^ 2), хотя.

assume int y[n], v[n] where v[i] initialized with 1; as described in the question
for (i=1;i<n;i++) 
   for ( j=i-1 ; j>=0 && y[j]<y[i] ; j--) v[i]++;