Dołożę swoje 3 grosze. Wydaje mi się, że zadanie WIE mogło trafić do dywizji C po to, aby można było szybko poznać wynik: czy dokładność rozwiązania jest już ok, czy jeszcze nie.

Dla takich nietypowych zadań z kategorii A lub B można zastrzec w regulaminie, że komunikacja o poprawności kodów źródłowych będzie odbywać się w sposób specjalny. Tak można zrobić np. z zadaniami rozproszonymi (jeśli kiedyś wrócą) oraz z zadaniami, dla których uczestnicy będą żyłować realny czas działania.

Również bardzo dziękuję za zorganizowanie tegorocznej edycji. Mimo że mam niedużą styczność z competitive programming, to jednak co roku nie potrafię nie wziąć udziału, tak mi się to zawsze podoba. Jest to dla mnie już taka mała tradycja przed świętami, która mi się zawsze bardzo miło kojarzy. :)

Przyłączam się do gratulacji i zachwytów nad oryginalnością zadań. Gdy odkryłem, że większość zadań wymyśliła jedna osoba, byłem w szoku (oczywiście rozumiem że całe jury miało mnóstwo roboty, bo przygotowanie zadania nie kończy się na spisaniu treści).

Uważam, że dobrze byłoby (jeszcze) bardziej spopularyzować Potyczki, dlatego pomysł z dywizją C jest świetny, ale w ciągu 2 lat uległ pewnej degeneracji :)

Może by ustalić jakieś umowne ramy trudności poszczególnych dywizji, np:
A: poziom IOI, B: poziom OI, C: poziom OIJ
oczywiście na każdym z tych konkursów jest pewna gradacja trudności zadań.

@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

Również bardzo dziękuję za ten konkurs <3 Bardzo odpowiada mi ten format z 36/60h na serię zadań, jako że będąc raczej początkującym nie wpadam na rozwiązania zbyt szybko, a implementuję je jeszcze wolniej :P Tu nie muszę się stresować z pisaniem rozwiązań w kilkadziesiąt minut.

A, i dzięki opracowaniom zadań otworzył się przede mną kolejny wymiar algorytmiki xD - nie miałem pojęcia, że są techniki optymalizacji DP i że można ich często używać zamiast za każdym razem liczyć na genialne olśnienia jak przyspieszyć algorytm.

> parametric search (<- nie potrafię wykazać że zachodzi ta fajna nierówność, które pozwala tego użyć)

Jeśli dobrze kojarzę, to jeśli mamy problem, w którym:
– trzeba podzielić dany ciąg wejściowy na k spójnych kawałków tak, by zminimalizować sumę kosztów kawałków; oraz
– funkcja kosztu kawałka spełnia „quadrangle inequality” postaci: koszt(a, c) + koszt(b, d) <= koszt(a, d) + koszt(b, c),
to automatycznie działa na tym problemie sporo optymalizacji dynamików: D&C, parametric search itd.

Intuicyjnie, quadrangle inequality jest swego rodzaju uogólnieniem pojęcia funkcji wypukłej na funkcje przyjmujące kawałki ciągu jako argument. Dla funkcji wypukłej (w 1D), „im większy x, tym szybciej rośnie funkcja”. Dla funkcji spełniającej quadrangle inequality: jak dokładam element X_i na koniec spójnego przedziału kończącego się X_{i-1}, to ten element zwiększa koszt przedziału tym mocniej, im dłuższy był oryginalny przedział.

Przykładowe funkcje, które spełniają tę nierówność:
– koszt(a, b) = kwadrat sumy od a-tego do b-tego elementu nieujemnego ciągu;
– koszt(a, b) = f(suma od a-tego do b-tego elementu nieujemnego ciągu), gdzie f jest funkcją wypukłą;
– koszt(a, b) = X[a] * Y[b], gdzie X jest ciągiem rosnącym, a Y jest ciągiem malejącym;
– koszt(a, b) = liczba spójnych podprzedziałów ciągu (x_a, ..., x_b) spełniających jakąś własność 𝒫.

Koszt z zadania to ten ostatni przykład, dla 𝒫 = „podprzedział oznacza poprawne wyrażenie nawiasowe”.

@Kamil

