Dołączam się do podziękowań, dobra robota!

@Hubert: Przykro mi to mówić, ale wątpię aby bitsety Ci tu cokolwiek dały. Brut w n^2 dostawał już 3/10 xd. Może nie zrobiłeś tego możliwie najlepiej, bo rzeczywiście raczej słyszałem o dostawaniu 5pkt za nie

Dla odmiany powiem, że ZAR bardzo mi przypadło do gustu i bawiłem się przy jego wymyślaniu równie dobrze jak przy DCC - jak się rozpisze przykłady i wpadnie na dobry pomysł, to implementacja nie stanowi wyzwania. Choć może faktycznie liczenie odwrotności modulo to trochę za wysoki poziom dla początkujących. Zadania w kategorii C uważam za dużo lepiej dobrane niż rok temu, mimo że BUC ostatecznie nie wymyśliłem i nie jestem typem zawodnika, który dopycha rozwiązania kolanem.

Z kolei zgodzę się, że w drugiej i trzeciej rundzie zadania B były za łatwe (można było co najwyżej głupio stracić pojedyncze punkty na nieuwadze), za to te z dywizji A - za trudne (od czwartej rundy już ich nie czytałem). To trochę komplikuje walkę o koszulki, bo takie zadania B za mało różnicują poziom.

Bajki w treściach jak są, to jest fajnie, bo dobra narracja lepiej oddziałuje na wyobraźnię i łatwiej zapamiętać warunki zadania (przynajmniej ja tak mam). Z drugiej strony - nic na siłę. Ważne natomiast, że w zadaniach typu C historyjka jest obowiązkowa. W tym roku bardzo spodobała mi się treść KRA, ale za to pewien niedosyt odczułem w stosunku do SPL. W tym ostatnim aż prosiło się o jakiś wątek krupiera tasującego karty.

A ja nietypowo - cieszę się, że konkurs odbył się w semestrze letnim, bo w semestrze zimowym nie jestem w stanie do niego podejść. I z mojego egoistycznego punktu widzenia PA mogłyby się na stałe przenieść na marzec ;) A może edycje co pół roku? :)

Czy jest gdzieś miejsce gdzie można dobijać zadania z poprzednich potyczek?

Ja mam tak samo pierwszą część, tylko tych dominatorów Y szukam w czasie liniowym, wykorzystując to, że graf jest planarny.

Identyfikuję ściany grafu z najwyższym wierzchołkiem tej ściany. Dla każdego wierzchołka (zaczynając od góry) liczę, jaką ma ścianę po lewej i jaką po prawej.

Teraz liczę dominatory, zaczynając od dołu. Żeby znaleźć dominatora Y wierzchołka X, muszę zacząć od lewego syna X i iść w prawo, i od prawego syna X i iść w lewo, aż te ścieżki się spotkają.

Więc po prostu idę w pętli, zawsze tym który jest wyżej.

Załóżmy że chcę pójść lewą ścianą w dół i jestem w wierzchołku v. Patrzę na numer ściany po prawej. Jeśli to jest X, to idę w prawo o jeden krok. Jeśli to jest ściana inna niż X, na przykład Z, to skaczę od razu do dominatora wierzchołka Z, który już był policzony wcześniej.

Razem to liczenie dominatorów ma złożoność O(n), bo każdą krawędzią pójdę tylko raz, i przeskok dla każdej ściany Z zrobię tylko raz.

Wprawdzie moje rozwiązanie nie jest krytycznie różne od wzorcowego, ale wydaje mi się, że jest prostsze (używa jump pointerów i niczego więcej, poza wyznaczeniem początkowego grafu).

Jeśli z x woda kapie do y to tworzymy sobie skierowaną krawędź z x do y. Analogicznie jak w rozwiązaniu wzorcowym, mamy lewe i prawe krawędzie. Dodajemy sobie sztuczny odcinek na samym dole, żeby wszystkie ścieżki do niego prowadziły.

