Cómo abordar el desafío Vertical Sticks

Este problema está tomado de interviewstreet.com

Se nos da una matriz de enteros $Y=\{y_1,...,y_n\}$ que representa $n$ segmentos de línea de modo que los puntos finales del segmento son ( i , 0 ) y ( i , y i ) . Imagine que desde la parte superior de cada segmento se dispara un rayo horizontal hacia la izquierda, y este rayo se detiene cuando toca otro segmento o golpea el eje y. Construimos un conjunto de n enteros, v 1 , . . . , vv i i V ( y 1 , . . . , Y n ) = v 1 + . . . + v $i$$(i, 0)$$(i, y_i)$$v_1, ..., v_n$ , dondees igual a la longitud del disparo de rayos desde la parte superior del segmento. Definimos.$v_i$$i$$V(y_1, ..., y_n) = v_1 + ... + v_n$

Por ejemplo, si tenemos , entonces , como se muestra en la imagen a continuación:$Y=[3,2,5,3,3,4,1,2]$$[v_1, ..., v_8] = [1,1,3,1,1,3,1,2]$

Para cada permutación de , podemos calcular . Si elegimos una permutación uniformemente aleatoria de , ¿cuál es el valor esperado de ?[ 1 , . . . , N ] V ( y p 1 , . . . , Y p n ) p [ 1 , . . . , N ] V ( y p 1 , . . . , Y p n$p$$[1,...,n]$$V(y_{p_1}, ..., y_{p_n})$$p$$[1,...,n]$$V(y_{p_1}, ..., y_{p_n})$

Si resolvemos este problema usando el enfoque ingenuo, no será eficiente y se ejecutará prácticamente para siempre para . Creo que podemos abordar este problema calculando de forma independiente el valor esperado de para cada palo, pero aún necesito saber si existe otro enfoque eficiente para este problema. ¿Sobre qué base podemos calcular el valor esperado para cada barra de forma independiente?v $n=50$$v_i$

Imagine un problema diferente: si tuviera que colocar palos de igual altura en n ranuras, entonces la distancia esperada entre los palos (y la distancia esperada entre el primer palo y una ranura nocional 0 , y la distancia esperada entre el último palo y un nocional ranura n + 1 ) es n + $k$$n$$0$$n+1$ ya que hayespacios dek+1para caber en una longitudn+1.$\frac{n+1}{k+1}$$k+1$$n+1$

Volviendo a este problema, un palo en particular está interesado en cuántos palos (incluido él mismo) son tan altos o más altos. Si este número es , entonces la brecha esperada a su izquierda también es n + $k$ .$\frac{n+1}{k+1}$

Entonces, el algoritmo es simplemente encontrar este valor para cada palo y sumar las expectativas. Por ejemplo, comenzando con alturas de , el número de palos con una altura mayor o igual es [ 5 , 7 , 1 , 5 , 5 , 2 , 8 , 7 ] entonces la expectativa es $[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$

Esto es fácil de programar: por ejemplo, una sola línea en R

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

da los valores en la salida de muestra en el problema original

> 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

¡La solución de Henry es más simple y más general que esta!

---

es aproximadamente la mitad del número esperado de comparaciones realizadas por el ordenamiento rápido aleatorio.$E[V]$

Suponiendo que los palos tienen alturas distintas , podemos derivar una solución de forma cerrada para siguiente manera.$E[Y]$

Para cualquier índice , dejar que X i j = 1 si Y j = max { Y i , . . . , Y j } y X i j = 0 de lo contrario. (Si los elementos de Y no son distintos, entonces X i j = 1 significa que Y j es estrictamente mayor que cada elemento de { Y $i\le j$$X_{ij} = 1$$Y_j = \max\{Y_i,...,Y_j\}$$X_{ij}=0$$Y$$X_{ij}=1$$Y_j$ .)$\{Y_i, \dots, Y_{j-1}\}$

Entonces, para cualquier índice , tenemos v j = ∑ j i = 1 X i j (¿Ves por qué?) Y por lo tanto V = n ∑ j = 1 v j = n ∑ j = 1 j ∑ i = 1 X i 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}.$$

La linealidad de la expectativa implica inmediatamente que

$$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}].$$

Como es 0 o 1 , tenemos E [ X i j ] = Pr [ X i j = 1 ] .$X_{ij}$$0$$1$$E[X_{ij}] = \Pr[X_{ij}=1]$

$Y$$\{Y_i,...,Y_j\}$$\Pr[X_{ij}=1] = \frac{1}{j-i+1}$$Y$$\Pr[X_{ij}=1] \le \frac{1}{j-i+1}$.)

And now we just have some math.

$$\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}$$ where $H_n$ denotes the $n$th harmonic number.

Now it should be trivial to compute $E[V]$ (up to floating point precision) in $O(n)$ time.

As mentioned in the comments, you can use Linearity of Expectation.

Sort the $y$: $y_1 \le y_2 \le \dots \le y_n$.

For each $y_i$ consider the expected value of $v_i = E[v_i]$.

Then $E[\sum_{i=1}^{n} v_i] = \sum_{i=1}^{n} E[v_i]$

One straight-forward and naive way to compute $E[v_i]$ would be first fix a position for $y_i$. Say $j$.

Now compute the probability that at position $j-1$ you have a value $\ge y_i$.

Then the probability that at $j-1$ you have a value $\lt y_i$ and at $j-2$ you have a value $\ge y_i$

and so on which will allow you to compute $E[v_i]$.

You can probably make it faster by actually doing the math and getting a formula (I haven't tried it myself, though).

Hope that helps.

Expanding on the answer of @Aryabhata:

Fix an $i$, and assume the item $y_i$ is at position $j$. The exact value of the height is immaterial, what matters is whether the items are greater than or equal to $y_i$ or not. Therefore consider the set of items $Z^{(i)}$, where $z_k^{(i)}$ is 1 if $y_k\geq y_i$, and $z_k^{(i)}$ is 0 otherwise.

A permutation on the set $Z^{(i)}$ induces an corresponding permutation on the set $Y$. Consider for instance the following permuation of the set $Z^{(i)}$: "01000(1)$\dots$". The item $z_i^{(i)}$ is the one is brackets, at position $j$, and the items denoted by "$\dots$" don't matter.

The value of $v_i$ is then 1 plus the length of the run of consective zeros just to the left of $z_i^{(i)}$. It follows that $\mathbb{E}\left(v_i\right)$ is actually 1 plus the expected length of consecutive zeors, until the first "1" is met, if we pick at most $j-1$ bits from the set $Z^{(i)} \setminus \\{z_i^{(i)} \\}$(without replacement). This is reminiscent of the geometric distribution, except that it would be without replacement (and bounded number of draws). The expectation is to be taken on $j$ as well, as a uniform choice on the set of positions $\{1,\dots,n \}$.

Once this is computed (along these lines), we can follow the lines of @Aryabhata's answer.

I dont really understand what do you demend, from tags it seems you are looking for an algorithm.

if so, what is the expected time complexity? by saying: "If we solve this problem using the naive approach it will not be efficient and run practically forever for n=50." it seems to me that your naive approach solves it in exponential time.

i do have a O(n^2) algorithm in mind tho.

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]++;