Ja mam brute-force O(n^2). Liczę na to, że wejdzie, bo działało w 39.5 sekundy.

Nie no... to ja mam O(q n)... zupełnie inny algorytm.

Też mam O(qn), tylko grupuję zapytania tak, żeby unikać liczenia dwa razy zapytań o tym samym końcu (którymkolwiek).

Ja mam n^3/2.
Kluczowy pomysł zadania jest taki, aby z zadania jednowymiarowego zrobić dwuwymiarowe... Tzn. jak mamy nasz graf przejść skaczący co 1 i co k, to on tak naprawdę topologicznie jest takim jakby ... spiralnym walcem. Tzn zmapujmy barierę pomiędzy (i-1)-szą i i-tą liczbą na pole o współrzędnych (i%k,i/k) (dzielenie całkowite oczywiście). Wtedy mamy strzałki z pola (a, b) do (a+1, b) o zysku 0 i do pola (a, b+1) o zysku "suma na którymśtam przedziale o długości k". Przy czym są jeszcze strzałki (k-1, i) do (0, i+1) (skąd to jakby walcowate sklejenie z przesunięciem). I nasze zadanie zamienia się w pewnym sensie dwuwymiarowego dynamika na planszy o wymiarach k x (n/k), tzn. każde zapytanie to pytanie o najdroższą ścieżkę pomiędzy jakimiś dwoma wierzchołkami na tej planszy. Jego można już rozwiązać przez dziel i rządź.
W prostszej wersji, gdy wybieramy sobie krótszy bok (co jest zależne od tego czy k jest mniejsze czy większe niż sqrt(n)) i tniemy w połowie po odpowiednim zawsze tym samym wymiarze. To da O(n^3/2 log n). W trudniejszej wersji możemy w każdym kroku patrzeć, który bok jest aktualnie krótszy (tzn raz tak raz siak), co daje n^3/2. Aczkolwiek te krawędzie (k-1, i)->(0, i+1) dodają sporo syfu i w szczególności deduplikacja kodu jest niezbyt możliwa, bo przynajmniej u mnie cięcia pionowe i poziome się sporo różniły.

Ja mam O(n*k*log n) za pomocą dziel i zwyciężaj.

Ja mam O(n^(5/3 + eps)) zakładając n ~ q.
Dla "małych k" można proste divide and conquer w nk log n.

Dla większych k taka obserwacja:
- Załóżmy że mamy wyniki dla wszystkich przedziałów [x, y], gdzie y % k == 0
- wtedy w O(nr / k) możemy policzyć wynik na przedziale [x, y], gdzie y % k == r, bo rekurencja nam zmniejsza resztę o max 1, czyli musimy przeliczyć r - 1 reszt * n/k kroków, które wykonujemy cofając się o k do tyłu.

Z reszt 0..k-1 wybieram k/l reszt w odległościach ~l i dla każdej z nich liczę dynamikiem odpowiedzi dla wszystkich początków. To robimy w czasie O(n * n/k * k/l) = O(n^2 / l). Zapytania realizujemy w O(nl / k) per zapytanie.
Biorąc l = k^(1/2) daje nam to alg działający w O(n^2 / k^(1/2)).

Optymalne k do wyboru między d&c, a tym drugim dziwactwem to k=n^(2/3 - eps), ale w praktyce d&c było trochę szybsze, więc ja przyjąłem k=1500.

Ja miałem dość proste O((n+q)n^(2/3)).
Brutalny dynamik idze tak: dp[i][j]=max(dp[i+1][j],dp[i+k][j]+A[i]+...+A[i+k-1]).

Niech S=n^{1/3}
Licze tego dynamika tylko dla i takich że
1. (i mod k) mod S = S-1
lub
2. i/k mod S= S-1

