@Jan Klimczak ciekawostka:
Trzymałem dokładnie to ale na vectorach shortów, pamięciowo się mieściło, ale czasówki przekroczone (różne submity dostawały 5-7 punktów)

Jak już wiesz, że masz tylko poziome albo tylko pionowe pasy, to wiesz, że ruszanie się pionowo i poziomo jest niezależne - tj. jak masz przejść z (A,B) do (C,D), to albo od razu możesz przejść do (C,B) albo od razu do (A,D). Więc zadanie robi się jednowymiarowe.

To teraz chcemy wiedzieć, ile zajmie przejście w poziomie z A do C, jeśli zaczynamy w chwili T (modulo NWW). I tu liczymy logarytmiczne skoki - dla każdego T (od 0 do NWW-1), dla każdego i (od 0 do 20), dla każdego N (od 0 do maxN / 2**i) chcę wiedzieć, ile zajmie przejście z N * 2**i do (N+1) * 2**i jeśli zaczynam w T (mod NWW). Oblicza się całe D w czasie NWW * MAXN * 2, bo każdy skok długości 2**i rozbija się na dwa skoki długości 2**(i-1) (przy czym ten drugi zaczyna w czasie przesuniętym o czas wykonania pierwszego skoku). I teraz każde zapytanie rozbija się na max 2 logN skoków długości 2**i, czyli pojedyncze zapytanie obsługuję w logN.

Irytujące detale:
* D jest inne jeśli idę w przód, a inne, jeśli idę w tył, czyli muszę policzyć i to, i to (ja w sumie miałem cztery tablice: pion/poziom, przód/tył).
* Na początku trzeba policzyć dla każdej ulicy, czy da się przez nią przejść w danym czasie, co naiwnie jest N * M * NWW. Nie byłem pewien, czy to się zmieści, więc wszystko pozmieniałem na bitmaski, i mam na początku N * M * NWW / 64.

Czyli łączna złożoność: (N * M * NWW / 64 + max(N,M) * NWW + Q log N). Czasy dochodzą do 4.7 / 9.

Tak jak wspomniano wyżej, pierwsza obserwacja jest taka, że z danego punktu można przejść w dowolnym kierunku jeśli nie jest zablokowana cała ulica pionowa/pozioma.
Obserwacja nr2: Nie ma sytuacji w której ulica pionowa i ulica pozioma są zablokowane w tym samym momencie(na jakimś skrzyżowaniu wtedy świeciłyby się 4 czerwone światła), czyli w danym momencie plansza jest podzielona na pionowe/poziome paski w których możemy się swobodnie przemieszczać.
Obserwacja nr3: Układ świateł powtarza się co 840 (840 = NWW(1,2,3,4,5,6,7,8)), możemy więc wyznaczyć dla każdej ulicy czy jest zablokowana w każdym momencie modulo 840(czyli czy jest zablokowana jeśli czas % 840 wynosi 0, potem 1, 2...839) w czasie O(n*m*8 + (n+m)*840*8)

Przejdźmy do odpowiadania na zapytania. Jeśli w momencie początkowym zapytania nie jest zablokowana żadna ulica to od razu możemy się przemieścić. Jeśli zablokowane są ulice poziome, to na początku możemy się ustawić nad/pod punktem końcowym i teraz interesuje nas tylko przesuwanie się w górę/dół. Mamy teraz punkty postaci (x,t), czyli wysokość na jakiej się znajdujemy i czas % 840, dla każdego takiego punktu możemy wyznaczyć jak najdalej jest w stanie przemieścić się w górę/dół w trakcie trwającej minuty (jest w stanie się przemieścić dopóki nie napotka poziomej zablokowanej ulicy). Jesteśmy w stanie wyznaczyć to w czasie O((n+m)*840).
Żeby teraz odpowiedzieć na pytanie zastanawiamy się, ile razy musimy skoczyć za pomocą tej znalezionej wartości. Żeby nie musieć tego symulować możemy użyć triku z LCA, czyli wyznaczyć w jakim miejscu znajdziemy się po 1,2,4,8,... skokach i binsearchować dla każdego zapytania.
Złożoność na wygenerowanie tych skoków to jakieś O((n+m)*840 * log(n)), złożoność na zapytania to O(q*log(n)). Trzeba jeszcze uważać na pamięć, tablica tych skoków zajmuje jej całkiem sporo. Rozwiązaniem jest pogrupowanie zapytań według tego czy będziemy chcieli skakać w lewo/prawo/górę/dół i dla każdej grupy najpierw przygotować te wartości a potem odpowiadać, możemy wtedy cały czas korzystać z tych samych tablic i ilość pamięci spada czterokrotnie.

Ta obserwacja inaczej sformułowana to "spójne składowe w każdym momencie to albo poziome pasy albo pionowe pasy"

Druga kluczowa obserwacja to że w każdej iteracji bajtocję da się podzielić na X pasów poziomych lub pionowych (zależnie od konfiguracji), gdzie wszystkie place w obrębie pasa są dostępne. Być może X=1 i wtedy każda podróż odbędzie się w czasie 0.

Mi zabrakło pomysłu, jak obejść długie ciągi tego samego typu (tylko pionowe, tylko poziome). Bo jak tylko pasy zmienią kierunek, to od razu można dojść do punktu docelowego.
Więc miałem bruteforce gdzie wyliczyłem wszystkie pasy - liczba iteracji to NWW(długość iteracji każdego skrzyżowania) - i symulowałem każde przejście dla czasu modulo NWW. Rozwiązanie takie dało 3/10.

Kluczowa obserwacja: przez ulicę można przejść bezpośrednio na drugą stronę, z wyjątkiem sytuacji, gdy wszystkie światła przez tą ulicę są czerwone.

To jak się robi to zadanie? Miałem różne obserwacje ale żadna specjalnie mi nie pomogła z faktem że jest milion różnych zapytań :P

Według harmonogramu koniec jest o 23:59, według zegarka na sio o 0:00.

To jest ważne dla tych, którzy planują w końcówce zawalczyć!

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

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)

Potwierdzam

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

Off top: pytanie do autora 'Adrian Mol': po nicku wnioskuję datę urodzenia na przedział 1971-1979... Możesz potwierdzić/zaprzeczyć?

+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

nk