nk

+1, ale ja się po drodze pochwalę moim kwadratem bo był śmieszny i z całkiem małą stałą (chyba, zobaczymy po wynikach xD)

Zauważmy, że pesymistycznie z każdej areny zawsze będziemy dostawać tę samą przepustkę.
Czyli szukamy takich par, że da się przejść niezależnie którą przepustkę będziemy dostawać zawsze z każdej areny.

Możemy sobie to rozpisać w logice pierwszego rzęd:

((v1 => w1 | v1 => w2 ...) & (...) ...) => (A => B))

Gdzie zmienne odpowiadają wierzchołkom, i jeśli w jakimś ustawieniu zmiennych W=true, to znaczy że "mamy przepustkę do W"

Po lewej dużej implikacji jest opis prefiksu grafu (krawędzie wychodzące dla pierwszych K wierzchołków, dla V1 wiemy że zachodzi V1=>W1, lub V1=>w2 ...)

Po prawej jest stwiedzenie: "Jeśli mamy przepustkę do A to możemy dostać przepustkę do B"

Czyli sumarycznie z opisy grafu ma wynikać że "Jeśli mamy przepustkę do A to możemy dostać przepustkę do B", niezależnie od wyboru krawędzi

Zatem para (A, B) działa, jeśli ta formuła jest tautologią, czyli jej negacja jest niespełnialna. Jak pobawimy się tą formułą to okazuje się,
że można przekształcić do takiej formy (możliwe że po drodze jeszcze negowałem wszystkie zmienne, nie pamiętam):

(v1 | !w1 | !w2 | ...) & (...) & ... & !A & B

Która jest w formie Horna, a Horn-Sat jest P-Complete i liniowy.

Jak popatrzymy na algos do robienia Horn-Sata oraz to, jaki dokłądnie jest nasz przykład, to okazuje się, że jeśli ustalimy B, to możemy wierzchołki (dodatkowe Horn-clauses) dodawać w amortyzowanym czasie stałym, i po każdym dodaniu mamy za darmo liczbę działających wartości dla A.

Zatem dla każdego B leci liniowo, sumarycznie kwadrat

Żeby dało się dojść do jakiejś areny X, musi być inna arena Y, z której krawędzie prowadzą *tylko* do X. Bo jeśli nie, to potwory mogą zawsze omiajać X.

Jeśli znajdziemy taką arenę Y, to łączymy sobie strzałką Y->X.

Teraz tak samo, żeby dało się dojść do drzewa Y->X, musi być inna arena, z której krawędzie prowadzą *tylko* do X albo Y. Jeśli znajdziemy taką, to łączymy strzałką do najniższego wspólnego przodka wierzchołków docelowych.

Dla każdego drzewa pamiętam zbiór innych drzew, do których prowadzi korzeń. Jeśli zrobi się z tego zbiór jednoelementowy, to łączymy drzewa.

Dla każdego drzewa też pamiętam zbiór krawędzi wchodzących do naszego drzewa. Gdy łączymy drzewa, to musimy łączyć te zbiory. Połączone drzewo przejmuje identyfikator tego drzewa, do którego prowadzi więcej krawędzi. Muszę poprawić wszystkie krawędzie z mniejszego zbioru.

W każdym wierzchołku pamiętam skoki o 1, 2, 4, 8, ... kroków w górę drzewa (potrzebne do najniższego przodka) ale liczę to leniwie, tylko jak jest potrzebne. Dzięki temu nie muszę tego poprawiać przy łączeniu drzew.

Może pojawić się cykl w korzeniu drzewa, łączymy taki cykl w jeden super-korzeń. Gdy powstaje cykl, przebudowuję całe drzewo przechodząc przez wszystkie wierzchołki. To się zdarzy tylko raz dla każdego wierzchołka.

Wydaje mi się, że mam N log^2 N, ale to jakaś jazda była.

Więc tak. Mamy graf, i chcemy zliczać pary (A,B) takie, że każda ścieżka wypuszczona z A zawsze trafi do B. Oznaczymy to R(A,B).

Zauważmy, że jeśli R(A,B) i R(A,C) to albo R(B,C), albo R(C,B) - bo jeśli z B da się chodzić nie trafiając do C, a z C da się chodzić nie trafiając do B, to mogę pójść z A jakkolwiek, trafić do któregoś z nich, i potem już nie trafić do tego drugiego.

