W poprzedniej edycji Kamil Dębowski napisał feedback do każdego zadania i bardzo mi się to spodobało, więc postanowiłem również takie coś napisać. Z ogólnych przemyśleń to wydaje mi się, że na pewno seria C była bardzo dobrze wyważona. Zrobienie całej serii na 10 nie sprawiało ogromnego wyzwania, choć trudność poszczególnych zadań wzrastała. Zadania z serii A natomiast w tym roku były bardziej bezlitosne dla (stosunkowo kiepskich) brutów - dwa razy wchodziły na zero.


1C = Finaliści
Zadanie rozgrzewkowe, żeby zachęcić ludzi do startowania i żeby każdy mógł zdobyć jakieś punkty. Podobnie jak co roku, może takie być na 1C.
1B = Praca
Zadanie ogólnie dosyć proste i odpowiedni pomysł przychodzi w zasadzie od razu, jak się w końcu ułoży w głowie, które spotkania można / trzeba / nie da się zrealizować oraz zauważy constraint n <= 8000. Zrozumienie treści zajęło mi dłużej niż odpowiednie obserwacje.
1A = Teleport
Zaskakująco trudne jak na 1A, bardzo łatwo wymyślić bruta i jakieś heury do niego. Próbowałem w miarę różnych podejść i z żadnego nie umiałem wycisnąć złożoności pesymistycznej lepszej niż O(n^4). Koniec końców wrzuciłem bruta z heurami (jeśli dla pary teleportów a,b mamy świadka u,v, że bak ma mieć co najmniej tyle co już w innym rozwiązaniu to early exit ze sprawdzania tej pary a,b + przeglądanie par u,v w kolejności d(u,v) malejąco), który wszedł na 10. Jak dla mnie to dobrze, choć jakiś niedosyt jest że nie udało się wymyślić oficjalnego rozwiązania. Na plus, że zadanie daje wiele otwartych ścieżek do eksploracji i kombinowania. Heury, które ostatecznie wrzuciłem, wymyśliłem stosunkowo na początku, już po kilkunastu minutach kminienia, choć nad samym zadaniem spędziłem łącznie kilka godzin, szukając O(n^3).

2C = Szkoła
Proste zadanie na sort, na 2C może być. Na 3C raczej już by było za łatwe.
2B = Wyliczanka
Do zrobienia jest całkiem przyjemna i w miarę naturalna obserwacja, jak się chce dokładnie poprzeliczać na papierze to idzie ją zrobić w pół godziny. Ja niestety zakopałem się w implementację, która zajęła mi 3+ godzin z powodu przede wszystkim problemów z WSLem na Windowsie, ale też jakichś off-by-one'ów, zbyt dużego skomplikowania implementacji, złego znaku nierówności itd. Dziękuję Krzysztof Potępa za egzostywne testy na forum, bez nich ten proces trwałby chyba jeszcze dłużej XD
2A = Egzamin
Ogólnie spostrzeżenie, że trzeba przechodzić w kolejności malejącej i że znaczenie mają tylko prawdopodobieństwa w t, t + 2, t + 4, … wymyśla się od razu, podobnie jak formułę na sukces dla nich. To już daje z bruta na O(n^2). Ponieważ taki brut nie przechodzi maxtestów, człowiek zaczyna się zastanawiać nad jakimś bucketowaniem, które w połączeniu z FFT daje O(n**1.5 log n). Rozwiązanie trochę przemocowe w porównaniu do innych pomysłów z forum, ale zadanie moim zdaniem łatwiejsze niż 1A, gdyż szło je tak właśnie przepałować stosując standardowe techniki.

