Nie wiem, czy ktoś jeszcze zwrócił na to uwagę, ale w treści zadania "Wielki Zderzacz Termionów" w wyjaśnieniu przykładu jest mowa o "Wielkim Zderzaczu Hadronów". Czyli chyba jednak te termiony to jest jakaś odmiana hadronów :)

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

Mój proces rozwiązywania zadania:

Po dobrym zrozumieniu procesu narysowałem sobie na kartce 14 drzew, które rozróżniały sąsiadów pola, któremu liczę wynik. Każde drzewo jest postaci np. T(2, {T(3, {T(4), T(3, {...})})}) czyli "wierzchołek stopnia 2 z nieśmiertelnym ojcem oraz dzieckiem stopnia 3, które ma jedno dziecko stopnia 4 i jedno dziecko stopnia 3, które ...". Kod to łączył w około 60 możliwych drzew z dodatnim wynikiem dla korzenia - gdzie już korzeniem jest pole, którego wynik dodam do globalnego wyniku. Po żmudnej implementacji miałem około 180k bitowych patternów pustych i zakazanych pól, co dawało złożoność O(N*M*180'000) i wystarczało tylko dla N, M <= 25. Szybko poprawiłem do 60k patternów i utknąłem na wiele godzin. Po zrobieniu kilku innych zadań wróciłem w niedzielę wieczorem do BAK i udało mi się zmergować podobne patterny, by mieć niecałe 7k przez Wiele godzin nie umiałem poprawić, ale w końcu pomergowałem jakieś podobne patterny i mam niecałe 7k, śmiga (na SIO 1.5s preprocessing i drugie tyle na przejście grida 200x200). Okropne zadanie, bardzo fajnie mi się nad nim pracowało.

Ta praktyka ulega zaniechaniu na krótkich konkursach, gdzie jest średnio pół godziny na zadanie. Jeśli testowanie jest przydatne w pracy, to zdecydowanie jest to argument za ćwiczeniem tego. Ale zgadzam się, że czasochłonność w późniejszych rundach ma znaczenie i może odstraszać.

Wgl to jesteś czerwony na Codeforces. Nie wierzę, że napisanie checkerki do 2B zajęłoby Ci dłużej niż 20-30 minut. To samo się tyczy każdego, kto walczy o wejście do finału.

Wiadomo. Mateusz Radecki koks, że takie zadanka wymyśla i przygotowuje.

Dziękuję wszystkim organizatorom!

Eliminacje bardzo mi się podobały. Czekałem na nie od kilku tygodni i się nie zawiodłem. Szło mi to powoli, ale świetnie się bawiłem przy 2A, 3A, 4A i jednym 5A (BAK) czyli przy większości zadań z dywizji A. Poniżej ogólny feedback i potem szczegółowy do zadań.

Trzy najważniejsze i łatwe do naprawy problemy:
1. Mocno za trudna dywizja C. Poleciłem startowanie kilku uczniom i żałuję. Wszystkie zadania poza 1C było mocno łamigłówkowe, a też przecież można wymagać więcej implementacji i typowych algorytmów.
2. Mała gradacja rozmiaru testów. Duży przeskok w Minach [3A] oraz w Linach [5B], gdzie było N=3000 w grupie 4 i aż N=120'000 w grupie 5.
3. Za dużo punktów za niektóre bruty do trudnych zadań, np. aż 3p za Gaussa O(N^3) to zadania Drzewa [5A]. Byłoby to ok w łatwiejszym zadaniu.

i mniej ważne:
4. Dobra trudność dywizji A, poza weekendem dosyć prosta dywizja B.
5. Czasochłonna runda 5. Coś z 5B fajnie by było zastąpić zadaniem z prostym kodem. Można było zamienić któreś 5B z Mędrcami [3A].

===

[1A] Wielki Zderzacz Termionów - Napisałem bruta, by znaleźć pattern. Nie jestem fanem takich zadań, ale jest dobre na pierwszą rundę. Potem jeszcze trochę implementacji. Spodziewałem się łatwiejszego zadania, ale jest ok.
1B, 1C - ok
[2A] Wersja dla profesjonalistów - Przyjemnie było robić rysuneczki.
[2C] Muzyka pop 2 - Odstraszające zadanie dla typowego programisty czy dla ucznia w szkole, który umie pętle i tablice. Bity są ok, ale leksykograficzne porównywanie ciągów? Dla nas oznacza to oczywiście minimalizowanie każdej kolejnej liczby i tyle, ale to nie jest naturalne. Trudność rozwiązania jest ok.
[2B] Podwyżki - Ok, o ile zawodnik wie, że takie programy trzeba porządnie testować. Być może bym to zamienił z którymś 5C, by był feedback. Natomiast nie uważam za problem, że oba zadania 2A i 2B wymagały checkerki i trudnego testowania, bo dywizja A nie jest dla począktujących.
[3A] Mędrcy - Super zadanie, bo długo mi zajęło zrozumienie że chodzi o kliki i vertex covera. Potem się męczyłem z wymyśleniem dobrej złożoności, ale to już problem ze mną.
3B, 4B - Bardzo fajne ale trochę za łatwe.
3C, 4C - Zrozumiała treść, ale trudne rozwiązanie jak na ten slot.
[4A] Miny - Super zadanie i podziwiam wzorcówkę. Miałem jeszcze bardziej skomplikowane rozkminy na centroidach i się zakopałem po 350 liniach. Szkoda, że bitsety wchodziły i to na maksa - rozważyłem je po drodze i niestety odrzuciłem.
[5C] Walizki - Ok. Miło że był Python.
[5C] Wieczór gier - Bardzo trudne.
5B, 5B - Szybko wpadłem na pierwszy pomysł i potem długo jeszcze myślałem nad całym rozwiązaniem, zanim zacząłem klepać. Oba zadania ok, ale może nie koło siebie. Nawiasowe podziały przekomplikowałem i miałem z 10 różnych prostych struktur (stosy, mapy, drzewo przedziałowe), a Liny miałem trochę za wolno.
[5A] Drzewa rozpinające - Nie wiem, mało próbowałem. Napisałem tylko Gaussa i szkoda że dostaje aż 3 punkty.
[5A] Bakterie - Dla mnie super i najlepsze zadanie tych eliminacji, ale obiektywnie to pewnie jest takie sobie. Spędziłem nad nim pół weekendu czyli kilkanaście godzin. Było za dużo łatwych punktów z podzadań, przez co większość pracy jest raptem za 5 punktów. To zadanie ponoć miało początkowo być użyte jako 5B, co byłoby straszne.

Ja również dziękuję organizatorom za przygotowanie świetnego konkursu. Była to rozrywka intelektualna na najwyższym poziomie. Podziwiam umiejętność wymyślenia tak trudnych, ale i wdzięcznych zadań.

Kamilu, rozumiem argument o unikalności Potyczek (chociaż OI też testuje testowanie na drugim etapie), natomiast nie sądzę, żeby to była dobra praktyka. Ba, uważam że to zła praktyka, która z dobrych powodów ulega zaniechaniu. Testujmy sobie kod w pracy, a na konkursach rozwiązujmy zadania.

Testowanie wymaga przede wszystkim czasu, zmniejszenie tego wymogu pozwoliłoby zwiększyć inkluzywność Potyczek dla osób, które nie dysponują tak bogatym budżetem czasowym

Może bardzo pojedyncze zadania powinny być oznaczone jako odsłanialne. Byleby nie dało się tego nadużywać. Przykładami dobrych na to zadań są Mędrcy (3A), Drybling Baj (3B) oraz Chodzenie po linie (5B). Byleby nie dało się tego oszukańczo wykorzystać.

Wciąż normą w dywizjach A i B powinna być brak możliwości odsłonięcia. Potyczki są unikalnym konkursem, gdzie testowana jest nasza umiejętność testowania.

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.

Czas na doroczne włożenie kija w mrowisko - a może by tak zrobić więcej odsłonięć w przyszłym roku? Ja rozumiem, że Potyczki lubią swój specyficzny format, ale nie da się ukryć ze jest on strasznie wymagający. Przede wszystkim czasowo bo liczba godzin jaką trzeba włożyć w wymyślenie i przetestowanie rozwiązań z A/B jest bardzo duża, i z tym chyba wszyscy się zgodzą. Podejrzewam, że wiele osób odpada już na starcie, rezygnując z udziału wiedząc że po prostu nie są w stanie sobie pozwolić na spędzenie tyle czasu nad konkursem. Fakt, że dodatkowo trzeba jeszcze spędzić czas testując swoje rozwiązania, nie pomaga. Sam low-effortowo startując przekonałem się o tym na 2B, które mi 'spadło' i musiałem się sporo napocić w późniejszych rundach żeby nadrobić tę stratę do koszulki.

Osobiście bardzo mi się podoba fakt, że w dywizji C można pozbyć się paranoi potyczkowej i po prostu po rozwiązaniu zadania przejść dalej nie martwiąc się że trzeba jeszcze spędzić 1-2 godziny na testowaniu wszystkich casów i stressowaniu z brutem.

Pewnie organizatorzy nie byliby chętni od razu dać wszystkich rund z odsłanianiem, ale może chociaż jedną dodatkową? Proponuję A - to całkiem smutne, że trzeba godzinami kminić hardkora i jeszcze można zzerować. Na koszulkę to nie będzie miało wpływu, ale chociaż dostęp do finału mniej zaporowy... Co myślicie?

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

Ja tradycyjnie chciałem podziękować organizatorom, którzy włożyli bardzo dużo pracy w przygotowanie wspaniałych zadań, których rozwiązywanie sprawiło mi bardzo dużo przyjemności. Zadania takie jak Wersja dla profesjonalistów, Mędrcy czy Łamigłówka zapamiętam na pewno na długo. Smutno mi jedynie z tego powodu, że na żadnym innym konkursie nie uświadczę tak wspaniałych zadań i na kolejne potyczki będę musiał czekać rok :) Pozdrawiam i podziwiam waszą pracę Panowie! :)

@skracanie ułamków. trochę na boku. Jeśli już licznik i mianownik sa duże, warto chwycić "binarny" GCD. Liczba "duzych" operacji arytmetycznych" podobną (O(n), n=liczba bitów liczby), ale zamiast dzielenia (brania modulo), ktore sa kosztowne dla duzych liczb, mamy tylko operacje "liniowe" (dodawanie/odejmowanie, dzielenie przez 2).

Ale jak poprzednicy powiedzieli, dało się ułamków (a nawet mnozenia/dzielenia duzych liczb przez siebie) pozbyć, odpowiednio dobierając trzymane parametry (i, przynajmniej u mnie, majac kwadratową zależność czasu od liczby węzłow, ułamki _chyba_ pozwalały tego uniknać).

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.