Ja miałem prawie tak samo z dokładnością do:
Jak mam potwierdzoną ścieżkę V0 - V1 - ... - Vm i chcę ją skrócić, to biorę jakiś jej prefix długości k i pytam o: V0, V1, ... Vk, Vm. Jak dostałem true, to skracam ścieżkę do V0, V1, ... Vk, Vm, jak false to do V0, V{k+1}, V{k+2}, ... Vm. Na początku dzieliłem na pół jak to w binsearchu, ale potem sprawdziłem doświadczalnie, że lepiej się sprawdza wzięcie trochę dłuższego prefixu, około 0.8 * długość całej ścieżki.
Dopisałem jeszcze takie dwa opty: jak się zgubiłem, to sortuję wszystkie wierzchołki, na których nie wywołałem MoveProbe od ostatniego potwierdzonego ruchu rosnąco po długości potwierdzonej sekwencji, a te które jeszcze nie mają przypisanej sekwencji daję na sam koniec i wywołuję się na nich w tej kolejności.
Jak szukam pierwszej potwierdzonej sekwencji, to wybieram losową permutację wszystkich wierzchołków, generuję jej wszystkie przesunięcia cykliczne, przeglądam je w losowej kolejności i iteruję się po wszystkich wierzchołkach w takiej kolejniści jak w danym przesunięciu cyklicznym

Z tymi wszystkimi optami najgorszy wynik z paczek 4-10 to 401151 zapytań na 10j (mniej niż moje rozwiązanie do subtaska 3, które najwięcej wykonało 551188 zapytań)

Ja moge dodać jeszcze, że w tym zadaniu symetria jest wygodna w implementacji - jeśli mamy obsługę górnej trasy dla nowej wartowni (R, C) to obsługę dolnej/lewej trasy można zaimplementować jako obsłużenie punktu (C, R).

Yeah, no need to use something like an order statistic tree to count the number of paths whose sum is more than something.

We can do the centroid decomposition at first, and sort these O(n log n) values in advance before the binary search, thus we can just use two-pointers in each check.

To find something to do the binary search, we can note that the answer is always "pool[i]+pool[j]"(1<=i<=j<=cnt), where cnt=O(n log n). Assume we now have "answer in (l,r)", we can do a two-pointers to find the number of pairs (i,j) such that l<pool[i]+pool[j]<r. If this number is not large, for example not more than 2e5, we can generate these pairs, sort them, and then run a binary search on them. Otherwise, we can just select a random pair, it won't increase the times of check too much.

Także w swoim imieniu bardzo dziękuję wszystkim zaangażowanym w Potyczki 2019. To jeszcze nie koniec, przed nami wielki finał. Potyczki to praca zespołowa, ale szczególnie chciałbym podziękować Mateuszowi, który wziął na siebie koordynację merytoryczną. Dobra robota.

KD

> A wiecie, że dopełnienie kuli też jest kulą? Ktoś widzi, co to ułatwia w zadaniu?

Też to zauważyłem, a nawet to że suma kul jest dopełnieniem przecięcia dopełnień (można było liczyć przecięcie zamiast sumy).

Osobiście próbowałem podejść do rozwiązania od "środka", tzn. od punktu który leży na najkrótszych drogach pomiędzy wszystkimi trzema kulami. Każdy układ można było sprowadzić do 7 liczb: liczba wymiarów, 3 promienie i 3 odległości od środka. Ale zadania nie rozwiązałem.

Można też mieć std::map z wierzchołkami trasy zamiast drzewa przedziałowego. Ale iterowanie po sąsiednich elementach mapy przy modyfikacjach bywa dość bugogenne ;)

Trudność zadań jak dla mnie optymalna - to właśnie lubię w potyczkach, że jest dużo czasu i trudne zadanka, a nie na odwrót, jak na tych serwisach zadankowych.

Najbardziej brakowało mi rundy rozproszonej albo innych tego typu freakowych i oryginalnych rzeczy.

Najciekawsze zadanko jak dla mnie to Sonda!

