Czy tylko mi się wydaje, że autorzy zadań trochę przegięli z trudnością w C? Z założenia jest to grupa dla początkujących w konkursach, zadania 1-3 były fajne i w miarę łatwe, natomiast od rundy czwartej to jakaś strasznie ostra jazda... Dla kontekstu, opiszę skrótowo swoje rozwiązania

4C - zbijamy ciągi operacji tak żeby był cykl (dół, prawo, góra, lewo), okazuje się że jak zaaplikujemy coś takiego to "kształt" figury się nie zmieni, tylko pola się przepermutują jakoś, no to znajdujemy tę permutację i podnosimy do K-tej potęgi, na końcu dopychając pozostałe brutem.. Łącznie ~300 linii kodu, ogólnie bardzo fajne zadanko tylko trochę.. trudne no.

5C [walizki] - niby rozwiązanie jest proste, ale i tak na codeforces to zadanko by miało jakieś 2600..

5C [gierka] - tutaj to już w ogóle brzmi jak ostra jazda z łańcuchami Markowa żeby to zrozumieć... nie za bardzo rozumiem czemu moje rozwiązanie działa ale chyba to nie jest wymagane żeby mieć punkty.. Od razu widać że parzystość jest wymagana, a wynik okazuje się być liczbą możliwych do wykonania ruchów z tego stanu (proste do policzenia), podzieloną przez sumę liczb ruchów możliwych do wykonania we wszystkich stanach osiągalnych (tzn o tej samej parzystości) (solidnie trudne do policzenia dla początkującego, ja mam dwa czterowymiarowe dynamiki po bitmaskach). Znowu fajne zadanie, ale jakbym miał tym zachęcić osobę początkującą w konkursach algorytmicznych to by mi się chyba nie udało :P

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.

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

@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 ;)

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

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.

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)

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

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

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.

55s na wszystko (jednowątkowo na laptopowym Ryzen 5 4600h). Brut, tylko z drobnymi optymalizacjami:
Zamiast stawiać 8 pionków i liczyć liczbę ruchów, stawiam jednego pionka (odpalajac funkcje dla wszystkich pozycji), wyliczam mu liczbę możliwych ruchów, stawiam drugiego (rekurencyjnie, na kazdym innym miejscu**)), doliczam do przekazanej z gory zmiennej liczbę ruchów wynikła z istnienia nowego pionka*) i idę piętro nizej, postawić 3 pionke... jak postawiełem ich k, zwracam skumulowaną z całej scieżki liczbę ruchów policzoną po drodzę (a funkcje sobie same to sumują zwijając się).

*) ta liczba ruchow moze byc ujemna. Dostawiając pionek pomiedzy 4 inne nie tylko nie ma on zadnego ruchu, ale zlikwidowałem po jednym ruchu czterem innym pionkom!
**)zeby nie bylo powtorzeń typu .1..2. i .2..1., stawiam nowy pionek tylko "za" poprzednio postawionymi, jeśli popatrzeć na "spłaszczoną" tablicę
Jako bonus, tablicę z poprzednio postawionymi pionkami trzymam jako uint64_t (nie bez powodu ma rozmiar 8x8:)) i dozwolonośc ruchu sprawdzam patrac na bit.
https://pastebin.com/Hfkgujfb //mięsko w funkcji dozwolonych_ruchow(..)

Zrobienie tego na małej dwuwymiarowej tablicy zamiast na jednym incie nie powinno dać być gorsze niż *10 (tablica 8x8 8 bitowych intow to tylko 8 razy wiecej niż uint64_t).
Liczenie ruchow pionków zamiast po drodze, to dopiero na koncu, oznaczałoby 8 razy wiecej operacji na najnizszym poziomie rekurencji/pętli.

Hmm, pozbywając sie obu opytmalizacji nagle może bo być i godzina liczenia.

Nadal znośnie. Najważniejsze, by robic odpowiednik
for (int p1=0; p1<pmax;p1++)
for (int p2=p1+1; p2<pmax;p2++)
for (int p3=p2+1; p3<pmax;p3++)
....
zamiast każdy pionek na każde miejsce (i potem redukować powtorzenia), bo to 8! =~= 40k razy więcej roboty.


