Napiszę to z perspektywy starego boomera, który zaczynał przygodę z Potyczkami jeszcze w LO w 2007 i nie jest wybitnym orłem w dziedzinie algorytmów, nie wygrałem nigdy żadnej olimpiady czy nie kończyłem mimuw. Lubię natomiast brać udział w tych konkursach dla funu. I po pierwsze na przestrzeni tych lat udało mi się wygrać koszulkę tylko dwa razy, ale przy ostatnich limitach 128 osób i moim skill'u, który już się raczej nie poprawi znacząco nie mam szans to wygranie.
Wobec tego tutaj ogromna prośba do organizatorów o pogadanie ze sponsorem i przemyślenie zwiększenia ilości na kolejne edycje.
Top 256, które było 2-3 lata temu, plus np próg połowy punktów do zdobycia z katerogii B+C to całkiem fair deal dla osób, które poświęciły kilka wieczorów na swoje hobby :)

Proponuję zmianę zasad obliczania rankingu.

Punkty za rundę = A + MAX(A, B) + MAX(A, B, C)

W przypadku równej ilości punktów decydują punkty zdobyte w A, potem w B, a potem C.

Zawodnik który rozwiąże dwa zadania z A zdobywa 60 punków, podobnie jak zawodnik który rozwiązał trzy zadania z B. Pierwszy zawodnik wygrywa jednak małymi punktami (więcej punktów zdobytych w grupie A). Obaj zostaną wyprzedzeni przez zawodnika, który rozwiąże dwa zadania w A i jedno w B.

W B+C - punkty za rundę to MAX(A, B) + MAX(A, B, C)

Uzasadnienie:

Obecnie najlepszą strategią jest rozwiązywanie w pierwszej kolejności zadań najłatwiejszych (nie ma żadnej premii za zadanie trudniejsze - wręcz przeciwnie - rozwiązując A zamiast B zmniejszam szanse na koszulkę).

Łatwiejsze zadania ułatwiają zabawę początkującym ale potem przeszkadzają (zajmując czas) w "przesiadaniu" się do trudniejszej grupy.

Nowy system miałby kilka zalet:

- Mogę zaryzykować rozwiązywanie trudniejszego zadania - jeśli mi się uda nie tracę prawie nic w rankingu nie rozwiązując zadań łatwiejszych. Zatem ciekawie robi się już na etapie wybierania zadań. (Można wymyślić o tym zadanie - Bajtazar rozwiązuje zadania z rundy N w czasach tA, tB, tC i z prawdopodobieństwami pA, pB, pC. Pomóż Bajtazarowi wybrać optymalny zestaw zadań).

- Mniej zadań "marnuje się" z powodu braku czasu - teraz jeśli zagrzebię się w B lub C nie próbuję nawet zaczynać/czytać A. W nowym systemie przeczytałbym wszystkie zadania i mógłbym zaryzykować rozwiązanie zadania trudniejszego.

- W ścisłej czołówce nadal jest presja na rozwiązywanie zadań ze wszystkich grup - po pierwsze ze względu na małe punkty, po drugie nie wysyłając prostszych zadań dużo ryzykuję (jeśli wyślę tylko A i się pomylę mogę stracić do 30 punktów).

- Realne staje się wprowadzenie grupy D :-))

@Marcin
Co najwyżej jednego? Znaczy technicznie prawda, ale obserwacja pomagająca zrobić całe zadanie i nie rozpatrywać tego nieistniejącego case'a jest nawet, że wszystkie głosy kupisz za nie więcej niż max(a_i), czyli to 64

@Paweł, no nieźle z tym link-cutem, gratki, że 10/10, ale overkill potężny trzeba przyznać, jak już nie chcemy na setach/przenumerować i na zwykłym drzewie przedziałowym, to wciąż są prostsze struktury by trzymać ścieżkę z tych klocków i rozcinać ją w odpowiednim miejscu, taki chociażby treap

