Temat: liniowe rozwiązanie do kurierów

Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.

Temat: liniowe rozwiązanie do kurierów

Nie wiem, jak miałoby działać, ale słyszałem plotki że takie istnieje. Ktokolwiek widział, ktokolwiek wie...

#721 | Wojciech Jabłoński | Dodany: 2013-11-07 14:38:32

jest liniowe, ale z dużą stałą

https://www.youtube.com/watch?v=OoRh1R7_lWo

#722 | Krzysztof Krawczyk | Dodany: 2013-11-07 16:03:23

Chyba dałeś złego linka, bo psorek pytał o liniowe rozwiązanie.

#729 | Karol Kaszuba | Dodany: 2013-11-08 19:53:03

na końcu jest opisywane

#731 | Krzysztof Krawczyk | Dodany: 2013-11-08 20:33:11

Polecam wtyczkę TeX The World for Chromium lub jakiś ekwiwalent pod inne przeglądarki.

Niestety, ale jakby na to nie patrzeć, to to rozwiązanie nie jest liniowe. Jeżeli chcemy uzyskać na [; m ;] zapytaniach prawdopodobieństwo równe [; a ;] to musimy na każdym zapytaniu wykonać [; \log_2 \left( \frac{1}{1 - a^{\frac{1}{m}}} \right) ;] sprawdzeń. Jest to [; O(log(m)) ;], gdyż [; \lim_{m \to \infty} \frac{\frac{1}{1 - a^{\frac{1}{m}}}}{m} = -\frac{1}{ln(a)} ;]

Zatem złożoność podanego rozwiązania to [; O(n + m \log m) ;]

#732 | Karol Kaszuba | Dodany: 2013-11-08 20:58:42 | Ostatnia modyfikacja: 2013-11-09 11:50:40

Czy to, co teraz wymyśliłem, jest na pewno dobre (i liniowe)? Aż sam się nieco zdziwiłem...

Niech dla dowolnego skończonego zbioru X zbiór [; L_d(X) ;] oznacza zbiór tych elementów, które występują w X co najmniej [; d|X| ;] razy - przy czym d jest pewną stałą. Powiedzmy też sobie, że ktoś miły wyznaczył nam [; L_d ;] dla każdego przedziału bazowego (przedziałów tych jest mniej niż [; 2n ;], więc suma rozmiarów wszystkich zbiorów nie przekroczy [; \inline \frac{2n}{d} = O(n) ;]).

Spróbujemy dla pewnego przedziału o szerokości [; l ;] wyznaczyć nie więcej niż C potencjalnych liderów - gdzie C jest pewną stałą. Ustalmy [; 2^k ;] jako rozmiar wykorzystywanego przez nas przedziału bazowego. Weźmy więc te przedziały bazowe, które mieszczą się w zadanym przedziale. Zauważmy, że zarówno od lewej, jak i prawej strony zostają niepokryte podciągi liczb o długości mniejszej niż [; 2^k ;]. Pokrywamy więc więcej niż [; l-2^{k+1} ;] liczb. Oczywiście te operacje można wykonać w czasie [; \inline O(\frac{l}{2^k}) ;] - czyli stałym przy odpowiednio dużym k.

Powiedzmy teraz, że dowolny wybrany przez nas element x należący do całego ciągu nie należy do żadnego zbioru [; L_d ;] dla żadnego z naszych przedziałów bazowych. Wtedy x nie może wystąpić w więcej niż [; dl ;] elementach należących do pokrytych liczb oraz [; 2^{k+1} ;] elementach należących do niepokrytych liczb (bo takich liczb jest nie więcej niż tyle). Tak więc x występuje w badanym przedziale w nie więcej niż [; dl+2^{k+1} ;] miejscach. Ta wartość ma być nie większa niż [; l/2 ;], czyli równoważnie [; \inline 2^{k+1} \leq l(\frac12-d). ;] Biorąc [; \inline d=\frac13 ;] oraz upraszczając, otrzymujemy [; \inline 2^k \leq \frac1{12}l. ;] Bierzemy więc długość przedziałów bazowych [; \inline 2^k \in \left(\frac1{24}l, \frac1{12}l\right> ;] (jeśli [; l < 12 ;], to po prostu bierzemy wszystkie liczby należące do przedziału jako kandydatów). Wtedy oczywiście jedynymi możliwymi wyborami na kandydata są elementy należące do [; L_d. ;] Nietrudno więc zauważyć, że skoro [; \inline \frac{l}{2^k} < 24, ;] to pokryjemy przedział mniej niż 24 przedziałami bazowymi, a przy naszym wyborze d oznacza to, że możliwych kandydatów jest mniej niż [; 24 \cdot 2=48 ;] (bo żaden przedział nie może mieć więcej niż dwóch 1/3-liderów).

Pozostał jedynie problem wyznaczania [; L_{1/3}(X) ;] dla X - wszystkich przedziałów bazowych ;). Tutaj jednak obserwacja jest podobna do tej, jak we wzorcówce - gdy weźmiemy trzy różne elementy należące do X i je wywalimy, to każdy element, który dotychczas występował w co najmniej 1/3 elementów, wciąż będzie spełniał ten warunek. Dlatego też liczenie tych zbiorów jest bardzo podobne do firmówki. Inicjujemy przedziały o szerokości 1, a następnie idziemy w górę drzewa przedziałowego zbudowanego na przedziałach bazowych. W każdym węźle ostatecznie trzymać będziemy kandydatów na 1/3-liderów i policzoną liczbę wystąpień "ponad" 1/3. Jeśli w trakcie tworzenia przedziału bazowego o szerokości [; 2^k ;] w dwóch łączonych przedziałach o szerokości [; 2^{k-1} ;] pojawia się co najmniej 3 kandydatów na 1/3-lidera, to "redukujemy" ich dokładnie tak, jak we wzorcówce. Nietrudno zauważyć, że ten preprocessing zajmuje czas [; O(n) ;]. Każdy z badanych przedziałów początkowo przetwarzamy w czasie [; O(1) ;]. Wytwarzamy łącznie [; O(m) ;] kandydatów na liderów, a ich przetworzenie algorytmem ze wzorcówki zajmie czas równy [; O(n+m) ;] (sortowanie zdarzeń wykonujemy poprzez sortowanie przez zliczanie). Tak więc wygląda na to, że algorytm jest liniowy - z duuużą stałą, ale jednak liniowy ;)

#743 | Marek Sokołowski | Dodany: 2013-11-11 21:33:59

#29672 | charles hensen | Dodany: 2022-03-06 16:52:57

#29673 | charles hensen | Dodany: 2022-03-06 16:53:56