Nie ma to jak zbugować kod po wygenerowaniu poprawnych outów na forum xddd. Nawet nie wiem co mogłem zrobić aby tak zwalić, ale RIP 2 punkty

I ja się zgodzę z przedmówcami. Zadania z dywizji C bardzo mi się podobały, myślenie nad nimi było dla mnie przyjemnością i świetną zabawą. Problem w tym, że od czwartej rundy zajęły mi one praktycznie cały czas jakim dysponowałam i na pomyślenie o zadaniach z grupy B (a tym bardziej A) już nie starczyło czasu. Trochę szkoda. Zadania 4C i 5C spokojnie mogłyby znaleźć miejsce w dywizji B z początku/środka tygodnia.

Ja w WAL policzyłem iloczyn stopni wychodzących i wynik to jest dzielnik tej liczby. Puszczam właśnie tyle walizek i patrzę jakie jest gcd liczby walizek które poszły każdym pasem i przez to dzielę. Nawet nie wiem jak tu można ułamki wcisnąć xd

Bartek: Stwierdzenie, że C zajęły Ci więcej niż B jest dla mnie mega zaskakujące. Wymyślenie żadnego z C nie zajęło mi więcej niż parę minut (aczkolwiek 4C kodziłem 2h xd...), za to ostatnie zadania z B były baardzo trudne, wielogodzinne boje, a i 3B i 4B też uważam za bardzo trikowe.
Aczkolwiek zgadzam się z tym, że przy publikacji każdej kolejnej rundy byłem zaskoczony wyższą trudnością C niż się spodziewałem, tzn. nawet jeśli wymyślałem je szybko to wiedziałem, że dla początkujących mogą być zaporowe

To ja też się przyłączę do rantu (?), zawsze dodatkowa wymówka na słaby wynik :P W tym roku miałem mniej czasu, więc to może przez to, ale też uważam, że zadania C w porównaniu z takim 2020 były sporo trudniejsze i w połowie zawodów poziom już był jak z ostatniej rundy 2 lata temu.

Btw - w WIE jaki był szybki brute na stablicowanie tych 256 wartości? Krzysztof mówi, że miał taki co policzył w 10 min, ale mój mielił dużo dłużej i kilka ostatnich wartości musiałem wyliczyć "ręcznie" patrząc na zależności między S[n][m][k] -> S[n][m][k+1] dla mniejszych wartości (wychodziło mnożenie przez ułamki typu 56/7).

Również uważam że zadania C były zbyt trudne.
Dodam, że dywizja B również trzymała bardzo wysoki poziom.
Kiedyś do samego końca walczyłem o 100% w dywizji B. Tym razem z trudem udało mi się to w dywizji C. W dywizji B od 3 rundy lecę na brute'ach - fakt, że poniekąd ze względu na brak czasu, ale również z braku pomysłów na coś lepszego niż brute.
Kiedyś próbowałem zabierać się za dywizje A. Tym razem kompletnie ją odpuściłem (poza 2A, bo zadanie wyjątkowo mi się spodobało i po 2 minutach miałem pomysł na rozwiązanie, które okazało się dobre)

Do skracania ułamków najwygodniej jest policzyć GCD licznika i mianownika.
Jakkolwiek, w zadaniu z walizkami w ogóle nie trzeba było dodawać ułamków, można było zrobić je w całości na liczbach całkowitych.
W pierwszym ruchu można założyć, że długość cyklu (czyli liczby walizek po których system się zresetuje) jest równa liczbie wyjść z pierwszej platformy. Następnie dla każdej kolejnej platformy policzyć liczbę walizek przychodzących na tę platformę w ciągu cyklu. Jeśli ta liczba jest niepodzielna przez liczbę pasów wychodzących z platformy, to obliczam NWW liczby walizek przychodzących i liczby wyjść i aktualizuję wartość cyklu i wszystkich policzonych dotąd wejść przez otrzymany mnożnik. Rozwiązanie co prawda kwadratowe, ale dla 100 platform wystarczająco szybkie, na żadnym teście nie przekroczyło 0.01s.

