Jak już zaznaczyłem, nie jestem tego testu autorem, również mojego programu (n log n) on nie rozwalił.

Wzorcówka podobno miała ponad dwa tysiące linii kodu.
Cóż.. czekam na omówienie na kanale olimpiady ;-)
ps. Ja liczę na około 15 pkt, niby mam jakieś optymalizacje w swoim "algorytmie", ale zapewne na niewiele się zdadzą.

Tak, ktoś to zrobił.

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...