Zastanówmy się nad wierzchołkiem X, który ma lewe dziecko L i prawe dziecko R.
Główny pomysł jest taki, że na początku z wierzchołka X wychodzą dwie ścieżki, ale istnieje taki wierzchołek, że zarówno idąc na początku krawędzią w lewo, jak i w prawo, jesteśmy w stanie do niego dojść (takim wierzchołkiem na pewno jest sztuczna podłoga). Takich wierzchołków może być wiele, ale zauważmy, że z najwyższego z nich na pewno prowadzą ścieżki do wszystkich pozostałych. Jeśli znajdziemy ten najwyższy wierzchołek Y i wiemy już, że do naszego wierzchołka X da się dojść z k wierzchołków wyżej, to chcielibyśmy dodać k+1 wszystkim wierzchołkom osiągalnym z X. Dodajmy więc k+1 do L i R oraz odejmijmy k+1 w Y. W ten sposób robimy coś w stylu sum prefiksowych na drzewie.

Problemem pozostaje znalezienie tego wierzchołka Y. Będziemy chcieli użyć do tego jump pointerów. Zauważmy, że Y musi być osiągalny idąc jedynie w prawo z L i jedynie w lewo z R. Podobnie więc jak w jump pointerach będziemy się przemieszczać o potęgi dwójki po lewych i prawych krawędziach odpowiednich wierzchołków. Niech L i R utrzymują oddzielne zmienne (jump_L, jump_R), które mówią, który rozmiar skoku powinien być teraz rozpatrywany (2^jump_L, 2^jump_R). Załóżmy, że aktualne rozmiary skoków są za duże, tj skacząc o te wartości, ominęliśmy Y (łatwo to sprawdzić, dobry skok to taki, że R znajduje się całkowicie na prawo od L po skoku, złe skoki to wszystkie pozostałe). Ale problem jest taki, że nie wiemy, czy tylko jedna wartość jump jest za duża, czy obie. Ale na pewno za duża jest wartość jump tego wierzchołka, który po skoku wylądował niżej(!), możemy ją więc bezpiecznie zmniejszyć i kontynuować. Jest tu jeszcze kilka przypadków, ale znając ten najważniejszy fakt łatwo resztę wymyślić.

Poznałem zastosowania bitsetów w zeszłym roku dzięki Twojemu filmowi na YT. Udało mi się dzięki temu wyrwać 3/10 za Kraniki : ) Po ujawnieniu rozwiązań zajrzę do Twojego kodu by zobaczyć jak wygląda ta znacznie szybsza implementacja

W mojej opinii było ok. Fajnie jest mieć jedno lub dwa trochę trudniejsze zadania, ale z możliwością odsłaniania wyników.

W nawiasie mój czas wymyślenia rozwiązania.

[1C] Kto wygrał?
Świetne zadanie na ten slot. Bardzo lubię, gdy łatwe zadania mają naturalną treść i użycie zasad danego konkursu jest dobrym przykładem. Może warto zawsze w treści 1C dodać zdanie/przypis, że należy odsłonić swój wynik po wysłaniu zgłoszenia? Ja chyba o tym zapomniałem.
[1B] Liderzy
Dobra trudność i zadanie, słaba treść. Jakieś straszne podciągi w tak łatwym zadaniu. Pracujesz w sklepie i masz N cukierków o smakach a[i]. Podziel je na mieszanki, każda musi być określona dominującym smakiem czy coś. Swoją drogą, najpierw źle przeczytałem treść i chciałem dzielić na przedziały, nie umiałem.
[1A] Modernizacja Bajtocji (5-10m z kartką)
Super, bardzo podobało mi się rozwiązanie. Ze smutkiem przyznam, że pewnie 1A powinno być łatwiejsze, by zostawić miejsce na rosnącą trudność w ciągu tygodnia. Trudna decyzja: przystępne zadanie dla większego grona czy od razu jakaś zabawa dla czołówki.