Trochę zoptymalizowałem stałą w Piratach w piątek rano, ale już moje czwartkowe rozwiązanie wbiło 2pkt. W tym zadaniu kluczowa obserwacja jest taka, że przy kupowaniu głosów piratów co najwyżej na jednego trzeba będzie wydać więcej niż K=64. Czyli jak mówimy o O(N^2) to można zrobić to O(N*(K+N)) jak też i O(K*N^2) -- to drugie podejście pewnie przekroczy limit czasu

Też nie lubię nie egzekwowalnych zasad, ale w zawodach w niekontrolowanym środowisku większość zasad jest nie egzekwowalnych. Np. zasada "nie dzielenia się złożonością/rozwiązaniami" i "nie zatrudniania kogoś z top 20 z cfa żeby rozwiązali ci zadanie 3A za pieniądze".

Myślę że zasada dobrej wiary żeby nie używać czegoś zupełnie zautomatyzowanego do competetive programmingu jest OK. Pewnie też jakiś anty-plagiat mógłby znaleźć te rozwiązania jak wielu uczestników skorzysta z tego samego narzędzia.

Część z zadań C pewnie można by rozwiązać za pomocą GPT o3 w kilku iteracjach zapytań i testów, ale myślę że nie jest to duży problem.

Mi się ta zasada nie podoba głównie z jednej przyczyny - jest kompletnie nieegzekwowalna. Stawia osoby uczciwe, które zastosują się do zasady, w gorszym położeniu niż nieuczciwe, które z takich narzędzi i tak będą korzystać.

@Wojtek: może racja z tym 4 za bruta do 4B. Nawykłem do myślenia, że bruty w serii B dają zazwyczaj całkiem sporo punktów, jako że limity są mniej ciasne. Nie miałem świadomości, że całe zadanie było aż tak trudne (miałem w pt czas tylko na pisanie brutów). W takiej sytuacji rzeczywiście rozdźwięk między 4 a 10 punktów wydaje się przesadzony.

@Marcin:
1) widać jakoś lepiej napisałeś piracką chciwość (no i bez loga) ;) Dużo czasu spędziłeś na optymalizowaniu na tym zadaniu?
2) w Akwarium to spodziewałem się, że pewnie będzie trzeba jakieś trójki pitagorejskie powyznaczać albo rozwiązywać równanie typu x^2 + C = k^2, na co też są znane techniki, to wolałem napisać tablicowanie i iść dalej z życiem. Dlatego pisałem, że szkoda, że limitów nie podbili na tyle, żeby tablicowanie jednak nie wchodziło, a szare komórki trzeba było bardziej ruszyć ;)

@Paweł:
Fajna recenzja, mieliśmy podobne doświadczenie! :D
1) 5C-2 nawet nie zauważyłem że tylko pierwszy tysiąc + ostatni ma znaczenie :p
2) 5A-1 - szkoda że nie poświęciłem zadaniu więcej czasu w takim razie, bo dużo komentarzy że brut na 2 był łatwy.

Otwieram dyskusję o nowej zasadzie o nie używaniu AI. Rozumiem idee, że auto-solvery pewnie rozwiązałby całą rundę C I część rudny B/A, ale chyba wolałabym żeby była dosyć bardziej doprecyzowana jakich auto-solverów AI nie wolno używać.

Zasada o nie używaniu AI w ogóle była dosyć zaskakująca, bo Copilot i GPT są zintegrowane w workflow programistów na tyle, że niektórzy pewnie musieli wyłączyć autocomplete w swoich edytorze żeby nie łamać zasad. Ja pewnie rozluźniłabym zasady żeby pozwolić na te narzędzia.

Ponadto bardzo dużo narzędzi których każdy używa na co dzień używa AI pod spodem (np wyszukiwarka google).

[1C] - Finaliści
Podoba mi się pomysł, że 1C wprowadza do zasad. W tym roku pierwszy raz mogą mi się przydać :)

