Gdyby Potyczki były przez cały rok, to klepałbym zadanka przez cały rok. Zadania są świetne - problemy nie są przekombinowane, są dość elementarnie sformułowane i ich rozwiązania często są bardzo eleganckie i proste, że przyprawia to o szok, jak zobaczy się rozwiązanie, na które się nie wpadło... a jednak tak ciężko na nie wpaść, bo zawsze jest oryginalne.

Formuła Potyczek odpowiada mi idealnie - jest wystarczająco dużo czasu, żeby zastanowić się nad trudnymi problemami i zaimplementować trudne w implementacji zadanka - nie jest to klepanie prostych i powtarzalnych rzeczy na czas.

Zawsze po Potyczkach jestem podjarany i zaczynam robić zadanka na znanych stronkach contestowych i po 2-3 dniach mi się to nudzi - to nie to samo.

Omówienia zadań w PDF - super! Zwięzłe i bardzo przydatne.

W zadanku DES, pomimo dużych danych wejściowych, był problem z rozróżnieniem złożoności rozwiązań za pomocą testów dlatego, że "gorsze" rozwiązania dobrze korzystały z cache. (pomijając, że być może limity były źle dobrane)

Teraz pytanie, czy to oznacza, że dobrze byłoby (jedna z opcji):

(a) Wprowadzić na Potyczkach liczniki instrukcji jak na OI i oceniać rozwiązania z teoretycznym założeniem, że losowy dostęp do pamięci zajmuje O(1)

(b) Wrócić na OI do realnego pomiaru czasu, bo losowy dostęp do pamięci nie jest O(1), tylko bardziej O(sqrt(n)) - Tomek Czajka podlinkował: https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

(c) Zmodyfikować pomiar za pomocą liczników instrukcji, żeby wypluwał "czas" w modelu, gdzie losowy dostęp do pamięci rozmiaru n zajmuje magiczna_stała*sqrt(n) - co może być dość problematyczne

Ja chyba lubię po prostu realny pomiar - lubię implementować algorytmy, żeby je odpalić na realnej maszynie, a nie żeby miały dobry czas w jakimś teoretycznym modelu obliczeń. Ciekawa sprawa, że być może trzeba zrewidować to całe założenie O(1) dostępu do pamięci w algorytmice. A co Wy myślicie?

Mam prostsze rozwiązanie niż w opisie.

Swoją drogą w opisie podejrzanie wiele razy jest powtórzona myśl, że zarażenie całej grupy miast jest korzystne ;)

Otóż dzielimy wszystkie dwustronne grupy miast na pół. Jeśli jest nieparzysta liczba miast to środkowe miasto też dzielimy na pół, więc mamy na przykład grupę składającą się z 3.5 miasta.

I teraz wszystkie grupy miast zarażają się z tą samą prędkością, 1 miasto/dzień. Ratujemy grupy od największej. Ja bym powiedział, że dlatego, że ratowanie dużych grup jest korzystne, a nie dlatego, że zarażanie małych grup jest korzystne, no ale to już zależy od punktu widzenia ;)

Sumujemy rozmiary uratowanych grup. Zaokrąglamy w górę do liczby całkowitej, ze względu na to, że jeśli na samym końcu uratowaliśmy pół miasta, to wtedy drugie pół też się załapie na gapę, ale to jedyny wyjątek.

Fajnie byłoby użyć jakiegoś gotowca do forum, brakuje mi dodawania reakcji do postów, powiadomień o postach, może odpowiadanie na wiadomości jako pod-wątek, itp.

Fajny byłby też oficjalny czat - to zastąpiłoby dział Hydepark z głupotkami.

Albo zamiast forum i czatu coś pomiędzy - może oficjalny discord/slack, tam też mogłyby być ogłoszenia.

Gotowce teraz są naprawdę dobre - pytanie tylko, gdzie jest właściwy kompromis pomiędzy posiadaniem wszystkiego w jednym systemie vs przełączania się pomiędzy kilkoma.

Moje O(nq) przeszło paczki 1,2,3 i 6,7

Dowiedziałem się właśnie że na Szkopule będą po finale.

@Krzysztof Maziarz mam tak samo, tylko nic nie grupowałem, mam O(nq) w naiwnej części. Też mam ac na 1-5.

A jakie mieliście czasy? Mi weszło ledwo O(n log n) na multimapie (najwięcej: 10o OK 2.96s / 3.00s) :)
Po przerobieniu na O(n) (2 tablice z wierzchołkami połączonymi z danym, (jak był wierzchołek stopnia > 2, to krawędzie nie były potrzebne)) czasy dla dużych testów spadły koło siedmiokrotnie.

Ja wysłałem D&C dla k <= 30 (biorąc pod uwagę subtask z treści) + naiwne nieopcone O(n^2) dla k > 30 (grupowanie tylko po lewym końcu), i też dostałem 5/10. U mnie przeszło pierwsze 5 paczek; u was też?

Odpalenie divide n conquer zdaje się być tu kluczowe - ja rownież zachłannie grupuję w obie strony i samo to nie weszło czasowo.

Czy jest możliwość upsolvovania zadań i jeśli tak, to gdzie można je submitować? Na Szkopule jeszcze nie ma, ale to może kwestia czasu?

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

@Marek Dzięki, n^2 k / p < 3e-7 dla p=2^61-1 ma sens! (a w n^2 / p już nie wnikam).

Obaj napisaliście "w praktyce", ja to rozumiem jako "dla słabych testów", więc mam nadzieję, że ktoś takie coś ubije w przyszłości :)

Jeśli p również jest losowe to może być ciężej ubić, chociaż nie jestem pewny.

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

@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?