@Michał
Ja tak samo nawet nazwałem u siebie A,B,C i D - ale nie preprocesuję sum na trójkątach, tylko tak:
Też iteruję dla każdego `c` i `d`, ale potem jak zostaje mi `a` i `b` do ustalenia, to pierwsze 2 kule mają na tych pozostałych bitach te same wartości, czyli problem (dla już ustalonego `c` i `d`, wewnątrz pojedynczej iteracji) redukuje nam się do przecięcia już tylko 2 kul w mniejszej przestrzeni A+B wymiarowej. W każdej iteracji jak ustalimy `c` i `d`, to oddalają one nas od wejściowych 3 kul o pewną odległość, więc te kule ze zredukowanego problemu musimy rozwiązać dla mniejszych promieni (pomniejszonych o te odległości, które już przebyliśmy). No i w każdej iteracji będą nam się zmieniały tylko promienie tych pozostałych 2 kul, więc dla każdej możliwej pary promieni mamy spreprocessowany wynik.

Prawie to samo, ale jakoś cieplej człowiek myśli o kulach niż o układzie nierówności.

@Kamil
wow, faktycznie, a ja też zasadę włączeń i wyłączeń robiłem :D

Moje rozwiązanie: Utrzymujemy "najbardziej górną" i "najbardziej dolną" możliwą trasę między osadami. Nowa warownia będzie wyburzona wtw. gdy leży na obu z nich.

Dla ustalenia uwagi, skupmy się na "najbardziej górnej" trasie. Możemy ją trzymać na drzewie przedziałowym, dla każdej kolumny trzymając maksymalny wiersz przez który przebiega trasa w tej kolumnie. Trzymamy również wszystkie warownie, które leżą pod trasą, bo być może później będą musiały być ominięte.

Kiedy dochodzi nowa warownia (R,C) przecinająca trasę, jej aktualizacja wymaga obniżenia trasy do poziomu co najmniej (R+1) na odcinku [C-1,M]. Jeśli istniały jakieś warownie na odcinku (0,C-1) - (R+1,C-1) lub (R+1,C-1) - (R+1,M), które wcześniej były pod trasą, to je też musimy ominąć (i jednocześnie wyrzucić z listy warowni pod trasą, żeby rozpatrzeć je co najwyżej raz).

W przyszłym tygodniu.

Jak to zrobić na 10 punktów?

Ja miałem tylko pomysł na 5 punktów, żeby bezpośrednio zapamiętywać, z których obszarów da się dojść o obu osad--nazwijmy te obszary "dobrymi"--i dla każdej odległości od pierwszej osady, ile jest dobrych obszarów w tej odległości od niej. Wtedy niszczymy warownię wtedy i tylko wtedy, kiedy jest byłaby ona na jedynym dobrym obszarze o tej odległości od pierwszej osady.

Jeśli nie burzymy warowni, możemy aktualizować złe obszary DFS-em takim, że jeśli zaznaczamy jako zły obszar o pozycji (i, j), to jeśli obszar na prawo do góry, czyli (i - 1, j + 1) jest zły, to zaznaczamy jako złe obszary (i - 1, j) i (i, j + 1), jeśli jeszcze nie były zaznaczone jako złe oraz analogicznie jeśli obszar czyli (i + 1, j - 1) jest zły, to zaznaczamy jako złe obszary (i + 1, j) i (i, j - 1), jeśli jeszcze nie były zaznaczone jako złe.

I had a similar idea, that I am now trying to finish debugging, but in O(n log^4 n) because don't you need to use something like an order statistic tree to count the number of paths whose sum is more than something?

And how do you find the "something" to do the binary search? Do you take it to be the length of a random path in the search interval, like I am going to?

Also, I am going to use small-to-large instead of centroid decomposition but this doesn't change the complexity.

Jeśli ktoś jest zainteresowany - poniżej moje rozwiązanie z zastrzeżeniem, że nie mam pełnego dowodu na to, że zawsze mieści się w limicie operacji (aczkolwiek max na testach to ~530K). Losuję kolejność przeglądania wierzchołków żeby nieco zabezpieczyć się przed złośliwymi testami.