Edit: a co do ogolu, zgadzam się, tak jak przez lata była inflacja trudności zadań B, tak teraz to samo dotyczy C.

W tym roku zaprosiłem kilka osób, które uczę algorytmiki do udziału w Potyczkach algorytmicznych. Osoby te sensownie radzą sobie z olimpiadą informatyczną, ale od zadań z grupy C odbiły się jak od ściany. Aż później zacząłem żałować, że powiedziałem im, że powinny sobie poradzić z zadaniami B i C. Ja rozumiem, że poziom informatyki w Polsce jest wysoki i na Potyczkach trzeba dawać trudne zadania, aby w rankingu różne osoby miały różną ilość punktów :D Ale wydaje mi się, że organizatorzy są już na takim pułapie programowania konkursowego, że nie pamiętają z jakimi zadaniami mają szansę zmierzyć się początkujący. Wierzę, że wezmą nasze uwagi do serca i następne potyczki będą jeszcze lepsze :)

Tak samo jak pisze Krzysztof Piecuch - zachęciłem kilku uczniów do startowania w dywizji C i to był błąd. Dużo za trudne zadania i niestety zniechęcą mnóstwo początkujących.

Fakt, zadania "C" były trudne. Ależ się namęczyłem z "Walizkami"... Spodziewałem się miłych zadanek "na rozgrzewkę", a lekko nie było i nie starczyło mi czasu na zadania "B" i "A".
Ale w sumie dobrze, że piszecie o tym, bo już myślałem, że to coś ze mną jest nie tak - starość, a może skutki covid - różne myśli mi chodziły po głowie :)

@Bartłomiej Szczygieł Pewnie już sprawdziłeś to w editorialu, ale co do [WIE], trzeba było zliczać wszystkie krawędzie w grafie w inny sposób. Zamiast liczyć (możliwe ruchy) dla każdego (ułożenia), trzeba było liczyć (liczbę ułożeń) dla których jest możliwy każdy z (ruchów). Zmiana kolejności sumowania trywializuje rozwiązanie

Jak uświadomiłem sobie rozwiązanie zadania 4C, to już się zacząłem zastanawiać co organizatorzy szykują na weekend w dywizji C... U mnie wyszło nawet blisko 400 linii. Na weekend takie obszerne w implementacji zadanie byłoby jednak całkiem w porządku, razem z WAL.

Zadanie WIE było po prostu trudne do wymyślenia - przynajmniej dla mnie, prawdopodobnie już zresztą zmęczonego wcześniejszym wysiłkiem umysłowym w trakcie wcześniejszych rund. A co dopiero dla początkujących - w 2020 i 2021 były w dywizji C zadania weekendowe "na pomysł", ale zdecydowanie bardziej przystępne.

Jak dla mnie to 4C może i było implementacyjne, ale mój kod ma 130 niezbyt skompresowanych linii (w tym jakieś 25 templatek, obsługi testcasow itd.), więc wydaje mi się, że warto było pomyśleć jak to napisać.


Edit: Może są trochę skompresowane :)

@Hubert Banaszewski tak. Wczoraj, jak Wojtek podeł wzór, nadal myślałem, że mimo jego prostoty to było coś bardziej skomplikowanego. A dziś przeglądając pdfa i widząc tak oczywisty sposob liczenia, uznałem, że mi łeb wapnieje;-)

Zgadzam się, że zadania w C były dość trudne tylko ja uważam to za duży plus. Zadania na przeczytaj, naklep, zapomnij są stratą czasu gdyż niczego nowego nie nauczą. Najfajniejsze są zadania które albo zostaną rozwiązane dużym nakładem sił albo nie zostaną rozwiązane, lecz po zakończeniu poznanie rozwiązania wnosi coś ciekawego na "przyszłość".

Może rozwiązaniem dla początkujących jest osobny ranking dla początkujących?

