Ostatnia puszka energetyka chyba była zbędna. Dlatego, żeby wyszło z tego coś pożytecznego, niech tu będzie feedback do zadań (trochę długi, ale mam nadzieję, że przydatny):

Zadania bardzo mi się podobały, wielkie podziękowania dla organizatorów! Napiszę kilka słów o wybranych zadaniach:

1A – miałem rozwiązanie w O(n³), smutne, że wiele błędnych rozwiązań przeszło wszystkie testy. Nie do końca wiadomo, co z tym zadaniem zrobić – wydaje się, że nie da się odsiać wszystkich błędnych rozwiązań, jednocześnie akceptując poprawne. Mimo to, cieszę się, że udało mi się rozwiązać je w „uczciwej” złożoności – według mnie jedno z najładniejszych zadań w konkursie.

1B – dość oczywiste zadanie (co nie jest złe) z bardzo życiowym warunkiem xd. Może warto byłoby dać nieco mniejsze ograniczenia, bo początkujący mogli mieć problem ze zmieszczeniem się w limicie czasowym.

2B – ciekawe zadanie, moim zdaniem najlepsze z grupy 1-4B.

2A – najbardziej standardowe zadań typu A (miałem rozwiązanie FFT + D&C w O(n log² n)). Główną obawą było to, czy nie pojawią się błędy związane z precyzją. Na szczęście nie było problemów.

3A – najlepsze zadanie konkursu. Wymyślanie zajęło mi >5-6 godzin, a przez pierwsze 3 godziny byłem przekonany, że rozwiązanie wymaga flow xd. Spostrzeżenie, że wystarczy rozważyć tylko 2 możliwości dotyczące pierwszego elementu, jest bardzo eleganckie i nieoczywiste.

3B – dobre zadanie. Cieszę się, że nie zabrało mi zbyt dużo czasu, bo mogłem w pełni skupić się na 3A xd.

4A – interesujące zadanie, moim zdaniem znacznie łatwiejsze niż 3A. Cieszę się, że nie było problemów z TL (widocznie trudno wymyślić test lepszy niż losowy).

4B – zadanie, na które poświęciłem najwięcej czasu na implementację i debugowanie :(. Sama idea jest dobra, ale to zdecydowanie bardziej zadanie implementacyjne. Może warto byłoby rozdzielić 4A i 4B na różne dni, bo oba dotyczą struktur danych. Zgadzam się z Wojtechem, że 5 punktów za brute force to za dużo.

5B – oba zadania były ciekawe, może trochę łatwiejsze, niż powinny być (przynajmniej w porównaniu z zeszłym rokiem).

5A LIS – Z jednej strony fajnie, że jest tak wiele grup, ale z drugiej strony to prowokuje do pisania oddzielnych rozwiązań dla każdej z nich (i nie powiedziałbym, że rozwiązanie dla którejkolwiek grupy poza ostatnią zasługuje na oznaczenie 5A). Wydaje mi się, że w mniejszych ograniczeniach to zadanie mogłoby pojawić się we wcześniejszych rundach (bardziej standardowe, ale też mają swoje miejsce), a w tej rundzie zamiast niego mogłoby być 3A. Ale moje rozwiązanie wciąż się testuje, więc nie będę jeszcze za dużo narzekać xd.

5A GLA – zadanie, z którym przez ostatnie 2 dni przeżyłem całe życie xd. Dość szybko sprowadziłem je do liczenia diagramów Younga, ale potem przez 10 godzin nie zrobiłem żadnego postępu :(. Niestety, nic nie udało się wygooglować (choć na próby poszło >2 godziny), wydaje się, że nikt nie bada sposobów ich liczenia, albo to po prostu skill issue :). Wiedziałem, że odpowiedź będzie miała formułę, ale zupełnie nie rozumiałem, jak ją znaleźć. Jeśli ktoś z uczestników rozwiązał to, znajdując formułę, to może podzielić się, jak ją znalazł?
Uważam, że 3 punkty za c = a + b - 1 to za dużo. Po pierwsze, to dość znany fakt, który niewiele pomaga w rozwiązaniu, a po drugie, odpowiedź można było znaleźć w OEIS. Niemniej jednak, autorskie rozwiązanie jest bardzo piękne (choć nadal nie rozumiem, jak na to wpaść bez wcześniejszej znajomości).

Dodatkowe uwagi
Bardzo dobre treści, wszystko było zrozumiałe nawet bez tłumacza. Osobne podziękowania za szczegółowe wyjaśnienia i rysunek Bajtozaura!

Może warto dodawać więcej opisów grup, jeśli nie ułatwiają znacząco rozwiązania zadania (a może nawet i w takim przypadku).

Nie jestem pewien, czy ograniczenia 5e4 w prawie wszystkich zadaniach to dobry pomysł. Rozumiem, że to ma swoje zalety (nie sugeruje złożoności, zachowuje spójny styl treści), ale w zadaniach 2A i 4A bardziej skłaniało to do próby oddania rozwiązania kwadratowego.

Jeszcze raz dziękuję wszystkim autorom i organizatorom, miałem ogromną frajdę!

I derived a 2^a*a solution for GLA, with some ideas based on LGV-lemma. The first step is indeed to understand the answer is the product of two numbers, one of them can be found by hook-length formula directly. The other number is harder.

In the c=a+b-1 case, we should understand how to count ways to fill a rectangular Young tableaux. Another way to think of it is to start with a sequence xi=i, repeat N times: increment exactly one element while maintaining xi<x_(i+1); and end up with xi = yi, where yi = i+b.

To overcome the condition where x has to be increasing always, we can ignore this condition and instead count ways to reach y' for each permutation of y, and weight it by 1 if the permutation is even and -1 otherwise. The concept is just some inclusion-exclusion. I don't know if it is a direct application of LGV-lemma, but the spirit is the same, except that it is unnecessary to write the anwer as a determinant here.

Now when c is not a+b-1, we are actually counting ways to start at (0,0,..0,1,2,3..,) and end at some y, and we need to maintain xi<x_(i+1) unless they are both 0. Similar to above, we can ignore the increasing condition by considering ways to reach all permutations. This time we should instead impose that if i<j and xi and xj are both 0 at the start then we must increment xj first.

At last, we just need to do bitmask dp, storing the sum of (ways*parity of permutation) after fixing some prefix of y'.

I also think OPI is very funny problem.

Dodatkowa zgoda co do Bajtazaura: fajny rysunek i zabawne imię :) spodobały mi się przy czytaniu bajki ;)