Rozwiązanie składa się z dwóch części. W pierwszej staramy znaleźć się w takim wierzchołku, że:
(A) Wiemy na 100% że do niego weszliśmy, pomimo że
(B) wierzchołek nie został potwierdzony (jest to "nieparzysty sukces"), oraz
(C) wierzchołek ma co najmniej 2 sąsiadów.
Jedyny przypadek, kiedy jest to niemożliwe, to gwiazda z centrum w wierzchołku 1 - taką sytuację jesteśmy w stanie wykryć i obsłużyć.

Robimy to szukając jak najkrótszych "potwierdzonych sekwencji" (tzn. od pozytywnej do pozytywnej odpowiedzi sondy) między różnymi wierzchołkami. Będąc w danym "potwierdzonym" wierzchołku, mamy 3 możliwości:
[1] Jesteśmy w danym wierzchołku po raz pierwszy. Chcemy znaleźć dowolną "potwierdzoną sekwencję" do innego wierzchołka. Możemy to zrobić próbując każdego potencjalnego sąsiada i próbować przejść z niego do każdego z pozostałych N-2 wierzchołków. Niepowodzenie oznacza gwiazdę.
[2] Znamy już "potwierdzoną sekwencję" z naszego wierzchołka. Próbujemy ją skrócić - jeśli poprzednio było to V(1) - W1(0) - W2(0) - ... - Wn(0) - Z(1), to teraz próbujemy V1(1) - W2 - ... -Wn - Z. Jeśli po drodze dostaliśmy odpowiedź pozytywną, to mamy krótszą sekwencję. Jeśli dotarliśmy do końca bez potwierdzenia, to znaczy że V - W1 - Z jest istniejącą ścieżką, a więc idealną "potwierdzoną sekwencją". Zgubiliśmy się, więc szukamy jakiegokolwiek potwierdzonego wierzchołka.
[3] Znamy "potwierdzoną sekwencję" długości 2 - przechodzimy do środkowego wierzchołka tej sekwencji. Spełnia on kryteria (A)-(C).

Druga część rozwiązania to już wyznaczanie drzewa rozpinającego grafu, rozpoczynając od wierzchołka R spełniającego kryteria (A)-(C).
[1] Będąc w niepotwierdzonym wierzchołku, bardzo łatwo możemy wyznaczyć listę sąsiadów
[2] Dla każdego sąsiada N1 wierzchołka R chcemy wyznaczyć również jego listę sąsiadów. Robimy to przy pomocy dodatkowego sąsiada R - N2.
(a) Jeśli sekwencja R(0)->N1(1)->N2(0)->R(?) zakończy się potwierdzeniem, to znaczy że N1-N2-R stanowią trójkąt. R jest obecnie potwierdzony, więc możemy przejść do każdego z jego sąsiadów jako niepotwerdzonego i wywołać przeszukiwanie rekurencyjnie.
(b) Wpp. między N1 a N2 nie ma krawędzi. Żeby przetestować istnienie krawędzi N1-V, wykonujemy sekwencję N1(1)->V(0)->N2(?). Jeśli mamy potwierdzenie dla N2, to istnieją krawędzie N1-V-N2. Jeśli nie, to przedłużamy: N1(1)->V(0)->N2(0)->R(0)->N2(?). Ostatni ruch wykonaliśmy z V lub R. W zależności od tego, czy się powiódł, wiemy w którym z nich byliśmy i czy krawędź N1-V istnieje.
[3] Mając teraz sąsiadów sąsiadów R, możemy do nich wejść jako niepotwierdzonych i wykonać przeszukanie rekurencyjnie.

My solution is O(n log^3 n) and got 10.

Using binary search, we need to count the number of paths whose sum is no more than something, which can be done using centroid decomposition and two-pointers.

To handle the huge number, we can use persistent segment tree storing hash on each node to compare two huge numbers in O(log n) time.

Ja każdemu obszarowi przyporządkowuję ciąg 0-1 tak, że każda liczba odpowiada jednemu prostokątowi, a długość ciągu to liczba prostokątów. Zamiatamy i zamieniamy 0 na 1 i na odwrót gdy przechodzimy przez bok prostokąta. Teraz nad tym ciągiem utrzymuję drzewo hashy i danemu obszarowi przyporządkowuję hash z korzenia.