Np. Przy rejestracji dodajemy osobny select box z pytaniem jak obiektywnie oceniasz swój skillset? Np. "aktywny wyjadacz", "wyjadacz na emeryturze", "aktywny zawodnik średniego szczebla", "emerytowany zawodnik średniego szczebla", "początkujący z mniej niż 50 zadaniami w życiu". Następnie dodajemy filtr na rankingu po kategoriach i każdy może się porównać do ludzi o podobnym skillu. Pewnie będzie mniej boleć, że się nie rozwiązało jakiś zadań. A wręcz może motywować do ciułania punktów brutami. Sam się łapie często na tym, że jeśli nie jestem wstanie napisać poprawnego rozwiązania to nawet bruta nie piszę za 1-3 punkty.

@Wladyslaw: nie zgodzę się z pierwszą częścią, wszystkie koncepcje do zadań C (poza WIE) widziałem już wcześniej w jakichś zadaniach, a i tak musiałem spędzić dłuższą chwilę na odkryciu i zaimplementowaniu ich rozwiązań na nowo. Ja to bym chciał zobaczyć w dywizji C więcej zadań opartych na wykombinowaniu jakiegoś dowodu, tak jak w 1A - konkretny dowód pewnej własności jakiegoś obiektu nie jest często spotykany, natomiast idea która za nim stoi może się generalizować na inne zadania i przydać się w przyszłości. Inną sprawą jest możliwość konstrukcji takich zadań.

@Sebastian: Jak się jest w kategorii "wyjadacza" z setkami zadań rozwiązanych to trudno naprawdę coś zupełnie nowego znaleźć. Nie twierdzę też, że jakoś zadania C wzniosły moją wiedzę na nie wiadomo jaki nowy level - wszystkie koniec końców rozwiązałem. Jednak nawet dla mnie widzę rzeczy z wartością edukacyjną które przeoczyłem.

WIE -> trochę kminy o błądzeniu losowym i wyostrzeniu sobie intuicji co się dzieje w nieskończoności. Fajne było też to, że można było zliczać liczbę krawędzi łopatologicznie lub pomyśleć dwa razy i wyprowadzić prosty wzorek -- poraz kolejny wpadłem w tą pułapkę, że zamiast pomyśleć zacząłem klepać coś oczywistego.

WAL -> bardzo ciekawe zadanie symulacyjno-optymalizacyjne typu: spróbuj czegoś, stwierdz czemu nie działa, popraw dane wejściowe i spróbuj ponownie. Trochę mi zajeło się przekonanie, żeby skierować moje myśli w tym kierunku. Na początku na siłę szukałem jakiegoś układu równań modulo.

LAM -> Kilka fajnych obserwacji prowadzących do standardowego rozwiązania. Pierwsza to, że kształty w rogach zawsze będą takie same. Druga, że klocek z tego samego pola zawsze trafi na to samo pole, czyli tworzymy sobie graf gdzie wierzchołkami są pojedyńcze pola na planszy. Trzecia obserwacja, że każdy wierzchołek w tym grafie ma stopień dwa to znaczy że mamy zbiór rozłącznych cykli, inaczej graf permutacji. Skąd dochodzimy do standardowego problemu potęgowania permutacji.

Fajne było też to, że jeśli nawet nie znało się tych trików z rozbiciem cyklowym i permutacjami to odrabiając zadanie domowe z FOT można było zrobić LAM, nie robiąc FOT.

FOT -> wariacja standardowego problemu sortowania z niestandardową operacją dokonywania swap'ów. Jak ktoś nie zna można dodać do portfolio bardzo przydatny trick, że dowolne przesunięcie cykliczne da się uzyskać za pomocą operacji "inverse" ciągu (dość często wykorzystywany trik przy takich zadniach)

MUZ- > niby zachłanny algorytm bez historii. Ale sam przegapiłem ten ciekawy fakt ze szkicu rozwiązań:

"...Dla ciekawskich pozostawiamy również udowodnienie następującej własności: każde optymalne rozwiązanie zawiera prefiks dodatnich liczb całkowitych poza jedną..."

PUN -> bez historii.

PAL -> niby próbne, ale trochę czasu mi zeszło by to zrobić. Równie dobrze mogło by być pewnie na równi z 3B.