3C = Akwarium
Zacząłem od napisania bruta, który szedł po wszystkich trójkach (a, b, h) i sprawdzał, czy a**2 + b**2 + h**2 jest kwadratem (i jeśli tak, to czego -- liczby są na tyle małe, że sqrt ma wystarczającą precyzję). To działało w 37 sekund, a w dodatku cały output miał tylko jakoś 22kB czy coś takiego (printowałem difference array wyników, a nie same wyniki, więc w kodzie jeszcze musiałem zrobić sumę prefixową). Ponieważ wyszło, że stablicowanie wszystkiego wchodzi, to tak zrobiłem. Raczej wiedziałbym jak zrobić to zadanie gdyby limity były do większych n (podobnego typu zadania są całkiem liczne na Project Euler) i może trochę szkoda, że nie zostały zwiększone, żeby jednak takie tablicowanie wyników nie wchodziło na 10, bo tak to trochę się zadanie strywializowało i poniekąd zmarnowało.
3B = Mnożenie cyfr
Sama koncepcja dynamika po prefixie liczby dosyć się tu narzuca, ale ile było zabawy, żeby to jakoś w sensownym czasie działało! Bardzo dobrze się przy tym zadaniu bawiłem, wycinając wektorami mapy / sety gdzie tylko mi się udało. Ostatecznie główna optymalizacja, dająca 10 zamiast 6 polegała na dopisaniu lazy ewaluacji stanów dynamika, co miało zaskakująco duży wpływ na czas działania -- szkoda, że pomyślałem o tym dopiero po kilku godzinach zabawy. Zadanie bardzo mi się spodobało.
3A = Opieka
Zadanie jest bardzo trudne w wymyśleniu jakiegokolwiek bruta, dającego przekonanie, że jest on poprawny. Co więcej, z powodu zabaw z MNO, do tego zadania napisałem tylko na szybko heurę, polegającą na zmultiplikowaniu instancji n/2, n/2+1,...,n razy (wyszło mi na intuicję, że mianownik jest <= n, a nie ma sensu sprawdzać mianownika 2, jeśli będzie się sprawdzać też np 4 -- sprawdzając mianownik 4, wyjdzie nam po prsotu 2 razy większy licznik, jeśli poprawna odpowiedź ma mianownik 2). Każdą taką instancję weryfikuję już całkowitoliczbowo, bez subpodziałów. Niestety brakło czasu, żeby tu coś mądrego wymyślić, a backtracking nie wchodził nawet na 1p :( Zadanie ciekawe, może być, szkoda, że nie umiem takich rozwiązwać.

4C = Wieża
Zadanie na nietrudnego do wymyślenia dynamika, czyli dobre na dywizję C. Warunek, że rozmiary klocków mogą być różne to tylko taki zaciemniacz, żeby analizować stany dynamika blokowo.
4B = Zbieranie klocków
Zadanie fajne, chociaż nie miałem w ten dzień zbytnio dużo czasu, więc niestety nie miałem szansy pomyśleć wystarczająco dużo. Brut z odpalaniem po każdym query od nowa odcinania wchodzi na 4, albo na 5 po usunięciu jak największej liczby map i setów. Myślę, że całkiem uczciwe jak na serię B.
4A = Piracka chciwość
Całkiem szybko narzucał się brut w O(n^2 log n) idący +/- jak w rozwiązaniu znanej wersji zagadki. Ten brut wchodził na 0. Uważam, że to o tyle uczciwe, że na zadaniu 4A brut dostający jakieś punkty powinien jednak reprezentować pewne obserwacje i wysiłek.

5C1 = Migawka
Ja zacząłem od napisania losowania plasz i patrzenia, które dają dobre wyniki, a że akurat patrzyłem na plansze o bardzo małej liczbie wierszy (np tylko 3 wiersze), to szybko trafiłem na wylosowanie takich, które miały na końcu linii w miarę długi ciąg 0 lub 1. I to narzuciło pomysł, żeby napisać takiego wężyka co idzie po kwadracie 99x99. Zadanie bardzo urocze, nie miałem przyjemności skorzystać z wizualizera, więc się nie wypowiadam.
5C2 = Turniej trójek
Binary search w binary searchu daje 10p. -- jak na końcowe zadanie serii C może być, trzeba policzyć jakiś dwumian albo w inny sposób sobie rozpisać wzór.
5B1 = Heavy Metal
Po pierwsze sprawdzamy Dijkstrą, czy to się w ogóle da zrobić. Podejść do znalezienia najdłuższej ścieżki miałem cztery w tym zadaniu, ostatecznie najlepsze okazało się szukanie optymalnej ścieżki od końca + early exit jeśli potencjalna dalsza ścieżka będzie w stanie dać mniej niż aktualny best. Trudno mi powiedzieć, jaki miał być wzorcowy algorytm, bo moje rozwiązanie raczej przypomina przeheurowanie Dijkstry.
5B2 = Podciągi
Znów brut jak w 4B, polegający na sprawdzeniu po każdym query od nowa: zliczamy wszystkie unikalne słowa oraz takie, które są unikalne na tylko jeden sposób i odejmujemy. Wychodzą do wymyślenia dwa przyjemne dynamiki i ogólnie jest frajda rozwiązać nawet taki uproszczony wariant tego zadania. Taki brut wchodzi na 3 i to jest chyba całkiem uczciwe, choć chyba żałuję, że nie próbowałem dodawać jakiegoś cache'owania prefixów, żeby próźniej obliczać tego dynamika tylko od punktu zmiany.
5A1 = Gładkie permutacje, 5A2 = Liście
Nie ruszyłem ostatecznie tych zadań, wyglądają na trudne. Do liści idzie wymyślić bruta, ale spojrzenie na podzadania raczej przekonuje, że wyjdzie 0. Do permutacji trudno nawet o bruta, choć warunek a <= 20 dawał jakiś potencjał.

Ogólnie zadania mi się podobały i reprezentowały tradycyjnie wysoki poziom, choć były nieco łatwiejsze niż rok temu (aż 9 osób z 120p. po 4 dniu!), więc próg będzie pewnie wyższy i do finału trochę punktów zabraknie. Dziękuję uprzejmie Organizatorom za interesujący dobór zadań i kontynuowanie tradycji tego wspaniałego konkursu.

Ja bym głosował za jawniejszym mówieniem jakie są podzadania, bo to trochę guesswork co koniec końców dostanie punkty, a co nie. W LIS były ładnie rozpisane, ale straciłem dużo czasu na 1) żyłowanie bruta w 4A, 2) zrobienie GLA dla 2<=a<=6 i obie te rzeczy dały finalnie 0 punktów. Gdybym znał zawczasu opisy paczek, to bym wiedział, że nie ma sensu, a raczej było sensownym mieć nadzieję, że oba coś dadzą.