Jeżeli mam zapytanie (i,j) i chce dostać dp[i][j] dla niepolicznego i puszczam takiego jakby bfs-a, ze chce znac odpowiedz dp[i+1][j] i dp[i+k][j].
Widac, że bfs-em odwiedze co najwyzej S^2 stanów zanim dojdę do już policzonych, a dynamika musze policzyć dla co S-tego i. Sumarycznie mam O(n^(5/3)+qn^(2/3)).

@Tomek Czajka niestety raczej nie wejdzie, mam identycznie (też grupuję) i pomimo że maxtesty na zwykłym /usr/bin/time wychodziły blisko limitu, to na sio (sprawdzane skryptem oiejq ze strony OIa) już przy n=q=100k wychodziło powyżej 100 sekund. Niewykluczone że gdzieś zepsułem grupowanie, bo przy dużych losowych testach odrzucało mi tylko około połowy zapytań.

Ja mam bruta z kilkoma optymalizacjami pętli wewnętrznej, co liczył big testy z forum w 10-20sekund (przed optymalizacjami nawet >55sekund). Optymalizacje zrobilem tylko dla k>=5... Ciekawi mnie jakie było to oczekiwane przez autorów zadania rozwiązanie :)

Moje rozwiązanie jest zrandomizowane, ale nie zdążyłem do końca policzyć jaka tak naprawdę jest jego złożoność.

Rozwiązanie opiera się o obserwację, że możemy wylosować pozycję jakiegoś piwota wewnątrz tablicy i dla niego
policzyć wszystkie stany DP na lewo i na prawo. Teraz jeżeli ten piwot jest pomiędzy dwoma blokami z optymalnego
rozwiązania w jakimś zapytaniu, to wtedy znajdziemy za jego pomocą odpowiedź dla tego zapytania. Po każdym
pivocie możemy więc przeiterować się po zapytaniach i zmaksować ich odpowiedzi.

Dopóki mamy czas, będziemy więc losowali piwoty i dla nich maxowali wyniki. Okazuje się, że uda sie nam w ten sposób
wylosować jakieś N/30 pivotów. Jeżeli teraz zauważymy, że każdy koniec bloku z optymalnego rozwiązania dla jakiegoś
zapytania ma 1/20 szans na bycie wylosowanym, to szansza porażki przy kilkuset blokach w rozwiązaniu jest już znikoma.

Są dwa problemy:
1) Krótkie przedziały - wtedy po prostu wykonujemy dla nich naiwne obliczenia

2) Długie zapytania, których rozwiazania są prawie całkowite wypełnione blokami - Tu jest nieco ciężej, ale oobersujemy
że jeżeli dla takiego zapytania wiemy, że jest mało komórek, których nie uwzglądnia w rozwiązaniu (niech tych komórek będzie x),
to możemy policzyć dla niego wynik za pomocą nieco zmodyfikowanego DP w czasie (Nx / k). Wydaje mi się, że to wystarcza
do osiągnięcia maksymalnej liczby punktów.

Warto zauważyć, że to rozwiązanie potrzebuje jedynie pamięci O(N)

Ja mam to, co Tomek Czajka, tylko jak zapytanie nie było wliczone w jakiś dłuższy przedział niż o dlugosci 2k, to odpowiadam drzewkiem przedziałowym. Maxtesty z forum chodziły < 30s, ale test n = 3e5, q = n/2, każde zapytanie jest o 2 krótsze jakieś 55s lokalnie. @Igor Hańczaruk myślę, że coś zepsułeś z grupowaniem. Ewentualnie, masz mało wydajne pętle w części z brutem

IMO jeśli O(n^2) z jakimiś drobnymi optymalizacjami stałej wchodzi, to myślę że trochę porażka dawać takie zadanie. Limity sugerują że brut nie może zajmować jakoś dużo ponad TL, ale zakładałem że autorzy zadania opcili bruta low-level trickami przez tydzień, i nie zbili czasu dostatecznie, więc zdecydowali się zadanie dać, ale może nie jest to prawda.

W obronie bruta:

Jeśli dobrze policzyć złożoność obliczeniową, biorąc pod uwagę, że losowy dostęp do pamięci wielkości M na dwuwymiarowym układzie scalonym zajmuje czas O(M^0.5) [*], to rozwiązanie dziel i rządź również zajmuje O(nk log n + qk n^0.5) = O(n^2) dla q = n, k = n^0.5.

Natomiast rozwiązanie Jacka jest lepsze, nadal wychodzi O(n^(5/3)).

[*] https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

Ja mam wielką nadzieję że wyoptowane O(nq) nie dostanie więcej niż 2-3 punkty ale coś czuje że się zdziwię

W zadaniu 4b za trochę większą stałą traciło się 2-4 punkty. Równie dobrze wyoptowanie w tym zadaniu n^2 powinno dostawać jakieś 6+ imo.

Potyczki Cacheowe to mój ulubiony konkurs

Da się poprawić algorytm dziel i rządź żeby działał szybko z pamięcią (cache-oblivious), w czasie O(n^1.5 log n):

Sortujemy zapytania przechodzące przez linię podziału po początkach i po końcach. Nie łączymy wyników lewych i prawych od razu dla każdego zapytania (bo to wymaga losowego skakania po pamięci), tylko zbieramy połówkowe wyniki w tablicy o wielkości 2q, ułożone według początków/końców zapytań. Na koniec sortujemy tą tablicę po numerze zapytania, i dopiero wtedy łączymy dwa wyniki dla każdego zapytania.

| "Ja mam O(n*k*log n) za pomocą dziel i zwyciężaj."

| "Dla "małych k" można proste divide and conquer w nk log n."

First things first... jak w ogóle to proste d&c zrobić?? :/

@Adam

jak robisz jakieś przecięcie w połowie i wyliczasz zapytania przechodzące przez nie to dla każdego z nich masz dwa przypadki:

1. w optymalnym wyniku nie znajduje się żaden przedział długości k przechodzący przez nasze przecięcie:
ten przypadek ogarniamy licząc sobie optymalne wyniki na każdym prefiksie od przecięcia w lewo i prawo i dodając odpowiednie dwa wyniki

2. w optymalnym wyniku znajduje się przedział długości k przechodzący przez nasze przecięcie
takich potencjalnych przedziałów jest tylko k, więc sprawdzimy każdy, w tym celu policzymy sobie dpka na każdym prefiksie w prawo od punktu przecięcia zaczynając od 1 elementu, zaczynając od 2 elementu ... zaczynając od kgo elementu i analogicznie w lewo (w sumie 2k dpków) i teraz jak zakładamy że ten przedział długości k zawierający się w optymalnym wyniku wystaje na lewo o x (dla x=1,2...k) to wynik maxujemy z sumą z tego przedziału + wartość z dpka w lewo startującego od x+1szego elementu + wartośc dpka w prawo startującego od k-x+1go elementu

A nie jest tak że cache i czas dostępu do pamięci na SIO nie ma znaczenia, bo liczony jest zwirtualizowany czas działania, gdzie każda instrukcja działa w czasie 1 cyklu procesora jak na OI? https://oi.edu.pl/l/srodowisko/

"W zadaniu 4b za trochę większą stałą traciło się 2-4 punkty." - well, jak się miało złą złożoność i jakieś jumppointery, jak chyba praktycznie wszyscy co na forum opisywali, to nie takie dziwne, że można było stracić punkty xd No i też nie zapominajmy, że nazywanie zależności od ósemki stałą nie jest do końca w porządku. Aczkolwiek nie wiem co dokładnie miałeś na myśli.