[1B] - Praca
Aż kusi, żeby w treści zmienić 'rozwiązywanie rund zdalnych' na 'rozwiązywanie zadania Praca' :)
Ekspresowo wymyśliłem coś kwadratowego, a potem jeszcze długo myślałem czy się nie da szybciej,
bo jakoś przeleciało mi obok głowy że dla n <= 8000 to już wystarczy.

[1A] - Teleport
Nie wpadłem na nic sześciennego, ale wpadłem na rozwiązanie w
O(n^4) ze stałą ~1/47 dla najgorszego przypadku więc uznałem, że wejdzie i nie trzeba myśleć dalej.
(Obliczam najkrótsze ścieżki między każdą parą wierzchołków i potem dla każdego ustawienia teleportu
sprawdzam w kolejności od najdłuższych ścieżek jaka jest nowa długość, i stopuję na długości średnicy.
Trudniejsze od zadania było pewnie zrobienie testów, które oddzielą takie O(n^4) od O(n^3)...

[2C] - Szkoła
Fajne, można się sortować nauczyć, nawet zgubiłem jednego long longa i miałem na 8 przez chwilę.

[2B] - Wyliczanka
Bardzo długo nie mogłem wymyślić nic sensownego, mimo, że sobie spisałem, że mogę podzielić a_i
na l_i i r_i czyli ile razy przyszedłem z prawej a ile z lewej. Coś myślałem o ścieżkach eulera,
a wyszło w końcu, że chciałem napisać bruta fiksując start i koniec.
Skończył się na tym, że dla ustalonego startu mogłem sprawdzić wszystkie końce w O(n), a jak już zauważyłem
że zmiana czegoś o 1 zmienia ciąg o 0, -1, 0, -1... to już wiedziałem, że się będę męczył z kejsologią na parzystości.
Treść mi się podobała, miałem wrażenie, że zbyt toporna kejsologia jak na 2B, ale mam talent do przekomplikowywania.
Czekam na omówienie, bo pewnie się da zrobić jakoś bardziej elegancko.

[2A] Egzamin
Super problem, szkoda, że takie egzaminy już dawno za mną...
Bardzo się cieszyłem jak coś co myślałem, że jest przyśpieszonym brutem weszło mi na 10,
a ignorowałem tylko depeki z wynikiem < 2*10^11. Precyzja robi brrr.

[3C] - Akwarium
Zobaczyłem n <= 5000, napisałem bruta, stablicowałem i zapomniałem o zadaniu.
Nie wiem czy ktoś nowy by o tym pomyślał, ale wiedziałem, że da się zrobić szybciej, więc
spodziewam się, że nowi mieli właśnie tam zabawę, która była na dobrym poziomie :)

[3B] - Mnożenie cyfr
Bardzo dużo funu miałem. Idąc spać wpadłem na pomysł, że po jednym ruchu w rozkładzie na czynniki pierwsze
są tylko czynniki 2, 3, 5, 7 czyli takich liczb będzie "jakoś mało". Wstałem, napisałem wyszło, że to za dużo.
Ale wystarczyło wyciąć te liczby które schodzą do zera bo ich jest "jeszcze mniej". Bardzo dużo zabawy przy tym miałem,
ulubione zadanie z tej rundy pod względem stosunku zabawy w kminie i zabawy w klepaniu.
O("jakoś mało" * długość_liczb * liczba_cyfr + q * "jeszcze mniej" * długość liczb) mnie satysfakcjonuje.

[3A] - Opieka
Długo myślałem, ale bez skutku, napisanie bruta było w sumie dosyć trudne, wyzerowałem, bo nie usunąłem testkejsów
po testowaniu z forum >facepalm<, cieszy przez to, że pewnie wchodził na zero, a imo jeden punkt by był zasłużony.

[4C] - Wieża
Fajny dynamik, chyba dobry poziom jak na C, poszło bardzo szybko, ten warunek na 5 punktów trochę dla zmyłki miałem wrażenie.

