Mój kod, który failuje testy Arka z L <=1000 na średnio co 230 teście dostał 10 XD.

5/10 za qn z grupowaniem. +1 do tego, co mówi Anadi - po co tak duże limity czasu? (osobiście nie narzekam, no ale wciąż...)

tl;dr Tak, myślę, że znajomość algorytmów pomogła mi znaleźć lepszą pracę

To ja jeszcze może się wypowiem z perspektywy stażu/"new grad hire". Praktycznie każda moja rozmowa do większych firm na pozycje software developer w większości opierała się na rozwiązywaniu problemów algorytmicznych (prostszych bądź trudniejszych). Oczywiście podczas rozmowy o pracę implementacja rozwiązania nie jest jedynym czynnikiem i można zostać odrzuconym pomimo napisania FFT w 30 min.

Gdy zatrudnia się ludzi z doświadczeniem to można się pytać o znajomość frameworków i poprzednie projekty, jednakże do sprawdzania studentów bez doświadczenia algorytmy świetnie się sprawdzają. Nie chcesz odrzucić zdolnego studenta tylko dlatego, że jeszcze nie programował w dziedzinie którą się zajmujesz. Również szkolenie nowego pracownika w dużej firmie jest porównywalnie mniej kosztowne niż w małej firmie, więc chętniej zatrudniają ludzi bez doświadczenia w konkretnej technologii.

> Ile wynosi prawdopodobieństwo porażki tego algorytmu?

Oczywiście błąd może być tylko jednostronny: jeśli wyznacznik nad pierścieniem wielomianów jest zerowy, to po zewaluowaniu go wciąż będzie zerowy.

Wielomiany w każdej komórce macierzy są stopnia <n (bo stopień wielomianu w danej komórce macierzy to dokładnie długość najdłuższej ścieżki od wskazanego źródłą do wskazanego ujścia). Ponieważ macierz jest kxk, to wyznacznik macierzy ma stopień <nk. A można nawet wykazać, że stopień wielomianu-wyznacznika jest <n, przywalając np. lematem Lindströma-Gessela-Viennota (ale to już trochę off-topic). Tak więc szansa, że jeden wyznacznik, który nad pierścieniem wielomianów był niezerowy, wyjdzie nad Z_p zerowy, jest szacowana przez Schwartza-Zippela przez <nk/p (lub nawet <n/p). Są miniproblemy techniczne w stylu "co, jak rząd badanej macierzy jest <k?", ale łatwo sobie z nimi poradzić.

Liczba badanych macierzy jest równa n. W praktyce o algorytmie wzorcowym można bowiem myśleć tak: startujemy z każdego wektora o indeksie r \in \{k+1, ..., n\} i znajdujemy zachłannie bazę Z_p^k złożoną z dosuniętych możliwie na prawo wektorów \{v_{k+1}, v_{k + 2}, ..., v_r\}. Chcemy zagwarantować, że nasz algorytm randomizowany znajdzie każdą z n-k takich baz poprawnie. To znaczy: optymalna zachłanna baza nad pierścieniem wielomianów jest taka sama, jak w Z_p. W tym celu uruchamiamy powyższy argument n-k razy i szacujemy ostateczne prawdopodobieństwo błędu za pomocą union bounda. Otrzymujemy szacowanie <n^2k/p (lub <n^2/p). Ponieważ n^2 ~ 10^10, zaś p ~ 10^18, prawdopodobieństwo porażki jest bardzo małe.

A argument Wojtka heurystycznie ma sens z grubsza z tego samego powodu, dla którego haszowanie słów mod 1e9+7 "działa": jeśli porównujemy w słowie długości n parę podsłów, to Schwartz-Zippel dostarcza nam oszacowanie na prawdopodobieństwo porażki jedynie rzędu n/p (co dla n ~ 10^6 i ok. 10^6 porównań jest zdecydowanie niewystarczające). Ale zawodnicy zazwyczaj zakładają, że szansa na porażkę jest rzędu 1/p -- takie, jakie zachodziłoby dla haszów w pełni losowych -- i w praktyce zazwyczaj tak właśnie jest. Zdaje się, że tutaj zachodzi podobny efekt.

Trochę nie rozumiem w takim razie, czemu limit czasu nie był rzędu 15-20 sekund. Z tego co się orientuję, to rozwiązania pierwiastkowe działały rzędu ~8-12 sekund, więc to by dobrze odcięło bruty od wzorcówek.

Ja jednak tylko 5.

10/10 za O(qn)

Ile pkt macie za O(qn)? Ja mam 5pkt za wersje bez żadnych optymalizacji, jedynie z grupowaniem po początku.

