Pewnie ktoś chciałby się dowiedzieć, więc napiszę. Słowa klucz to "liniowa reprezentacja gammoidu" xd.
Tzn. robimy coś takiego. Bierzemy sobie liczbę pierwszą P i dla każdej krawędzi losujemy liczbę od 1 do P-1. Następnie dla każdego wierzchołka v i dla każdego źródła 1<=z<=k wyznaczamy sumę iloczynów wartości na krawędziach po wszystkich ścieżkach od z do v (łatwo policzyć dynamikiem po DAGu). Dla każdego v otrzymujemy zatem wektor długości k (tzn te k wartości dla kolejnych źródeł). Kluczowe stwierdzenie jest takie, że przepływ wierzchołkowy ze źródeł do zbioru wierzchołków to rząd macierzy wektorów odpowiadających wierzchołkom z tego zbioru (łatwo się o tym przekonać w jedną stronę, bo jak istnieje małe cięcie wierzchołkowe, to łatwo widać, że ten rząd nie może być większy niż to cięcie, a w drugą nie wiem, ale są papery co tak twierdzą).
No to to jest klucz zadania, a zabawy z wektorami opisywać nie będę, bo obstawiam, że to ta pierwsza część zadania była bardziej zaporowa :P. Udało mi się osiągnąć O(mk+nk^3), ale to balansuje na granicy TL (wcześniej miałem O(mk+nk^2 log n + nk^3), ale na szczęście część z nk^2 log n udało mi się przyspieszyć do nk^2)

Wojtek, wyszukałeś w internecie, znałeś, sam wymyśliłeś, czy coś brałeś i Ci się przyśniły te gammoidy?

Jakbyś był "patriotą" i został w kraju i poszedł na UW, a tam na ćwiczenia z algorytmów parametryzowanych, które prowadzę co 2 lata, to może byś usłyszał o gammoidach :P... O gammoidach w istocie słyszałem i wiedziałem, że są liniowo reprezentowalne (aczkolwiek czym jest owa reprezentacja, to musiałem googlać), ale nigdy w życiu bym się nie spodziewał, że to się może jakkolwiek przydać na contestach.

Czymś pewnie istotnie bardziej znanym będzie tzw. matroid transwersalny. Bez nazywania go po imieniu to tak naprawdę już dla jajec klepałem go na preOIu w liceum. Tzn. klasyczne zadanie o największym skojarzeniu w grafie dwudzielnym. Zamiast je robić ścieżkami powiększającymi, to można każdą jedynkę w macierzy sąsiedztwa zastąpić przez losową liczbę mod P i policzyć rząd tej macierzy, który będzie właśnie rozmiarem owego skojarzenia. Pewnie jest to coś, o czym sporo osób tutaj słyszało/było tego świadomym, a to jest tak naprawdę szczególny przypadek tego gammoidu i jego liniowej reprezentacji.

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?

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?

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.

@Marek Dzięki, n^2 k / p < 3e-7 dla p=2^61-1 ma sens! (a w n^2 / p już nie wnikam).

Obaj napisaliście "w praktyce", ja to rozumiem jako "dla słabych testów", więc mam nadzieję, że ktoś takie coś ubije w przyszłości :)

Jeśli p również jest losowe to może być ciężej ubić, chociaż nie jestem pewny.