Heh, no właśnie napisałem sobie checkerkę czy moja odpowiedź jest poprawna, ale odpaliłem tylko na testach z forum, które najwyraźniej nie były zbyt mocne... :(

@Franciszek

Zabawa jak zabawa, dla mnie raczej masochizm.. Ale to chyba kwestia indywidualnego gustu

@Michał Miodek #89810 dzięki za przypomnienie, że liczy się, że spędziłem czas na trenowaniu umiejętności, a nie go przetraciłem. Co prawda mój czas na dostanie się na OI i ACMki już minął, ale uwielbiam algorytmikę i jednocześnie ćwiczę coś choć trochę użytecznego w pracy i na rozmowach kwalifikacyjnych

@Bartłomiej Szczygieł #89815 nom, nie pisałem całej biblioteki ze wszytkimi działaniami arytmetycznymi i bitowymi - zrobiłem (trochę nieefektywnie) jedynie big+big, big*big, połączone <big/big, big%big> oraz big-big (na potrzeby dzielenia). Wciąż z moimi skillami wywalało się na po jednym przypadku z sześciu grup testowych i dostawałem 4/10 : <

> to nie znaczy, że reszta z dzielenia przez 10^9+7 też jest niezerowa, nie wiem, czy był na to test, ale podejrzewam, że da się taki ułożyć
Był taki test (10j), mam z jego powodu 9/10.

Chciałem być mądry i stwierdziłem w algorytmie: jeśli mam pecha i przy bardzo nieszczęśliwym wyborze wektorów u, v i mnożników dla wierszy wyjdzie zbyt mały wielomian minimalny, to zaczynam od nowa, z nowym zestawem losowych współczynników, while(true). Zupełnie nie przeszło mi przez myśl, że wynik może być podzielny przez 10^9+7 i wtedy wielomian minimalny będzie zawsze stopnia mniejszego niż n. 🤡

Czy będzie możliwość dobijania zadań (np. na szkopule)?

Owszem korzystamy z Kirchoffa
Pierwszy krok: mając tą macierz chcemy umieć szybko pomnożyć przez nią wektor, zauważamy, że jak dla każdego d <= zakres weźmiemy wszystkie indeksy podzielne przez d i dla każdej komórki na przecięciu wiersza i kolumny z tego zbioru dodamy -phi(d), to w komórce i,j dodamy łącznie sumę po d dzielących gcd(a_i, a_j) z -phi(d), czyli -gcd(a_i,a_j), czyli dostajemy to, co trzeba z dokładnością do wyrazów na przekątnej, tłumacząc na mnożenie wektora przez macierz: dla każdego d bierzemy sumę wyrazów na indeksach takich, że d dzieli a_i, mnożymy przez -phi(d) i dodajemy wynik do tych samych indeksów w wynikowym wektorze a na koniec dla każdego indeksu dodajemy w wynikowym wektorze wejściową wartość na tym samym indeksie razy różnicę między tym co jest w macierzy na przekątnej a tym, co powinno być. Tu jest jeszcze jeden haczyk, jak napiszemy to tak jak powiedziałem, to jest n * maksymalna liczba dzielników, czyli trochę za wolno, trzeba najpierw pogrupować takie same wartości a_i i zostawić tylko sumę tych elementów wektora, odpalić całą tą procedurę i na koniec każdy wyraz zastąpić przez n kopii, to wyjdzie suma po *różnych* liczbach liczb ich dzielników, czyli zakres * log(zakres)

To teraz druga część mając macierz przez którą umiemy szybko mnożyć obliczyć jej wyznacznik, brzmi bardzo standardowo, więc się zdziwiłem, że nic nie mogłem na ten temat znaleźć (jak ktoś kojarzy jakieś źródło, które potencjalnie robi prościej to będę wdzięczny za linka), ja zrobiłem tak:
Najpierw wylosowałem dla każdego wiersza losową stałą i przełożyłem cały wiersz przez nią (tłumacząc na obliczanie przekształcenia najpierw pomnożyłem każdy element wektora przez odpowiadającą mu stałą) i na koniec otrzymany wyznacznik podzielę przez iloczyn tych stałych, zaraz się okaże dlaczego tak, następnie biorę dwa losowe wektory u, v i liczę u^T(A^k)v dla k od 0 do 2n+2 i wrzucam to w Masseya (https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm), to co Massey mi zwróci to najkrótszy możliwy ciąg a_i taki, że \sigma a_iu^T(A^k)v = 0, czyli u^T(\sigma a_iA^k)v = 0, u i v było losowe, więc praktycznie na pewno jest to po prostu minimalny ciąg taki, że \sigma a_iA^k = 0, czyli wielomian minimalny macierzy, teraz wielomian minimalny może się różnić od wielomianu charakterystycznego tylko jak macierz ma wielokrotne wartości własne, jako że wylosowałem te stałe dla wierszy, to raczej tak się nie stanie, więc wyznacznik to po prostu wyraz wolny*(-1)^{n-1}, jedyny wyjątek to jak macierz od razu miała rząd mniejszy o co najmniej 2 od liczby wierszy, wtedy przez co jej nie przemnożę, to nadal ma podwójną wartość własną 0, więc doifowałem, że jak Massey znajdzie krótszą rekurencję, to wypisuję 0 (inb4: wyznacznik liczy drzewa rozpinające, a wiemy że co najmniej jedno istnieje, tak, ale to nie znaczy, że reszta z dzielenia przez 10^9+7 też jest niezerowa, nie wiem, czy był na to test, ale podejrzewam, że da się taki ułożyć)

Jak chcemy jakoś udowodnić, że faktycznie nie będzie tych wielokrotnych wartości własnych, to żeby tak było, to wielomian charakterystyczny musi mieć pierwiastki wielokrotne, czyli musi mieć jakiś wspólny pierwiastek ze swoją pochodną (jak jesteśmy w ciele skończonym, gdzie nie ma pojęcia granicy dalej możemy zdefiniować pochodną wielomianu https://en.wikipedia.org/wiki/Formal_derivative i dalej ma ona własności typu (fg)'=f'g+fg' i z tego wyprowadzamy, że p^2 | f wtedy i tylko wtedy gdy p | f i p | f', czyli f i f' mają wspólny dzielnik), czyli ich https://en.wikipedia.org/wiki/Resultant jest równa 0, resultant to wielomian stopnia O(n^2) od tych współczynników dla wierszy, czyli jeśli tylko istnieją jakieś parametry (i to jest fragment który nie wiem jak zrobić) dla których jest niezerowa, to z lematu Schwartza-Zippela prawdopodobieństwo, że wyjdzie 0 jest co najwyżej O(n^2/p), czyli bardzo mało

I jeszcze na koniec jak n=1, to de facto liczymy wyznacznik macierzy 0x0, jakby chcieć go zdefiniować, to istotnie wyjdzie 1, ale coś w kodzie się wywala, ja tego nie doifowałem i tylko 9/10 ☹️

Ja tez dziekuje, swietnie sie bawilem

Zgadzam się z Kamilem co do tych uwag 1–5 (może tylko uważam, że 1B–3B były wystarczająco trudne jak na swoje sloty). Na fajności zadań się (standardowo) nie zawiodłem. Byłem w przeszłości i zawodnikiem, i współorganizatorem – i wciąż nie rozumiem, jak Mateusz potrafi wymyślać tyle zajefajnych zadań.

O dywizji C już mówili wszyscy (i podzielam opinie), ale dodam, że wg mnie Wieczór gier [5C] – nawet z dokładnie tymi samymi ograniczeniami na wejście/wyjście – byłby dobrym zadaniem na finał: względnie krótkie rozwiązanie, zdecydowanie nie wszyscy finaliści by zadanie wbili (sam nie wiem, czy bym je zrobił pod presją czasu). Rzucenie go w dywizji C to spora przesada. Zgadzam się też co do uwag do 2C, 3C i 4C (i tym, że 2B mogłoby dać radę jako 5C).

Wielu ludzi się ze mną może nie zgodzić, ale uważam, że parametric search (aka Aliens trick) w dywizji B (5B–podziały) jest sporym szaleństwem: ta metoda była podstawą rozwiązania najtrudniejszego zadania na IOI'16, a teraz coś jeszcze (imo) trochę trudniejszego jest w dywizji B.

W wymienionych zadaniach akurat nie zastanawiałem się nad przydatnością odsłonięć, a nad (nie)możliwością nadużycia systemu. W zadaniach Miny oraz Nawiasowanie bardziej bym się bał, że ktoś wepcha heurę.

Swoją drogą: odsłanianiem pojedynczych zadań organizatorzy mogą lepiej dopasywować trudność rund.

@Kacper Walentynowicz

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

Odniosłem wrażenie, że rolą zadania 2B było właśnie sprawdzić czy ktoś dostatecznie uważnie testuje swoje rozwiązania.

> Proponuję A - to całkiem smutne, że trzeba godzinami kminić hardkora i jeszcze można zzerować.

Moim zdaniem konkurs bardzo dużo by stracił na czymś takim. Brak odsłonięć w A to jest wręcz część zabawy. Poza tym testy z forum w pewnym sensie zmniejszają liczbę tych wyzerowań, i są według mnie złotym środkiem między pracą totalnie bez feedbacku z zewnątrz i pracą z odsłonięciami.



@Kamil Dębowski

> Przykładami dobrych na to zadań są Mędrcy (3A), Drybling Baj (3B)

Rozumiem chęć odsłaniania 3A (naprawde trudne do zweryfikowania czasowego i poprawnościowego, ale sam był bym mimo wszystko za brakiem odsłonięć), ale czemu 3B? Losowy maxtest z doklejonymi dwoma ciągami LLLL...LL i PPPP....PP chyba odsiewał wszystkie niepoprawne rozwy, a czas można sprawdzić na testrunie.