@Yahor, co do tego 5e4 to jeśli wzorcówka O(nsqrt(n)) w EGZ, czy O(n log(n) K log K) gdzie K to to ograniczenie na chciwość w PIR, czy O((k+q)log(k+q)) w ZBI ma dużą stałą, to nie chcemy dawać n=5e5 i TL=doba bo sprawdzaczka tego nie przeżyje przy liczbie testów potrzebnej by uwalić wszystkie błędne rozwy, dajemy z grubsza najmniejsze n, przy którym czujemy się bezpiecznie, że brut typu O(n^2) jest bez szans, jak to będzie coś koło 50,000/75,000 to nie widzę w tym większego problemu zwłaszcza jak masz test-runy, jak zastanawiasz się, czy O(n^2) ma szansę przy n=50000 po prostu naklep, wrzuć na SIO z jakimś testem, który mniej więcej wybija maksymalny czas i zobaczysz, że niespecjalnie ma

Dzięki sprytnym optymalizacjom piraci O(n^2) mogą zostać zoptymalizowani do 7 punktów, a prawdopodobnie przy dalszym dopracowaniu można osiągnąć 10 punktów (nie przeszło 3 testów z limitem czasu). (Ja tego nie zrobiłem, ale mój znajomy BLOBVISGOD używał takiego podejścia).

Też żyłowałem O(n^2) do piratów i przeszło pod limitem wszystkie testy (5.53s/6s najgorzej). Dostałem 6 o dziwo przez głupie WA, które da się łatwo naprawić nie ruszając bottlenecka, więc z fixem prawdopodobnie dostałoby 10

Wydaje mi się, że jednak powinny być bardziej n ~ 100k w takich zadaniach. Na nieszczególnie zoptymalizowanym O(n^2) do egzaminu miałem już 2s z 3s TL na uruchomieniu próbnym.

@Konrad nie doceniacie umiejętności uczestników pod kątem żyłowania brutów. Jeżeli chodzi o moje własne zdolności w tym kontekście to są one bardzo słusznie niedoceniane, ale przy innych przypadkach jak widać się pomyliliście. Poza tym, nawet jeśli się koniec końców bruta wepchać nie uda, to takie limity są zaproszeniem dla uczestników aby próbowali i marnowali czas. Jak się chce odróżnić O(n) od O(n log n) to rzeczywiście podnoszenie limitów z powiedzmy 1e6 na 5e6 niewiele da w kontekście ich rozróżnienia, a ubije sprawdzarkę, ale w przypadku PIR gdzie chcemy odróżnić O(n polylog(n)) od O(n^2) to podniesienie z 5e4 na 1e5 da bardzo dużo, a sprawdzarki wcale jeszcze tak nie ubije. Poza tym nie widzę wielkiego problemu aby po prostu zmniejszyć limit na chciwość (oznaczmy go K) w tym zadaniu, więc dając 32 zamiast 64 to nawet sprawdzarki tak nie będziemy zamęczać, brutowi O(n^2) to niewiele pomoże, a o ile mnie coś nie omija, to nie pojawi się też żadne inne rozwiązanie, które w "niecny sposób" wykorzysta mniejszy limit na chciwość (chyba, że bardzo chcieliście odróżnić K log K od K^2, ale to się wydaje secondary issue)

Jak tak wszyscy się chwalą, to ja też się pochwalę, że wepchnąłem O((n + m + q) sqrt(n)) do LIS :)

Przykro mi to mówić, ale zrobiłem to samo dla LIS. Jednak moja rozwiązanie wykorzystuje bardzo proste operacje, a teoretyczna różnica 10x jest łatwa do zniwelowania. Tak czy inaczej, fakt, że zamierzone rozwiązanie jest tylko 10 razy wolniejsze od dość prostego podejścia z strukturami danych, a jednocześnie moje podejście bez większego zastanowienia również zdobywa pełne punkty, wydaje mi się pewnym niedopatrzeniem.