Wobec tego mamy drugi graf, skierowany, gdzie mam krawędź z A do B jeśli R(A,B). Dodatkowo, można zdefiniować S(A), czyli pierwszy wymuszony wierzchołek na wszystkich ścieżkach z A, i jeśli R(A,C), to albo C = S(A), albo R(S(A), C). Będziemy starali się utrzymywać graf zdefiniowany przez S. Ten graf jest prawie lasem, tylko jeszcze czasem z korzenia jakiegoś drzewa wychodzi krawędź gdzieś z powrotem do tego drzewa. R jest po prostu domknięciem przechodnim S.

Teraz zastanówmy się, kiedy pojawia się krawędź S(A) z jakiegoś wierzchołka A, jeśli mamy moc K (czyli wygrywamy na arenach K i mniejszych, co jest równoważne temu, że usuwamy z pierwotnego grafu wszystkie krawędzie dotykające jakiegokolwiek wierzchołka dalszego niż K). Więc dzieje się to, jeśli wszystkie krawędzie wychodzące z A trafiają do tej samej spójnej składowej drugiego grafu (tego zdefiniowanego przez S) (to jest spełnione w szczególności, jeśli wychodzi tylko jedna krawędź).

Wpierw dla uproszczenia załóżmy, że graf zdefiniowany przez S nie ma cykli. Będziemy przerabiali areny od najsłabszej, zliczali wynik, i aktualizowali graf S. Robimy tak:
- dla każdego wierzchołka pamiętamy czy ma już zdefiniowaną krawędź S.
- pamiętamy też jego spójną składową (na spójnych składowych będziemy robić find-union, i pamiętać korzeń drzewa, które jest tą spójną składową).
- będziemy musieli liczyć LCA na grafie S, oraz liczyć głębokość wierzchołka na grafie S, więc trzymamy dla każdego wierzchołka wierzchołki przesunięte o 1, 2, 4, 8, etc. Będziemy je wyliczali leniwie, żeby nie musieć aktualizować wszystkiego przy łączeniu składowych. Dla każdego wierzchołka w każdej chwili mam wyliczony jakiś prefix, aktualizacje leniwe robią się (wydaje mi się, że to amortyzuje się do stałej na pytanie, ale być może do log(N).

Teraz jak łączmy dwie składowe, dołączając A do B, to do wyniku dodaję rozmiar A razy "liczbę wierzchołków na ścieżce z miejsca, gdzie dołączyłem do B, do korzenia B". To drugie wyliczam w log N; to pierwsze jest łatwe.

OK, a skąd wiem, kiedy łączyć składowe? Dla każdego wierzchołka (będącego korzeniem składowej, inne nie są interesujące) pamiętam dwie wybrane krawędzie idące do różnych składowych. Jeśli te dwie składowe kiedyś się połączą, to będę przeglądał kolejne krawędzie w poszukiwaniu dwóch prowadzących do różnych składowych. Jeśli się nie uda (albo od początku mam tylko jedną krawędź), to wszystkie krawędzie prowadzą do jednej składowej. Liczę LCA końców tych wszystkich krawędzi, dostaję wierzchołek X, w który trafiam. Teraz albo ten wierzchołek X to arena, do której już mogę pójść - wtedy łączę składowe - albo jeszcze nie - wtedy zapamiętuję korzeń tej składowej w X, i połączę te składowe kiedy dojdę do przetwarzania areny X.

OK, a skąd wiem, kiedy składowe się łączą? Dla każdej składowej A pamiętam zbiór korzeni, dla których jedna z dwóch wybranych krawędzi pokazuje na A. Teraz jak łączę dwie składowe, A i B, to łączę ich zbiory, przy czym dodaję mniejszy do większego. Jeśli przy dodawaniu zobaczę, że jakiś wierzchołek był w obu, to właśnie jego dwie składowe się połączyły. Dzięki temu, że łączę mniejszy do większego, to wciąż jest logarytmiczne.

Dobra, to na koniec cykle. Cykl wygląda tak, że w pewnym momencie korzeń X składowej A ma S prowadzące do swojej własnej składowej. To się robi trikowe, bo powoduje, że wartość, którą trzeba dodać jak inną składową B dołączam do A jest trudna do policzenia dynamicznie. Fortunnie, dany wierzchołek pojawia się w składowej z cyklem tylko raz. Więc po prostu dla każdej składowej pamiętam jej skład, łaczę znowu mniejszy do większego, i jak pojawi się cykl, albo jak dołączam się do składowej, która ma cykl, to po prostu przeliczam dla każdego wierzchołka w składowej ile będzie trzeba dodać. Fortunnie to już nigdy się nie zmieni (bo z korzenia mojej składowej już nie wyjdzie żadna więcej krawędź).


(ten opis jest dość skrótowy, i pomija jakieś badziewia w implementacji, ale zawiera kluczowe pomysły)

(to co ma Tomek i to, co mam ja, wygląda bardzo podobnie).