Como abordar o desafio Vertical Sticks

23

Esse problema foi retirado de Interviewstreet.com

É-nos dada uma matriz de números inteiros que representa segmentos de linha, de modo que os pontos finais do segmento sejam e . Imagine que, do topo de cada segmento, um raio horizontal é disparado para a esquerda, e esse raio para quando toca outro segmento ou atinge o eixo y. Construímos uma matriz de n números inteiros, , em que é igual ao comprimento do raio disparado da parte superior do segmento . Definimos .Y={y1,...,yn}ni(i,0)(i,yi)v1,...,vnviiV(y1,...,yn)=v1+...+vn

Por exemplo, se tivermos , então , como mostra a figura abaixo:Y=[3,2,5,3,3,4,1,2][v1,...,v8]=[1,1,3,1,1,3,1,2]

insira a descrição da imagem aqui

Para cada permutação de , podemos calcular . Se escolhermos uma permutação aleatória uniformemente de , qual é o valor esperado de ?p[1,...,n]V(yp1,...,ypn)p[1,...,n]V(yp1,...,ypn)

Se resolvermos esse problema usando a abordagem ingênua, ele não será eficiente e será executado praticamente para sempre por . Acredito que podemos abordar esse problema calculando de forma independente o valor esperado de para cada stick, mas ainda preciso saber se existe outra abordagem eficiente para esse problema. Em que base podemos calcular o valor esperado para cada stick independentemente?n=50vi

Rafael
fonte
Você pode usar a linearidade da expectativa. Esta questão é provavelmente mais apropriado em math.SE

Respostas:

23

Imagine um problema diferente: se você tivesse que colocar sticks de alturas iguais em slots, a distância esperada entre os sticks (e a distância esperada entre o primeiro stick e um slot nocional e a distância esperada entre o último stick e um nocional o slot ) é pois existem intervalos para caber no comprimento .kn0n+1n+1k+1k+1n+1

Voltando a esse problema, um determinado stick está interessado em quantos (inclusive ele) são tão altos ou mais altos. Se esse número for , o intervalo esperado à esquerda também será n + 1k .n+1k+1

Portanto, o algoritmo é simplesmente encontrar esse valor para cada stick e adicionar a expectativa. Por exemplo, começando com alturas de , o número de paus com altura maior ou igual a é [ 5 , 7 , 1 , 5 , 5 , 2 , 8 , 7 ] então a expectativa é 9[3,2,5,3,3,4,1,2][5,7,1,5,5,2,8,7].96+98+92+96+96+93+99+98=15.25

É fácil de programar: por exemplo, uma única linha em R

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

fornece os valores na saída de amostra no 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
Henry
fonte
1
(n+1)/(k+1)
kn+1k+1n+1
Muito agradável. Isso substitui completamente minha solução; se todas as alturas forem distintas, então . E[V]=k=1nn+1k+1=(n+1)(Hn+11)=(n+1)Hnn
Jeffe
2
@ Henry: Para os k sticks de altura igual, problema de n slots, qual foi o seu raciocínio para o comprimento médio = (n + 1) / (k + 1)? Se eu tenho k sticks e quero saber o comprimento médio dos raios de um desses sticks em cada permutação desses k sticks em n slots, na verdade é igual ao seu resultado, mas não entendo o porquê. Existe lógica ou você deduziu matematicamente de fazer o que eu descrevi para 1 stick e n slots, depois 2 sticks en, slots, ... k sticks, n slots, e percebendo que era igual a (n + 1) / ( k + 1)? Você mencionou a adição de um slot n + 1. Isso parece muito contra-intuitivo.
286 Alexandre Alexandre
3
n+1k+1(n+1)/(k+1)n+1thnk
Henry
11

A solução de Henry é mais simples e mais geral que esta!


E[V]

E[Y]

ijXij=1Yj=max{Yi,...,Yj}Xij=0YXij=1Yj{Yi,,Yj1}

Então, para qualquer índice , temos (Você vê por quê?) E, portanto, jvj=i=1jXij

