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

na końcu jest opisywane

Ja mam algorytm online. Złożoność pamięciowa O(n log n), czasowa O((n + m) log n).
Każdą liczbę z ciągu na wejściu rozkładam binarnie i dla każdej pozycji bitu zapisuję sumę prefiksową ciągu na tym bicie.
Jak dostaję zapytanie o przedział, to dla każdej pozycji bitu wiem ile na tym przedziale było 0, a ile 1. Zatem biorę to, czego było więcej (jak gdzieś była dokładnie połowa, to zwracam 0). Dzięki temu w czasie O(log n) dostaję jedynego kandydata na lidera. Sprawdzenie czy ten kandydat jest liderem robiłem wyszukiwaniem binarnym, również w czasie O(log n).

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

Jak w temacie.
Ja przewiduję, że dostanę co najwyżej 15pkt za to zadanie.

Otóż bynajmniej nie Ty jeden wpadłeś na tego typu test. Nie jest to jakaś wielka niespodzianka czy mądrość. Mało, bo mało, ale kilka testów z paczek dostępnych na forum już wcześniej również rozkładało te same liniówki co i Twój test.
Przyznaję tego typu test położył moje pierwsze rozwiązanie do tego zadania

Ciekawe czy złożoność czasowa O((n+m)log n) starczy na 100 :D?

Ponieważ I etap się już skończył, więc myślę, że mogę to udostępnić:

15
pppjjpjpjpjjppj

(by Adrian Siwiec)

powinno wyjść 5

Podobno wywalało to większość liniówek

Ja nie miałem pomysłu, więc zrobiłem cache dla przedziałów co 100, 1000, 10000 i 100000. Generalnie czas wygenerowania ich wynosił dla skrajnych wartości kilkaset ms (~0.6s), ale potem algorytm rozwiązywał program w maksymalnym czasie ~0.5s korzystając z wcześniej wyznaczonych przedziałów.

Macie jakieś rozwiązania inne od omawianych?
Ja, w skrócie, sprawdzałem (dla wszystkich przedziałów jednocześnie, analogicznie do omówienia) czy dominują liczby z przedziału [1;n/2] czy (n/2;n]. Później sprawdzałem która połowa dominującego przedziału jest dominująca i tak aż do znalezienia konkretnych liczb. Złożoność czasowa O((n+m)logn).

jest liniowe, ale z dużą stałą

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

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

Myślę że 95% osób które rozwiązało to zadanie ma tak jak na omówieniu, tylko mogą mieć ewentualnie inny wzorek :)

Jak powyżej, jak zrobiliście to zadanie? Wzorcówka to jedno, ale wiadomo praktyka to drugie. Moje O(n^2) działa podobnie jak to rozwiązanie z omówienia. Jednak ja wierzchołek w którym ukorzeniam drzewo traktuje nie jako wierzchołek x(ten z omówienia, część wspólna ścieżek pomiędzy trójką wierzchołków), tylko jako wierzchołek z trójek postaci{a,b,c}(tutaj a to wierzchołek w którym ukorzeniłem drzewo, wtedy też znajduje wszystkie pary, które zawierają a i zaznaczam a jako wierzchołek przetworzony). Warto dodać, że wszystkich trójek {a,b,c} jest rzędu O(n^3), dlatego nie wyznaczam wprost wszystkich tych trójek, tylko je sprytnie zliczam w czasie O(n)(dla każdego drzewa).

Działa