Papery mówią, że trzeba mieć ciało rozmiaru co najmniej 2^k, aczkolwiek w sumie to nie zagłębiałem się w sumie co to tak naprawdę znaczy i jak się to ma w kontekście prawdopodobieństwa błędu. Ja na początku używałem liczby pierwszej rzędu 2^62, ale ze względu na szybkość działania przerzuciłem się na 1e9+7 (które jest w szczególności mniejsze niż 2^50), nie wpadłem na trik z 2^61-1. Mnożenie modulo wykonywałem początkowo dla tej dużej liczby pierwszej na int128 i ta podmianka zbiła mi czas wykonania kilkudziesięciokrotnie... Nie spodziewałem się tak ogromnej różnicy. Ale dla 1e9+7 byłem trochę zamartwiony tym pstwem kolizji i w ramach przetestowania tego empirycznie zapuściłem sobie porównywanie outów dla 1e9+7 z outami dla 1e9+9 i na około 100 losowych maxtestach się wszystko zgodziło, więc w praktyce chyba nie jest duże to pstwo, a od strony teoretycznej aż tak się nim nie przejąłem. Aczkolwiek jak dostanę jakieś jedno WA to się _aż tak_ nie zdziwię.

Ile wynosi prawdopodobieństwo porażki tego algorytmu?

Te wielomiany wydają się wysokiego stopnia, a już szczególnie jeśli mowa o wyznacznikach macierzy czy coś, a lemat Schwartza-Zippela mówi o prawdopodobieństwie (stopień wielomianu / P). A jeszcze trzeba to przemnożyć przez liczbę tych macierzy, czyli n albo n*k?

Czy oby na pewno p = 2^61-1 wystarcza, jak sugeruje omówienie?

Również dziękuję za organizację konkursu, zadania świetnie dobrane. Ale chciałbym jeszcze dorzucić jedną rzecz do podziękowań, a mianowicie książeczka z szkicami, za to mam ochotę podziękować raz jeszcze, napisanie takiej książeczki to dodatkowy wysiłek, a przecież i tak już sporo włożono w organizację konkursu.

Ja jakoś w żadnym momencie myślenia nad tym zadaniem nie ustalałem liczby wierzchołków. Wydało mi się, że rozmiar independent setu nie jest tutaj czymś specjalnym, i to przejście z drzew nieukorzenionych na ukorzenione zadziałałoby gdyby to co nas interesuje w drzewach było dowolną funkcją f(T) (o ile umiemy przeliczać f po doczepieniu rootowi dodatkowego poddrzewa, co jest prawdą zarówno gdy f = liczba wierzchołków, jak i gdy f jest takie jak tutaj). Ale może to nie jest prawda?

Też się świetnie bawiłem rozwiązując zadania – były bardzo ciekawe i na wysokim poziomie. Przygotowanie takich zawodów to dużo pracy (włącznie z cudowną niespodzianką) i serdecznie dziękuję organizatorom za ten włożony wysiłek.

@Franciszek dzięki wielkie, faktycznie... a ja mergowałem przedziały jak w drzewku przedziałowym w O((n+q)*k^2 * log(n))...

"W zadaniu 4b za trochę większą stałą traciło się 2-4 punkty." - well, jak się miało złą złożoność i jakieś jumppointery, jak chyba praktycznie wszyscy co na forum opisywali, to nie takie dziwne, że można było stracić punkty xd No i też nie zapominajmy, że nazywanie zależności od ósemki stałą nie jest do końca w porządku. Aczkolwiek nie wiem co dokładnie miałeś na myśli.

Moim zdaniem w hipotetycznie dobrze przygotowanym opracowaniu tego zadania na hipotetycznej sensownej sprawdzarce bruty do niego nie powinny wchodzić na więcej niż jakieś 2 punkty. Ale jest spora gama rozwiązań pośrednich (jakieś n^5/3, n^3/2 log n), więc rozumiem, że można chcieć jednak trochę stopniować stopień skomplikowania testów i nie mieć maxtestów już od trzeciej paczki. Ale przy istnieniu rozwiązania n^3/2 moim zdaniem TL powinny być bardziej brutalne, 42s to za duży zapas. Niestety wierzę Tomkowi i spodziewam się, że jednak było to możliwe wcisnąć bruta na 10/10. Na Codeforces nawet cyrkuluje znane meme ze mną w roli głównej, gdzie wyśmiewam autorów zadań, których wzo to n^3/2 log n, a potem się dziwią, że 100% wbitych rozwiązań to bruty n^2, a orgowie raczej chyba myślą podobnie jak ja w tej kwestii, więc się spodziewałem, że wzo powinna być co najwyżej n * sqrt(n log n). Ale te 42 sekundy zastanawiały...