V=j=1nvj=j=1ni=1jXij.

A linearidade da expectativa implica imediatamente que

E[V]=E[1ijnXij]=1ijnE[Xij].

Como é ou , temos .Xij01E[Xij]=Pr[Xij=1]

Finalmente - e este é o bit importante - porque os valores em são distintos e permutados de maneira uniforme, cada elemento do subconjunto é igualmente provável que seja o maior elemento desse subconjunto. Assim, . (Se os elementos de não forem distintos, ainda temos .)Y{Yi,...,Yj}Pr[Xij=1]=1ji+1YPr[Xij=1]1ji+1

E agora só temos um pouco de matemática. onde indica o th número harmónico .

E[V]=j=1ni=1jE[Xij][linearity]=j=1ni=1j1ji+1[uniformity]=j=1nh=1j1h[h=ji+1]=h=1nj=hn1h[1hjn]=h=1nnh+1h=((n+1)h=1n1h)(h=1n1)=(n+1)Hnn
Hnn

Agora deve ser trivial calcular (até precisão de ponto flutuante) em tempo.E[V]O(n)

JeffE
fonte
Isso pressupõe que os gravetos tenham altura distinta?
Aryabhata
Sim, assume alturas distintas. (Aparentemente, eu interpretei mal a pergunta.) A equivalência com o quicksort aleatório ainda permanece quando há empates, mas não a solução de forma fechada.
jeffe
4

Conforme mencionado nos comentários, você pode usar a Linearidade da Expectativa.

Classifique : .yy1y2yn

Para cada considere o valor esperado de .yivi=E[vi]

EntãoE[i=1nvi]=i=1nE[vi]

Uma maneira direta e ingênua de calcular seria primeiro fixar uma posição para . Diga .E[vi]yij

Agora calcule a probabilidade de que na posição você tenha um valor .j1yi

Então a probabilidade de que em você tenha um valor e em você tenha um valorj1<yij2yi

e assim por diante, o que permitirá calcular .E[vi]

Você provavelmente pode torná-lo mais rápido, efetivamente, fazendo as contas e obtendo uma fórmula (embora eu ainda não tenha tentado).

Espero que ajude.

Aryabhata
fonte
3

Expandindo a resposta de @Aryabhata:

Corrija um e assuma que o item está na posição . O valor exato da altura é imaterial, o que importa é se os itens são maiores ou iguais a ou não. Portanto, considere o conjunto de itens , onde é 1 se e é 0 caso contrário.iyijyiZ(i)zk(i)ykyizk(i)

Uma permutao no conjunto induz uma permutação correspondente sobre o conjunto de . Considere, por exemplo, a seguinte permeação do conjunto : "01000 (1) ". O item é aquele que está entre colchetes, na posição , e os itens indicados por " " não importam.Z(i)YZ(i)zi(i)j

O valor de é então 1 mais o comprimento da execução dos zeros consectivos à esquerda de . Segue-se que é na verdade 1 mais o comprimento esperado de zeores consecutivos, até que o primeiro "1" seja atingido, se escolhermos no máximo bits do conjunto (sem substituição). Isso é remanescente da distribuição geométrica, exceto que ela seria sem substituição (e número limitado de empates). A expectativa é para ser tomada em assim , como uma escolha uniforme sobre o conjunto de posições .vizi(i)E(vi)j1Z(i)zi(i)j {1,,n}

Uma vez calculado (nesse sentido ), podemos seguir as linhas da resposta de @ Aryabhata.

M. Alaggan
fonte
-2

Eu realmente não entendo o que você ignora, a partir de tags, parece que você está procurando um algoritmo.

Nesse caso, qual é a complexidade de tempo esperada? dizendo: "Se resolvermos esse problema usando a abordagem ingênua, ele não será eficiente e será executado praticamente para sempre por n = 50". parece-me que sua abordagem ingênua a resolve em tempo exponencial.

Eu tenho um algoritmo O (n ^ 2) em mente 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]++;

fonte