Moim zdaniem w hipotetycznie dobrze przygotowanym opracowaniu tego zadania na hipotetycznej sensownej sprawdzarce bruty do niego nie powinny wchodzić na więcej niż jakieś 2 punkty. Ale jest spora gama rozwiązań pośrednich (jakieś n^5/3, n^3/2 log n), więc rozumiem, że można chcieć jednak trochę stopniować stopień skomplikowania testów i nie mieć maxtestów już od trzeciej paczki. Ale przy istnieniu rozwiązania n^3/2 moim zdaniem TL powinny być bardziej brutalne, 42s to za duży zapas. Niestety wierzę Tomkowi i spodziewam się, że jednak było to możliwe wcisnąć bruta na 10/10. Na Codeforces nawet cyrkuluje znane meme ze mną w roli głównej, gdzie wyśmiewam autorów zadań, których wzo to n^3/2 log n, a potem się dziwią, że 100% wbitych rozwiązań to bruty n^2, a orgowie raczej chyba myślą podobnie jak ja w tej kwestii, więc się spodziewałem, że wzo powinna być co najwyżej n * sqrt(n log n). Ale te 42 sekundy zastanawiały...

@Franciszek dzięki wielkie, faktycznie... a ja mergowałem przedziały jak w drzewku przedziałowym w O((n+q)*k^2 * log(n))...

Ile pkt macie za O(qn)? Ja mam 5pkt za wersje bez żadnych optymalizacji, jedynie z grupowaniem po początku.

10/10 za O(qn)

Ja jednak tylko 5.

Trochę nie rozumiem w takim razie, czemu limit czasu nie był rzędu 15-20 sekund. Z tego co się orientuję, to rozwiązania pierwiastkowe działały rzędu ~8-12 sekund, więc to by dobrze odcięło bruty od wzorcówek.

5/10 za qn z grupowaniem. +1 do tego, co mówi Anadi - po co tak duże limity czasu? (osobiście nie narzekam, no ale wciąż...)

@Krzysztof Potępa

Zgaduję, ze włozyłeś wysiłek w optymalizowanie jakimś prefetchingiem/unrollingiem/pragmami? Próbowałem trochę pomyśleć jak tu dobrze skorzystać z pragm wektoryzacji, ale SIO jest stare i w sumie nie wiedziałem z jakich instrukcji mogę skorzystać (nawet jeśli, to packowanie LL nie powinno przynosić speedupu >2, a potrzebowałbym x10), dodatkowo liczenie sumy prefiksowej nie jest zbytnio przyjemne dla jakiejkolwiek wektoryzacji.. Unrolling także sprawdziłem z różnymi unroll factors ale żadnego zysku z tego nie było. Poddałem się i wysłałem zwykłego bruta. Chciałbyś się może podzielić tajnikami czarnej magii?

@Kacper Walentynowicz z popularnych na CFach pragm, działają afaik tylko ("sse,sse2,sse3,popcnt,abm,mmx,tune=native")
Pozostałe mają sporą szansę dać exitcode 4.

@Kacper Walentynowicz

To Cię zdziwie - obyło się bez low-level tricków (no poza pragmami, w tym unroll-loops). Moja krytyczna pętla liczy dp w tablicy rozmiaru k i robi dosłownie dp[i] = max(dp[i-1], dp[i] + elems[pos+i]). Takiego czegoś kompilator sam nie umie zwektoryzować, zapewne przez zależność dp[i] od dp[i-1] (polecam flagę kompilacji -fopt-info-all). To co próbowałem i pomogło na moim procesorze to ręczny unroll 4 iteracji i liczenie dla nich maxa prefiksowego w formie „drzewka”, by zmniejszyc sekwencyjne zależności. Jednak taki opt tylko spowalniał na sio2…

To co zrobiłem by wepchnąć to pod limit czasowy to specjalne grupowanie zapytań. Wybieram sobie miejsce w tablicy, w którym się zaczyna lub kończy jak najwięcej przedziałów i liczę dla takiej paczki razem wynik (w przód lub w tył). I potem zachłannie wybieram tak kolejne paczki zapytań do przetworzenia.

Jeszcze dodatkowo dla k <= 512 odpalam wersję dziel i zwyciężaj O(nk log n), bo dla małych k mój brut był wolny.