I trochę się sprzeciwię opiniom, że sensowna punktacja za bruty. 0 pkt za O(n^2 log n) w 4A to jakaś pomyłka. 4 czy tam 5 za bruta w 4B też. Ten brut do 4B zajmuje kilka minut, a całe zadanie zajęło mi około 10h roboty. Punktacja powinna jakoś odzorowywać potrzebny wysiłek, a tutaj pierwsze 10 minut dawało 4 pkt, a na zdobycie kolejnych 6 trzeba się niemiłosiernie męczyć wiele godzin?

Oczywiście wielkie dzięki za organizację, bardzo fajne zadania. Szczególnie 3A moje ulubione.

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.

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

[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ę.

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

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

@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

[MIG] - czy to jeszcze programowanie? Po napisaniu inputu dla visualizera, wystorczyło go wyprintować. Równie dobrze moglibyśmy wysyłać pliki .in...
[AKW] kusiło mnie ztablicować wyniki. Zgadzam się, że za hardcode rozwiązania nie powinno wpadać 10 punktów
[ZBI] limit pamięci był tak duży, że można było normalnie zrobić sobie tablicę bitów z całą planszą, która mieściła się w pamięci (625e6 bajtów).

@Albert
I co by Ci dała taka tablica bitów z całą planszą? Pomijając ogromne straty na czas alokacji i dostępu do takiego molocha, to już chyba serio lepszy set<pair<int, int>>. Z resztą ja w brucie na 5p utrzymywałem planszę jako graf, gdzie wierzchołki "zapominają" swoją lokację i masz normalną tablicę sąsiedztwa (pamiętany jest kierunek NWSE), a map<pair<int, int>, int> mówi jakie id wierzchołka jest przypisane danemu polu i jest updateowane raz na query. Więc literalnie tablica bitów na całą planszę to jest wręcz zaszkodzenie sobie.

Co do komentarza do MIG to się nie zgadzam: nie wszystkie zadania na konkursie algorytmicznym muszą się wiązać ze skomplikowanym kodowaniem, wręcz imo ważniejsza jest ta część koncepcyjna (która czasem się odwołuje do użycia znanych technik programistycznych, np. bitsetów żeby mieć złożoność O(coś/64)). To że zadanie nie ma inputu, to nie jest żaden problem, bo bardzo łatwo by było go na siłę dodać (np wczytaj dwie liczby n, k i wypisz planszę o rozmiarze nxn osiągajacą score k, i napisac w opisie testów, że i-ta grupa ma n = 100, k = (10i - 1)^2).

Co do AKW: trudno by było zapewnić brak stablicowania. Gdyby np było n <= 10 000, możnaby stablicować odpowiedzi dla tych większych n, które jeszcze się mieszczą w limicie na rozmiar kodu, a małe n brutem liczą się szybciej. n istotnie większe od 10 tys znacząco komplikuje rozwiązanie w stosunku do docelowego zliczania wartości a^2 + b^2 oraz k^2 - h^2.

Wydaje mi się, że zadania C mają przy okazji charakter edukacyjny, więc całkiem fajne jest pokazanie zadania, które może być rozwiązane właśnie tak, że piszemy wolny program, z którego wyniku możemy skorzystać we wzorcowym rozwiązaniu. Jak się to zna to wydaje się oczywiste, ale jeśli ktoś to zobaczył po raz pierwszy to myślę, że fajna lekcja.

Kilka komentarzy do niektórych zadań ode mnie.

[1A] TEL
Za nic nie mogłem wpaść na O(n^3), szkoda że nie pożyłowałem tego najprostszego O(n^4).

[2B] WYL
Dawno zadanie z rundy drugiej tak mnie nie wymęczyło. Koszmarna przypadkologia, choć mój kod i jest przesadnie "poifowany", bo to już była lekka paranoja. Ogólnie moje rozwiązanie polegało na stopniowym skracaniu zakresu wyliczanki o 1 przy ustalaniu 3 przedziałów wartości kolejnego elementu: pod warunkami, że znajdują się w nim 0, 1 lub 2 końce wyliczanki. Jeżeli element nie mieści się w danym przedziale, to ten przedział wypada. Jeżeli wypadną wszystkie 3 przedziały, to mamy NIE.

[3B] MNO
Bardzo przyjemnie mi się nad nim myślało (moje ulubione zadanie tych Potyczek), a rozwiązanie okazało się eleganckie. Podobny sposób rozumowania jak w poście Pawła wyżej.

[5C] TUR
Zadanie, które najlepiej świadczy o moim zmęczeniu umysłowym w okresie jego rozwiązywania. Dość powiedzieć, że najwięcej czasu straciłem przez niedodanie na kartce jednego ze składników wielomianu trzeciego stopnia i bezmyślne przepisanie błędnych wzorów do programu, czego nie zauważyłem przez dobrych kilka(naście?) godzin. Ogólnie trochę paskudne zadanie do samodzielnego testowania z pułapką dla osób, które za szeroko ustawiały zakres wewnętrznego binsearcha.

[5C] MIG
Nie zgadzam się ze stwierdzeniem, że nie było to zadanie programistyczne. Pewnie, byłem w stanie szybko "ręcznie" dojść do rozwiązania za 9pkt, ale nie dałbym rady zrobić 10pkt bez napisania sobie dodatkowego programu, który sprawdzał każdy układ punktów w kwadracie 4x4.