[2C] Znaczki pocztowe
Za trudne, ogromny skok trudności z 1C. I wydaje mi się, że znowu rozdawanie cukierków dałoby lepszą treść, jak w 1B.
[2B] Alchemik Bajtazar (kilka sekund)
Mi nie sprawiło przyjemności, bo natychmiastowo widziałem jak zrobić. Ale zadanie ok, właśnie taka powinna być dywizja B. To zadanie mogłoby też iść jako 5C. Byłoby za trudne na taki slot, ale bardziej robialne niż obecne tam zadania.
[2A] Grupa permutacji (nie umiałem w 1 dzień)
Najtrudniejsze 2A ever. Szybko wymyśliłem O(K*N^2) i próbowałem przyśpieszać. Długo też analizowałem jak cykle się ze sobą łączą, by może je utrzymywać lub liczyć LCM czy GCD. Pokonało mnie to zadanie. Fajne rozwiązanie, zaskakujące. Słabo, że trudno jest zrozumieć poprawność. Dostałem aż 6 punktów za bruta - trochę sporo, ale pewnie tak ma być skoro łatwe zadanie.

[3C] Obrazy (2m z kartką)
Ok, dobre na ten slot.
[3B] Żelki (30s)
Ok. Trudno mi ocenić trudność, bo od razu umiałem przez znajomość podobnych zadań. Bardzo lubię następujące: "Wsiadasz na parterze do windy, która ma trzy przyciski: jedź w górę o +A, +B lub +C pięter. Ile z N pięter budynku jest osiągalnych? A,B,C <= 1e6, N <= 1e18."
[3A] Splatanie ciągów (1 dzień, niedokończone)
Dobre trudne zadanie na eliminacje potyczek. Wydaje się na początku absurdalnie trudne, ale robienie przykładów na kartce szybko sugeruje do policzenia f(A,B) potrzebna jest tylko długość B, który prawdopodobnie jest tym krótszym ciągiem. Napisanie bruta to potwierdziło. Następnie wkopałem się w niepotrzebnie skomplikowane rozwiązanie: K-tą liczbę wyniku liczę w O((N/K)^2) z (jak się potem okazało) niepotrzebnymi funkcjami liniowymi i kwadratowymi, a małe K chciałem robić z FFT, ale zakopałem się tam z odejmowaniem źle policzonych przedziałów wewnątrz jednego monotonicznego kawałka. Celowałem w O(N^1.5 * log(N)), a lepiej było skupić się na jakimś D&C+FFT i mieć pewnie O(N*log^2(N)). Ja unikałem D&C, bo w połączeniu z pierwiastkiem byłby to bardzo wolny rozw. Nie wiem czemu nie połączyłem kropek pomiędzy moimi rozwiązaniami, by robić O(N/K * polylog). Dostałem 6 punktów za moje O(suma po (N/K)^2).

[4C] Łamigłówka 3 (kilka sekund)
Wydaje mi się bardzo standardowe i nie zdziwię się, jeśli gdzieś kiedyś było. To jest taki rodzaj zadania (w kontraście do np. 3C), że jest trywialne dla kogoś doświadczonego i może być trudne dla początkującego. Nie ma w tym nic złego, zadania z dywizji C mają być dopasowane do początkujących.
[4B] Desant 3 (nie umiałem w 1 dzień)
Kolejne zadanie po 2A, które mnie pokonało. Trochę głupio, bo zdarzyło mi się w przeszłości wymaksować rundy 1-4. Bardzo kusiło tutaj robić zadanie od tyłu, iterując najpierw końcowy przedział jedynek. Nic z tego nie wyszło. Symulacja od przodu też mi nie poszła, no cóż. Zadanie pewnie za trudne na swój slot, ale bardziej jednak odczuwam swój skill issue.
[4A] Kolorowy las (skip)
Zadanie nie wygląda na ciekawe. Trzeba pewnie użyć kilku standardowych trudnych rzeczy i jakoś pójdzie. W tym roku nie mogę jechać na finał przez kolizję terminów, więc z zadowoleniem skipnąłem to zadanie.