Może to jest skill issue, ale mi sumarycznie wszystkie C zajęły więcej czasu niż wszystkie B... Pamiętam, że początkowo dywizja C miała być z założenia małym dodatkiem, aby zwiększyć zasięgi, ale w miarę szybkim do zrobienia, żeby się dało dalej zająć A i B. Niestety z roku na rok założenie o dywizji C się zmieniło z proste do ad-hoc, ale już nie takie proste.

@Wojtek: No, to mam tak samo, tylko koszt na przedziale liczę w O(log n).

Btw, ten trick z kolejką kandydatów i binsearchowaniem momentu gdy jeden stanie się lepszy od drugiego w bólach wyparsowałem z https://codeforces.com/blog/entry/8219?#comment-139241

To ja jeszcze chętnie usłyszę jakieś ładne rozwiązanie do chodzenia po linie.
To co mi się udało wymyśleć to najpierw przyłożyć tym paperem - https://www.sciencedirect.com/science/article/pii/S0166218X06003040 - a potem jeszcze mocniej się produkować (da się poprzekształcać te wzorki i sprowadzić do jakiś pytań o punkty w prostokątach lub coś w tym stylu), ale brzmi to trochę jak overkill.

Też nieszczególnie podobało mi się WIE jako 5C. Niby kod i wzorki bardzo proste, ale bardziej to zadanie z RP niż z algo. 4C jako 5C by było moim zdaniem idealne trudnością.

W jaki sposób implementacja dodawania ułamków w pythonie skraca wynikowy licznik i mianownik? Robiłem w c++ i tu poległem.

@gierka upraszcza to się znacznie, jeśli zauwazysz, ze suma liczby ruchów ze stanu parzystego = suma liczby ruchów ze stanu nieparzystego (bo kazdu ruch parzysty prowadzi do nieparzystego, a ruchy sa odwracalne). Liczysz wiec sumę wszystkich mozliwych ruchów.
A co najważniejsza, takich liczb jest 512 (1-8, pionków, szerokosci i wysokosci planszy) więc nawet naiwnie generując każdy mozliwy stan i ręcznie liczac liczbę ruchów (oczywiscie, jakaś prosta rekurencja znacznie przyszpiesza:)), dosć szybko wygenerujesz tablicę, ktorą ładuje sie do właściwego programu. Podejrzewam, że nawet jeśli daje się te kombinacje liczyć szybciej, taka była intencja tworcow zadania.

A dlaczego to działa? Jeśli macierz połączań jest symetryczna, a właściwa macierz przejścia ma identyczne wartośći w danej kolumnie, to na palcach można policzyć, że wektor v, gdzie v(i) = iloćś polaczeń do wierzchołka, jest stacjonarny.
Zauważyć, że tak jest daje się na małych przykładach (ja tego nie wiedziałem/nie pamietałem przed).
Jak ten wektor unormujemy do suma=1, będziemy mieli prawdopodobieństwa.


z 4C miałem ten sam problem, niby wszystko proste, a implementacja 300+ linii. Ale też podejrzewam, że dałoby się skrócić, jakbym lepiej przemyślał, co z tym ciągiem poczatkowo robię.

Za rok-dwa będzie kategoria D ;)

Rozwiązanie WIE jest duzo prostsze niż to co opisujesz. Suma ruchów do wykonania ze wszystkich stanów to:
2 * (n * (m - 1) + m * (n - 1)) * newt[n * m - 2][k - 1]
Aczkolwiek to czemu trzeba policzyć w tym zadaniu co trzeba to rzeczywiście nie jest oczywiste i imho za trudne na dywizję C

Faktycznie, trudność zadań w dywizji C dają wiele do życzenia, aczkolwiek np. 5C [gierka] można było prościej zrobić. Można było ztablicować sumę liczb ruchów możliwych do wykonania we wszystkich stanach osiągalnych, bo sytuacji, które nas interesują jest 8 * 8 * 8, a trywialny brut policzył mi to ~10 minut.