English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Ależ Wy tu kombinujecie. A nie da się tego zadania zrobić jednym przejściem po całym ciągu bawiąc się jakimś stosem? :-)
Tak, ja zrobilem, mialem 1800 linii :D
Łukasz Wołoszyn, mam to rozwiązanie, które Cię ciekawi i wg moich wyliczeń opartych na obserwacjach, najgorszym możliwym przypadkiem może być nlog(n/2), ale nie potrafiłem takiego przykładu stworzyć i mój program podobnie jak Twój miał najgorszą złożoność na wszystkich testach z forum 6n.
Jeżeli tyle osób, ma to rozwiązanie, to może ktoś oszacował lepiej niż ja, ile trzeba razy przejechać po tej tablicy od prawa i od lewa,żeby wyznaczyć wszystkie granice? Albo inaczej, czy istnieje przykład dla którego nie wystarczy przejść 5 razy?
Moje również, chociaż dodatkowo dodałem optymalizację polegającą na aktualizowaniu jedynie małych fragmentów, które faktycznie tego potrzebują, a nie całej tablicy. Takie rozwiązanie na maxtestach z forum dawało mi czasy poniżej 0.1s (OITIMETOOL) :).
Moje rozwiązanie jest podobne do opisanego powyżej - wyznacza granice dopóki się da. Cóż - czas pokaże czy jest to optymalne rozwiązanie :)
Algorytmy, które działały na zasadzie wyznaczania granic pomiędzy "prawidłowymi" przedziałami,a "nieprawidłowymi" wywalały przedziały nieprawidłowe, jednakże w przedziałach nieprawidłowych mogły mieścić się przedziały prawidłowe jak w tym powyżej, przez co pokazywały zły wynik. Ciekawe jest jeszcze inne pytanie, jaką złożoność miałby zmieniony powyższy algorytm, który by wyznaczał granice dopóki można to robić? Z moich obserwacji(ale być może istnieją gorsze przypadki) wystarczało 5 razy od prawa i od lewa to zrobić, co oznaczałoby to, że jest to liniówka, ale jakoś w to nie wierzę. No cóż, zobaczymy czy testy ubiją moje algo na maxtestach
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 ;)
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 ;)
#include <vector>
#include <stack>
#include <queue>
#include <stack>
#include <queue>
yyy... tablicę? No i jakiś wektor do trzymania grafu, ale to jest oczywiste.
Może mi ktoś powiedzieć (w sensie napisać), co jest w tym teście takiego specyficznego?
Jakie struktury danych wykorzystywaliscie jezeli chodzi o jezyk programowania?
ufff, przez ostatnie 15 minut byłem przekonany, że wysłałem błędne rozwiązanie (wychodził mi wynik 1), ale na szczęście po prostu kopiowałem bez "15" na początku ;)
Również wydaję mi się, że było kilka testów tego typu na forum :P
Również wydaję mi się, że było kilka testów tego typu na forum :P
Ja miałem 360 loc, dla całkiem dużych testów działało.