[5C] Bardzo Ulubiony Ciąg (10-15m w głowie)
Świetne ale zdecydowanie za trudne. Dla koksów byłoby łatwiejsze, gdyby zmniejszyć wartości a[i] do ~100 i pozwolić na dynamika dp[i][suma][stanZaczętychPrzedziałów] w O(N*(N*ai)), ale nie byłoby to dużo gorsze zadanie. Bardzo podoba mi się właściwe rozwiązanie - byłem zadowolony z wpadnięcia na nie i warto było jeszcze kilka minut poświęcić na planowanie implementacji.
[5C] Żarówki (20m na kartce)
Zdecydowanie za trudne. Typowe zadanie ICPC, gdzie można długo nie wpaść na wymagany warunek. Nawet nie próbowałem udowadniać, tylko zaimplementowałem i wysłałem, skoro mamy odsłanianie wyniku. Nie jest tu dużym problemem wymagania znajomości jak policzyć dwumian newtona modulo, bo najpierw trzeba wymyślić rozwiązanie.
[5B] Dzielniki (2h na kartce i bez, potem 2-3h eksperymentowania z kodem)
Fajne, dobrze się bawiłem. Długo myślałem o podzielności przez małe liczby pierwsze i w końcu satysfakcjonujące było wpaść na pomysł badania potęg liczby 4. Super jest, by było z jedno takie zadanie na pracę z kodem, najlepiej właśnie w rundzie weekendowej.
[5B] Kraniki (nie umiałem w 1 dzień)
Długo walczyłem. Myślałem o zamiataniu z góry i z dołu - w obie strony miało to sens i zachowywało się to inaczej. Myślałem o D&C i jump pointerach. Nie wymyśliłem nic lepszego niż log^2 z D&C, więc zamiast tego napisałem pewnie równie szybkie bitsety w O(N^2 / 32). Starczyło na 5/10 punktów, chyba powinno być mniej.
[5A] Monety (1h + niepotrzebne kilka godzin na szukanie szybszego rozwiązania + 2-3h żyłowania)
Najłatwiejsze 5A ever. Już w trakcie konkursu zgadywałem, że organizatorzy nie przewidzieli tak łatwego rozwiązania. Znałem hackenbusha i od razu było dla mnie oczywiste, że możemy robić dynamika po bitach. Dla każdego K niezależnie liczę dp[bit][i][sumaUłamkowa][sumaCałkowita][zaczęteLiczby] w O(M^2 * N^4) czyli razem O(M^2 * N^5) z bardzo małą stałą. Niepotrzebnie myślałem nad lepszą złożonością zamiast od razu zaimplementować. Szkoda, że nie dało się wymusić trudnego rozwiązania z wielomianami, bo użycie ich też przeszło mi przez głowę.
[5A] Autostrada 2 (prawie skip)
Wyglądało absurdalnie trudne. Próbowałem tylko przez chwilę, priorytetyzowałem Kraniki. Super, że było jedno nierobialne zadanie, by nikt przypadkiem nie skończył w sobotę z niedosytem.

Olbrzymie podziękowania dla organizatorów, w szczególności za 50+ stron rozwiązań od razu po konkursie. Najbardziej podobały mi się zadania, których nie udało mi się rozwiązać, bo zazwyczaj miały przecież proste rozwiązanie. Propsy dla autorów, nie propsy dla przypisujących trudności (2A).

Ale pewnie tradycyjnie pojawią się na https://qoj.ac/category/30

Ja mam tak:

Obserwacja: jeżeli x=2^k mod 2^(k+1) to d(x) jest podzielne przez k+1.

