Jak podejść do wyzwania Vertical Sticks

23

Ten problem pochodzi z wywiadstreet.com

Dane są wartości całkowitych Y={y1,...,yn} który reprezentuje n segmentów linii, tak że punktami końcowymi segmentu ja(ja,0) i (ja,yja) . Wyobraź sobie, że od góry każdego segmentu promień poziomy jest wystrzeliwany w lewo, a promień ten zatrzymuje się, gdy dotyka innego segmentu lub uderza w oś y. Skonstruować tablicę liczb całkowitych n, v1,...,vn , gdzievja jest równe długości promienia wystrzelonego z góry segmentuja . ZdefiniowaćV.(y1,...,yn)=v1+...+vn .

Na przykład, jeśli mamy Y=[3),2),5,3),3),4,1,2)] , a następnie [v1,...,v8]=[1,1,3),1,1,3),1,2)] , jak pokazano na poniższym obrazku:

wprowadź opis zdjęcia tutaj

Dla każdego permutacji o [ 1 , . . . , N ] , można obliczyć V ( y p 1 , . . . , Y p n ) . Jeśli zdecydujemy się równomiernie losowej permutacji p z [ 1 , . . . , N ] , jaka jest oczekiwana wartość V ( y p 1 , . . . , Y sp[1,...,n]V.(yp1,...,ypn)p[1,...,n]?V.(yp1,...,ypn)

Jeśli rozwiążemy ten problem, stosując podejście naiwne, nie będzie ono wydajne i będzie działać praktycznie wiecznie dla . Wierzę, że możemy podejść do tego problemu, obliczając niezależnie wartość oczekiwaną v i dla każdego drążka, ale wciąż muszę wiedzieć, czy istnieje inne skuteczne podejście do tego problemu. Na jakiej podstawie możemy obliczyć oczekiwaną wartość dla każdego drążka niezależnie?n=50vja

Raphael
źródło
Możesz użyć liniowości oczekiwań. To pytanie jest prawdopodobnie bardziej odpowiednie na mat.SE

Odpowiedzi:

23

Wyobraź sobie inny problem: gdybyś musiał umieścić drążków o jednakowej wysokości w n szczelinach, to oczekiwana odległość między drążkami (i oczekiwana odległość między pierwszym drążkiem a hipotetyczną szczeliną 0 oraz oczekiwana odległość między ostatnim drążkiem a hipotetyczną gniazdo n + 1 ) to n + 1kn0n+1 ponieważ istniejek+1szczelin pasujących do długościn+1.n+1k+1k+1n+1

Wracając do tego problemu, konkretny drążek jest zainteresowany liczbą drążków (w tym siebie), które są tak wysokie lub wyższe. Jeśli liczba ta wynosi , to oczekiwana przerwa po jej lewej stronie również wynosi n + 1k .n+1k+1

Algorytm polega więc na znalezieniu tej wartości dla każdego drążka i zsumowaniu oczekiwań. Na przykład, zaczynając od wysokości , liczba drążków o większej lub równej wysokości wynosi [ 5 , 7 , 1 , 5 , 5 , 2 , 8 , 7 ], więc oczekiwane jest 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

Jest to łatwe do zaprogramowania: na przykład pojedyncza linia w R.

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

podaje wartości w danych wyjściowych próbki w pierwotnym problemie

> 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
Henz
źródło
1
Bardzo interesujące. Czy możesz nieco wyjaśnić, dlaczego oczekiwana odległość między drążkami wynosi ; ponieważ nie jest jasne (przynajmniej dla mnie), w jaki sposób zostało obliczone. Dziękuję Ci. (n+1)/(k+1)
M. Alaggan
W moim pierwszym przypadku drążków o jednakowej wysokości istnieje długość n + 1, którą należy wypełnić k + 1 szczelinami, więc średnia przerwa wynika z dzielenia się jedna przez drugą. Jest to oczekiwana przerwa (lub promień poziomy) przed każdym konkretnym drążkiem (i od ostatniego drążka do n + 1 ). Przenosi się do pierwotnego pytania, biorąc pod uwagę drążki, które są tak wysokie lub wyższe niż jakikolwiek konkretny drążek. kn+1k+1n+1
Henry
Bardzo dobrze. To całkowicie podważa moje rozwiązanie; jeżeli wszystkie wysokości są różne, wówczas . mi[V.]=k=1nn+1k+1=(n+1)(H.n+1-1)=(n+1)H.n-n
JeffE
2
@Henry: Dla k-ki o równej wysokości, problem n-slotów, jakie było twoje uzasadnienie dla średniej długości = (n + 1) / (k + 1)? Jeśli mam k-ki i chcę poznać średnią długość promienia jednego z tych kijów w każdej permutacji tych k-ki w n szczelinach, to w rzeczywistości jest równy twojemu wynikowi, ale nie rozumiem dlaczego. Czy jest jakaś logika, czy też wywnioskowałeś ją matematycznie z robienia tego, co opisałem dla 1 kija i n szczelin, a następnie 2 kijów i n, szczelin, ... kijków, n szczelin i zauważenia, że ​​jest on równy (n + 1) / ( k + 1)? Wspominasz o dodaniu gniazda n + 1. To wydaje się bardzo sprzeczne z intuicją.
Alexandre
3
To pytanie, z którym już sobie poradziłem. Zacznij od okrągłego stołu z miejscami, k + 1 osób i posadź ich losowo. Odległości między osobami są oczywiście równe średniej ( n + 1 ) / ( k + 1 ) . Teraz przełamać stolik w n + 1 th osoby, usunąć tę osobę i swoją siedzibę i wyprostuj tabeli. Teraz masz pytanie o n miejsc i k osób, ale tę samą własność iid i ten sam środek. (Znajdź rzadki rym przez miesiąc )n+1k+1(n+1)/(k+1)n+1thnk
Henry
11

Rozwiązanie Henry'ego jest zarówno prostsze, jak i bardziej ogólne niż to!


to w przybliżeniu połowa oczekiwanej liczby porównań przeprowadzonych przez losowy Quicksort.mi[V.]

Zakładając, że drążki mają różne wysokości , możemy uzyskać rozwiązanie dla w formie zamkniętej w następujący sposób.mi[Y]

Do ewentualnych wskaźników , niech x i j = 1 jeśli Y J = max { T i , . . . , Y j } i X i j = 0 w przeciwnym razie. (Jeśli elementy Y nie są różne, to X i j = 1 oznacza, że Y j jest ściśle większy niż każdy element { Y ijajotXjajot=1Yjot=max{Yja,...,Yjot}Xjajot=0YXjajot=1Yjot .){Yja,,Yjot-1}

Następnie dla dowolnego indeksu mamy v j = j i = 1 X i j (Czy widzisz dlaczego?), A zatem V = n j = 1 v j = n j = 1 j i = 1 X i j .jotvjot=ja=1jotXjajot

V.=jot=1nvjot=jot=1nja=1jotXjajot.

Liniowość oczekiwań natychmiast implikuje, że

mi[V.]=mi[1jajotnXjajot]=1jajotnmi[Xjajot].

Ponieważ wynosi 0 lub 1 , mamy E [ X i j ] = Pr [ X i j = 1 ] .Xjajot01mi[Xjajot]=Par[Xjajot=1]

W końcu, i to jest ważne, ponieważ bit wartości w różne i permutowane równomiernie każdy element podzbioru { Y i , . . . , Y j } jest również może być największy element tego podzespołu. Zatem Pr [ X i j = 1 ] = 1Y{Yja,...,Yjot} . (Jeśli elementyYnie są odrębne, nadal mamyPr[Xij=1]1Par[Xjajot=1]=1jot-ja+1Y ).Par[Xjajot=1]1jot-ja+1

A teraz mamy trochę matematyki. gdzieHnoznaczan-liczbę harmonicznych.

mi[V.]=jot=1nja=1jotmi[Xjajot][liniowość]=jot=1nja=1jot1jot-ja+1[jednolitość]=jot=1nh=1jot1h[h=jot-ja+1]=h=1njot=hn1h[1hjotn]=h=1nn-h+1h=((n+1)h=1n1h)-(h=1n1)=(n+1)H.n-n
H.nn

Teraz obliczenie (do precyzji zmiennoprzecinkowej) w czasie O ( n ) powinno być banalne .mi[V.]O(n)

JeffE
źródło
Czy to zakłada, że ​​patyki mają różną wysokość?
Aryabhata
Tak, przyjmuje wyraźne wysokości. (Najwyraźniej źle odczytałem pytanie). Równoważność z randomizowanym szybkim sortowaniem nadal obowiązuje, gdy istnieją powiązania, ale nie rozwiązanie w formie zamkniętej.
JeffE
4

Jak wspomniano w komentarzach, możesz użyć liniowości oczekiwania.

yy1y2)yn

yjavja=mi[vja]

mi[ja=1nvja]=ja=1nmi[vja]

mi[vja]yjajot

jot-1yja

jot-1<yjajot-2)yja

mi[vja]

Prawdopodobnie możesz to przyspieszyć, wykonując matematykę i zdobywając formułę (chociaż sam tego nie próbowałem).

Mam nadzieję, że to pomaga.

Aryabhata
źródło
3

Rozwijając odpowiedź @Aryabhata:

jayjajotyjaZ(ja)zk(ja)ykyjazk(ja)

Z(ja)YZ(ja)zja(ja)jot

vjazja(ja)mi(vja)jot-1Z(ja)zja(ja)jot {1,,n}

Po obliczeniu (zgodnie z tymi liniami ) możemy postępować zgodnie z odpowiedzią @ Aryabhata.

M. Alaggan
źródło
-2

Naprawdę nie rozumiem, czego żądasz, na podstawie tagów wydaje się, że szukasz algorytmu.

jeśli tak, jaka jest przewidywana złożoność czasu? mówiąc: „Jeśli rozwiążemy ten problem, stosując podejście naiwne, nie będzie ono wydajne i będzie działać praktycznie wiecznie dla n = 50”. wydaje mi się, że twoje naiwne podejście rozwiązuje je w wykładniczym czasie.

Mam na myśli algorytm 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]++;

źródło