[4B] - Zbieranie klocków
Jezu jaka klepa, podobało mi się bardzo, szkoda, że bruty dostawały dużo punktów, bo to implementacja była tu trudna a nie kmina.
Wyszło ~500 linii kodu, nie zauważyłem, że mogę robić wszystko na setach, więc nauczyłem się w końcu Link-Cuta :D

[4A] - Piracka chciwość
Nie miałem czasu przez ZBI nawet rozkminić co i jak, a wychodziło, że łatwy kwadratowy brut. Tu akurat cieszy z perspektywy,
że punktów nie dawał, ale to imo niesprawiedliwe, lubię takie zadania, ale nie jak zjada na nie czas klepacki gigant typu Carcassone czy ZBI.

[5C-1] Migawka
Napisałem sobie szybki skrypcik w pythonie i rysowałem sobie te przykłady w paincie, w godzinę dotarłem do rozwa w (98*99) ruchów,
trochę się pobawiłem rysując głupoty, w końcu wpadłem na grzebień i wymaksowałem. Fajne i proste, dużo bardziej robialne niż Żarówki z poprzedniego roku.

[5C-2] Turniej trójek
Fajne! Wymyśliłem binsearcha po wyniku, nie zauważyłem, że da się zrobić więcej binsearchy i szukałem niedecyzyjnego dynamika szybszego niż kwadrat bez skutku...
Na szczęście potem wróciłem do tego binsearcha, skończyło się na binsearchu w binsearchu, szkoda, że nie wymagało zrobienia trzeciego w środku, bo się dało :D
No i kmina, że wszyscy poza pierwszym tysiącem i ostatnim z automatu są do wywalenia bardzo fajna :)

[5B-1] Heavy metal
Dobra zabawa, nawet wbiłem na 10 żyłując swoje sqrt(10^9) * n * (n+m), liczyłem sobie ścieżki a'la Bellman Ford od przodu mnożąc, od tyłu licząc maksymalne wzmocnienie
o jakie można jeszcze przemnożyć. Nie wpadłem na pomysł, że mogę inaczej niż w pierwiastek, a to fajna kminka.