Żeby zacząć pytamy sobie o d(x),d(x+1),...,d(x+7) któreś x+i jest 4mod8, więc d(x+i) podzielne przez 3. Ale może być takich i kilka. No to tworze liste kandydatów np niech 3|d(x+3) i 3|d(x+5). To sprawdzamy dalej d(x+3+8) i d(x+5+8). Któraś jest podzielna przez 3. Jak obie to dalej i dalej. Tylko to się szybko wykruszy. I zostanie jeden kandydat. Wtedy znamy x mod 8. I potem analogicznie wyznaczamy kolejne bity. Lepiej to robić po dwa bity naraz bo d(n) rzadko jest podzielne przez małe liczby nieparzyste, przez duże zresztą też.

Zrobiłem to zadanie korzystając jedynie z chińskiego twierdzenia o resztach, rozwiązując układ maksymalnie 13 kongruencji, ale do tego potrzebne mi było trafianie za pomocą x+y w liczby pierwsze, co niestety wymagało około 450-500 zapytań dla x bliskich 10^14. Dużo za dużo. Co i tak nie zmienia faktu, że zabawa z tym była świetna :)
Z opisu przedstawionego w "solutions.pdf" widzę, że właściwym jest odgadywanie bitu po bicie. Jednak nie potrafię zrozumieć tego rozwiązania. Czy ktoś mógłby to prościej wytłumaczyć, a już najlepiej za pomocą przykładu?

Ja się przyłączę do ogólnej uwagi że poziom dywizji C w rundzie 5 był jednak za wysoki, lubię o sobie mysleć że nie jestem już poczatkujący ale BUC mnie pokonało, próbowałem wciskac (a potem żyłować) jakiś przekomplikowany dynamik dodajacy przedziały po wiele na raz dla każdego a[i] ale był za wolny :P ZAR nawet nie próbowałem bo tez przypomniało mi DCC z 2021 a to jest typ zadań który najmniej lubię (czyli łatwiej wymyslić rozwiązanie niż udowodnić że ono w ogóle działa :P)

Za to przez poprzednie 4 rundy bawiłem się bardzo dobrze, zadania ciekawe (chociaż też odniosłem wrażenie że A było trudniejsze niż zwykle podczas B było łatwiejsze niż zwykle :P), ogólnie przyłączam się do gratulacji dla organizatorów.

Jak zwykle super konkurs. Podziękowania dla ogranizatorów.


Zadanka:
- Bardzo fajne zadania (4B) DESant i (5B) DZIelniki. Szczególne ukłony dla autorów tych zadań.

- I bardzo nieulubione zadanie BUC.

A raczej BUCowate limity czasu i pamięci. Bo sama treść i poziom trudności wymyślenia są ok.
Idea +/- rozwiązanie wzorcowe (parowanie trójek prefiksów) napisane z jednym sortem czyli n^3logn dostała 5pkt. Wyrzuciłem log i przeszedłem na 2 pointery, mam n^3 i dostaje 7 pkt, dużo głupawych optymalizacji i wpychania kolanem i dostaje 9pkt (skończyły mi się limit na liczbę zgłoszeń, i nie dopchałem na 10).
Rozumiem, że pewnie dużo skaczę po pamięci i dlatego jest wolno i jakoś trzeba odsiać n^4, ale jak na zadanie z grupy C, to wydaje mi się, że limity były zbyt wyżyłowane. (I czasu i pamięci, bo jak chcesz zapamiętać n^3 par intów to już jesteś na granicy limitu pamięci).


Poziom:

Wydaje mi się, też że 2B,3B były prostsze niż zwykle. Dopiero DES przerzedził ranking B+C. A po trzecim dniu liczba osób z maksem to było chyba grubo ponad 200, (na 128 koszulek).

Poziom dywizji C, też wydaje mi się ok, poza limitami do zadania BUC, które mi zaszły za skórę xD.