[5B-2] Podciągi
Masakra, przegapiłem bardzo prostego dynamika i skończyłem z samym wykładniczym brutem za jeden punkt. A byłem bardzo ciekaw, bo tekstówki na potyczkach
mają fajne kminki w środku :(

[5A-1] Liście
Zajebisty dinozaur i darmowe 2 punkty, co jest pomyłką jeśli chodzi o stosunek nakładu pracy do punktów w porównaniu do [OPI].
Żałuję, że nie spędziłem tu więcej czasu zamiast męczyć przegapione podciągi bo wyglądało na kopalnię punktów dla zainteresowanych
czymś nieoptymalnym.

[5A-2] Gładkie permutacje
Przestraszyłem się matematyki, przyznaję się, nawet nie próbowałem :D

Ogółem bardzo dobrze się bawiłem, cieszyły mnie trudności implementacyjne, szczególnie klepanie ZBI, zaskakująco dużo punktów dało się zrobić
żyłując nieoptymalne rozwiązania co jest trochę smutne ale też cieszy, bo effort się w końcu opłacił.
Pierwsze potyczki gdzie nie straciłem punktów na testowaniu :D
Zasługa bardzo exhaustive testów, dziękuję wszystkim forumowiczom, którzy wrzucali paczki.
Nitpick dla uczestników, którzy wrzucali paczki niezgodne z typowym dla forum formatem, niektórzy miałem wrażenie,
że robią to celowo, żeby innym zmarnować te kilka minut. Strategicznie to dobry ruch, ale psuje zabawę.

Chciałbym w imieniu swoim (i wszystkich plusujących) podziękować bardzo organizatorom za świetnie zorganizowany konkurs programistyczny.
Zawody odbyły się bez żadnych wpadek za co należą się słowa uznania.
Poziom zadań sekcji C uważam, że był odpowiedni.
Wyniki moich zgłoszeń pojawiał się zwykle zaraz po północy (co swoją drogą też po części zachęcało do wysyłania moich rozwiązań odpowiednio wcześniej).
Historyjki w zadaniach były na najwyższym poziomie, za co należą się osobie je tworzącej osobne podziękowania (floating point... genialne!).
Żałuje, że nie znalazłem odpowiedniu dużo czasu na zastanowienie się nad niektórymi zadaniami, gdyż wyglądają na bardzo ciekawe. Mam nadzieję, że szybko pojawią się na szkopule i będę mógł nad nimi jeszcze posiedzieć.
Edit: Zadania z wizualizacjami to miła odskocznia od zwykłych zadań. Bardzo się cieszę, że pojawiło się w tym roku.

Wziąłem wolne od życia na tydzień w Bajtocji i nie żałuję (choć w weekend już zjazd formy i zrobiłem tylko HEA i MIG). Wikipedia podpowiada, że dostałem się na finały PA 15 lat temu, uaktualniłem swoje dane w rankingu. (Pamiętałem, że byłem kiedyś w Zielonej Górze, ale myślałem, że jako juror). Pozdrawiam i podziwiam wszystkich potwierdzających testy.

@Heavy Metal
Moje, wbiło 10/10:
1) BFS od mikrofonu, wzmacniaczami o łącznym wzmocnieniu <= MAX_Q = (1 + sqrt(10**9))
- tablica T[i][s] = 1, gdy ścieżka o sygnale s do rutera "i" istnieje (0 w przeciwnym przypadku)
2) podobnie, idąc od głośnika wstecz, wzmacniaczami o łącznym wzmocnieniu MAX_Q
- tablica R[i][q] = x > 0 oznacza, że z rutera "i" da się przesłać do głośnika sygnał x, wzmocniony na końcu do x*q
- idąc wstecz z R[b][q]=x przez wzmacniacz (a,b,w), R[a][q*w] = max(R[a][q*w], min(P[a], x/w))
3) w ostatnim kroku dla każdego wzmacniacza (a,b,w) obliczam max{ q * w * max(s <= R[b][q] / w : T[a][s] == 1), 1 <= q <= MAX_Q } -- tablicując T1[x] = max(s <= x : T[a][x] == 1)

@Teleport
- faktycznie, łagodnie oceniane (może dlatego, że poniedziałek?)
- moje O(N^4) dostało 9/10 bez żadnych heurystyk -- no chyba, że za heurystki uznajemy "goto":

...REP(s,n) FOR(t,s+1,n1) {
......g = 0;
......REP(i, n) {
.........FOR(j, i+1, n1) {
............h = D[i][j];
............if (h <= g) continue;
............h1 = static_cast<short>(D[i][s]+D[t][j]);
............if (h1 < h) {
...............h = h1;
...............if (h <= g) continue;
............}
............h1 = static_cast<short>(D[i][t]+D[s][j]);
............if (h1 < h) {
...............h = h1;
...............if (h <= g) continue;
............}
............g = h;
............if (g > res) goto break2;
.........}
......}
......if (g < res) res = g;
......break2: ;
...}

UPDATE: dodałem wcięcia przez .........

@Piracka Chciwość
- mój brute O(N^2) dostał 2/10 (może to kwestia optymalizacji stałej, używania C++ zamiast Pythona, itp)

@Akwarium
- nie trzeba było tablicować wyników, rozwiązanie "liczymy T[i] - na ile sposobów i=a*a+b*b, oraz U[i] = na ile sposobów i = m*m-h*h (dla m <= n), wynik to sum (T[i]*U[i])" mieściło się w limitach

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

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.

Zadania jak zwykle super, a zabawa jeszcze lepsza!

Mam tylko pytanie co do limitów czasowych: czy w tym roku były celowo wysokie, czy może nie dało się inaczej ich dobrać? Miałem wrażenie, że w tym roku dało się przepychać więcej zoptymalizowanych pałek niż zwykle.

Też 9802