Jak się robi to zadanie?

Ja robię na początku centroid decomposition, i zapamiętuję całą tą "strukturę" - w szczególności każdy wierzchołek wie do jakich centroidów "przynależył" na poszczególnych poziomach. Do danego centroidu na danym poziomie przynależyły jakieś wierzchołki, to obchodzę te wierzchołki, zapisuję w porządku preorder, i robię nad tym drzewo przedziałowe. W tym drzewie trzymam zysk z wierzchołka minus koszt ścieżki do roota (czyli tego ustalonego centroidu). Mając to można odpowiadać na zapytanie i robić update w O(log^2 n).

Ja tak niewinnie odpowiem bo nie udało mi się zaimplementować do końca, ale planowałem tak:
- heavy-light decomposition drzewa
- każda ścieżka hld zawiera dwa drzewa przedział-przedział, z których odczytujemy "gdzie na przedziale a..b jest najlepszy wynik w poddrzewie" - dwa, bo jedno jest do chodzenia w dół ścieżki i uwzględnia sumy prefiksowe kosztów krawędzi, a drugie na odwrót...
- liściami tych drzew są kolejki priorytetowe "gdzie w a jest najlepszy wynik w poddrzewie"
również O(n logn^2)

Mam złożoność czasową O(n * log(n) + q * log^2(n)) i pamięciową O(n * log(n)).

Rozbijamy drzewo centroidami. Każdy wierzchołek wystąpi w co najwyżej log(n) rozbiciach, tzn. w log(n) coraz mniejszych drzewach. W każdym takim drzewie wartością wierzchołka nazywamy jego cenę bananów pomniejszoną o koszt dojścia do niego z korzenia (korzeniem jest centroid obecnie rozważanego drzewa). Czyli wartość wierzchołka mówi jak fajny jest dany wierzchołek, gdyby poprzedniego dnia Bajtazar był w korzeniu. W każdym drzewie spamiętujemy preordery, by być w stanie zbudować strukturę danych odpowiadającą na zapytania:
1) znajdź w poddrzewie wierzchołek z najmniejszą wartością
2) zmień wartość wierzchołka - będzie potrzebne do zapytań z wejścia "zmień cenę bananów w wierzchołku"
3) dodaj wartość do wszystkich wierzchołków poddrzewa - będzie potrzebne do zapytań z wejścia "zmień koszt drogi", bo wtedy zmienia się wartość (czyli koszt idąc od korzenia) wszystkich wierzchołków w poddrzewie pod daną krawędzią

Ta struktura danych to po prostu drzewo (+, maks) zbudowane na preorderach wierzchołków. Złożoność każdego zapytania to O(log(rozmiar drzewa)).

Gdy na wejściu jest zapytanie "zmień coś", iterujemy się po wszystkich O(log(n)) drzewach centroidowych zawierających zadane wierzchołek lub krawędź i w każdym z nich zmieniamy coś w strukturze danych.

Pozostaje odpowiadać na zapytania z zadania - Bajtazar jest w jakimś wierzchołku X i chce przejść do optymalnego innego. Iterujemy się po drzewach centroidowych zawierających X i w każdym pytamy o optymalny docelowy wierzchołek przy założeniu, że ścieżka przejdzie przez centroid. Ze struktury danych odczytujemy odległość z X do centroidu (korzenia), po czym pytamy o najmniejszą wartość w pozostałych poddrzewach (tych synów korzenia, którzy nie zawierają X poniżej). Ja zrobiłem tak, że dla każdego X pamiętałem do poddrzewa którego syna korzenia należy X, po czym odczytywałem minimum z dwóch przedziałów (na lewo i na prawo od tego poddrzewa). Można też na chwilę zrobić sztuczne zapytanie "zmień wartość X na INF", by w ten sposób zakazać powrotu do X - okazuje się, że wtedy nie musimy się martwić tym, że dopuszczamy przejście z X przez korzeń z powrotem w dół do jakiegoś wierzchołka w tym samym poddrzewie. Bo przecież to nie jest optymalne.

To ja mam znowu inaczej niż wszyscy, ale tym razem nie przyjemniej :P.
Robimy sobie hld i w wierzchołku dla drzewa hld trzymamy sobie najlepszy wynik dla jego poddrzewa nie licząc tej części, do której schodzi ciężka ścieżka. Drzewo przedziałowe w hld to drzewo z wartościami i przesunięciem w punkcie (przesunięcie to krawędź między wierzchołkami) , aktualizacją w punkcie i maksem na przedziale.
Teraz jak chcemy zapytać się o wynik dla wierzchołka, to pytamy się o całą ścieżkę od roota do niego. Dzięki hld okazuje się, że wszystkie krawędzie na tej ścieżce, oprócz logn z nich, są ciężkie, a wtedy możemy brać maksa ze ścieżki w hld. Te logn wierzchołków rozpatrujemy osobno, na drzewku tylko w dół, usuwając "ręcznie" to poddrzewo, w którym jest wierzchołek z zapytania.
Aktualizacje są podobne - jak zmieniamy wartość, to trzeba zaktualizować tylko log wierzchołków w drzewie hld - te, na ścieżce do korzenia, do których idziemy lekkimi krawędziami.

A mnie tam nie interesuje, czy to będzie drzewo zrównoważone, czerwono-czarne, czy może brzoza, ani gdzie jest centroid. I nie mam pojęcia, jaka jest złożoność mojego programu. Uczyłem się tego w latach 80-tych i już nic nie pamiętam, a zadania robię "na zdrowy rozum". W tym przypadku rozumowanie przebiegało następująco:
Ponieważ między każdymi dwoma miastami jest tylko jedna ścieżka, to można na to patrzeć jak na MST w grafie, ale to też nieistotne. Ważne, że jest jedna.
- Wychodzimy z miasta, gdzie jest Bajtazar, po kolei każdą drogą, robiąc DSF.
- W każdym mieście po drodze zapamiętujemy (na stałe), którą drogą idzie się do Bajtazara.
- Wracając (od "liści"), w każdym mieście zapamiętujemy, jaki jest maksymalny zysk jak wyjdziemy z niego daną drogą (minus myto), i w którym mieście to będzie (o drodze, którą wracamy do Bajtazara, nie wiemy tego, ale w tej chwili nas to nie obchodzi, bo nie pójdzie w tę stronę). Sprawdzamy, czy w ogóle jest sens gdzieś iść, bo może w tym mieście zarobimy więcej, i informację o tym, gdzie jest największy zysk, propagujemy dalej wstecz.
- Bajtazar wie teraz, którą drogą iść i do którego miasta, żeby najwięcej zarobić, a idąc tam, w każdym mieście podmienia dwie wartości: którą drogą teraz trzeba iść do Bajtazara, i jaki jest maksymalny zysk dla drogi, którą tu przyszedł.
- O świcie, jak zmienia się zysk lub myto na drodze, propagujemy nową wartość, ale tylko od miasta, gdzie jest zmiana (dalsze z miast w przypadku zmiany myta) do miasta, gdzie jest Bajtazar. Reszta grafu się sama zaktualizuje, w miarę jak Bajtazar będzie sobie po nim chodził, lub przy propagacji kolejnych zmian.
- Bajtazar znowu wybiera drogę i miasto, gdzie będzie największy zysk. I tyle.

Czas wykonania dla mniejszych zestawów danych był 0s, dla dużych 0,4s, więc złożoność czasowa mojego programu napisanego "na zdrowy rozum" jest dla mnie satysfakcjonująca. Jak zwykle w jednym miejscu walnąłem się w kodzie, więc odjęło mi 3 pkt. Nigdy nie chce mi się testować własnych programów. Nudne to :)

Pozdrawiam wszystkich

No to się chyba organizatorzy nie popisali przy układaniu testów bo to rozwiązanie jest nieoptymalne.

Dobrze rozumiem, że przy każdym zapytaniu program rozważa wszystkie miasta na ścieżce od aktualnego do nowego optymalnego? Jeśli tak to rozwiązanie będzie za wolne w sytuacji gdy graf jest ścieżką i optymalne jest zawsze przejście na drugi koniec ścieżki. Wtedy Bajtazar musi przejść n*q kroków.

To brzmi jak O(qn). Jaki byłby czas działania Twojego rozwiązania dla:

ścieżki - 100000 wierzchołków, koszt każdej krawędzi to 1, zysk w wierzchołku 1 i n to 10^18, w pozostałych 1. Teraz mamy 100000 zmian na jednej krawędzi - na zmianę jej koszt będzie wynosił 1 lub 2. Z tego wynika, że Bajtazar dla każdego zapytania zawsze przechodziłby po całym grafie od jednego końca ścieżki do drugiego.

Edit. Przyjrzałem się testom - jeśli chodzi o małe zestawy, to są tylko 2: ban1 i ban2. Ban3 wygląda na losowy, ban5 i ban6 możliwe, że mają jakąś regularną strukturę. Ban4 i ban10 to wszystkie wierzchołki podłączone do 1. Ban7, ban8 i ban9 to ścieżki - aczkolwiek nie wiem jak zmiany na krawędziach wpływają na czas podróży. Czy miałeś zaakceptowany któryś z tych 3 ostatnich?

Janusz dziękuję za podzielenie się swoim pomysłem - bardzo mi się podoba to rozwiązanie!

Ja też tak zrozumiałem, że algorytm rozważa wszystkie wierzchołki od starego do nowego optymalnego (+jeszcze czas propagacji zmiany) co pesymistycznie daje O(nq), ale średnio dla losowych danych jest pewnie znacznie szybsze.

@Anna:
"przy każdym zapytaniu program rozważa wszystkie miasta na ścieżce od aktualnego do nowego optymalnego? Jeśli tak to rozwiązanie będzie za wolne w sytuacji gdy graf jest ścieżką i optymalne jest zawsze przejście na drugi koniec ścieżki."

A: Tak, ale to jest przypadek szczególny, a dla takich można zaimplementować inny algorytm, działający w czasie w przybliżeniu O(1) dla każdego zapytania, jeśli największa długość ścieżki będzie ~= ilości krawędzi. Tylko zeżre trochę pamięci wtedy. Dla algorytmu uniwersalnego zawsze można znaleźć jakieś ekstremalne przypadki. Na przykład pliki, które nie poddają się kompresji...

@Przemysław:
Wyłożył się na ban1, 7 i 9 (dla 1 błędny wynik, dla 7 i 9 zapętlił się). Po poprawce w jednej linijce przechodzi spokojnie wszystkie poza ban9. Czasowo też. Gdzieś mam jeszcze jeden błąd w kodzie.

@Janusz - to nie jest szczególny przypadek. Możesz mieć masę drzew, gdzie najdłuższa ścieżka będzie miała ok n/2 wierzchołków. Robisz to samo co poprzednio, w dwóch wierzchołkach na końcach tej ścieżki dajesz 10^18, reszta 1, koszt krawędzi 1, dajesz 100000 zapytań o podmianę jakiejś krawędzi z 1 na 2 i ciągle chodzisz po najdłuższej ścieżce w te i z powrotem.

Edit. W ogóle zastanawia mnie czy ten program jest poprawny. Pozapamiętywałeś najlepsze miasta dla każdego wierzchołka grafu. Weźmy najlepsze miasto, do którego mógł dojść Bajtazar przed zmianą - v. Teraz redukujemy zysk w v do tego stopnia, że przestanie być najlepsze. Wracasz od v -> x1->x2->..->Bajtazar. Jak aktualizujesz informacje dla xi, które miasto jest teraz najlepsze dla tego wierzchołka?

@Paweł
Bardzo proszę :)
Też się spodziewałem, że takie rozwiązanie będzie strasznie powolne, ale to jest bardzo duża ilość najprostszych operacji (porównania i proste operacje arytmetyczne). Ścieżkę rzędu 50000 można przejść nawet kilkanaście tys. razy/s. Przy danych rzędu milionów i więcej takie rozwiązanie już nie miałoby sensu.


@Przemysław
To _jest_ szczególny przypadek, ponieważ uparłeś się, że zmiany będą ciągle na dwóch końcach najdłuższej ścieżki. Nawet jeżeli, to algorytm będzie działał poprawnie, tylko wolniej niż inne. Przy zmianach losowych będzie w miarę wydajny, zwłaszcza że propagacja zmiany często skończy się natychmiast (patrz poniżej).

Q: "Jak aktualizujesz informacje dla xi, które miasto jest teraz najlepsze dla tego wierzchołka?"
A: Mniej więcej tak: między miastami przesyłana jest referencja do obiektu klasy

class NextCity {
public:
long nr; // numer miasta o największym zysku
long long profit; // maksymalny zysk, po drodze w locie odejmujemy od niego myto
long wayHome; // z którego miasta przychodzi informacja, czyli do którego miasta Bajtazar ma stąd potem iść

bool operator<(const NextCity& c) const
{
if(this->profit != c.profit)
return this->profit > c.profit;
return this->nr < c.nr;
}
}

Każde miasto, które nie jest "liściem", trzyma sobie cały czas set<NextCity>, a w nim to, co przyszło z każdej ścieżki, oraz obiekt <NextCity> dla samego siebie. Wysyła dalej zawsze pierwszy element, podmieniając 'wayHome' na swój numer.
Miasto, które jest "liściem", wysyła zawsze obiekt <NextCity> dla samego siebie.
Przy propagacji zmiany porównujemy to, co przychodzi, z pierwszym elementem seta. Jeżeli przyszło to samo, kończymy propagację zmiany (nie musi dojść do Bajtazara, bo reszta grafu się nie zmienia). Jeżeli przyszło co innego, wymieniamy w secie element, który miał taki sam "wayHome", na to, co przyszło, i wysyłamy dalej pierwszy element seta, podmieniając jak zwykle 'wayHome' na numer bieżącego miasta.
Ja napisałem to inaczej, żeby ograniczyć ilość operacji O(log(n)) na setach. Mieszam konieczne operacje na setach z prostymi porównaniami. Kod jest brzydki, ale dużo szybszy. Idea jest jednak właśnie taka.

BTW. Doszedłem do tego, dlaczego program wywalił się na ban9.in - tam jest najdłuższa ścieżka ze wszystkich testów licząc od miasta [1], ja zrobiłem jak głupi DSF rekurencyjnie na iteratorach, co się fajnie pisze, ale zajmuje kupę pamięci, i stos mi się skończył :) Gdybym napisał to bardziej niskopoziomowo, to też by przeszło.

Czyli set pełni rolę kolejki priotytetowej - jak przeczytałem Twój pierwszy opis to właśnie tak wywnioskowałem, że w każdym węźle jeszcze musi być kolejka.

Dokładnie tak. Przepraszam, ale ja już nie myślę pojęciami z algorytmiki, tylko od problemu przechodzę od razu do kodu. Zamiast "drzewo" myślę "mapa", a zamiast "kolejka priorytetowa" myślę "ta klasa musi mieć seta". Takie zboczenie zawodowe...

Maksymalna średnica drzewa we wszystkich testach poza 9 to 900. Test 9 to idealna lista (maksymalny stopień 1). :D

@Janusz: To teraz dalszy przypadek

mamy v <- x1 <-x2 <-..<-Bajtazar <-y1-<y2<-..<-root

Krawędzie mają koszt 1, wierzchołki mają zysk 1, v ma zysk 10^18, v, 10^17, v" 10^16

v' jest podłączone do x2, a v" do y2.

Teraz zmieniamy zysk w v na 1, więc aktualizujesz wszystkim wierzchołkom na ścieżce od v do Bajtazara wartość na v'. Bajtazar idzie do v'. Teraz zmieniamy zysk w nieznaczącym wierzchołku (np. v na 2). Więc Bajtazar z v' powinien pójść do v". Jak on to zrobi, gdy węzły od y1 do roota ciągle pokazują starą wartość do v (10^18)?

Edit. To chyba jednak będzie działać. W momencie przechodzenia z poprzedniego miejsca Bajtazara do y1, przekażemy nową wartość z Bajtazara, którą zaktualizujemy w secie y1 itd.

Do końca chciałem wierzyć, że to nieprawda, że cała masa ludzi spokojnie uzyska 9/10 za to zadanie. To rozwiązanie ma złożoność gorszą niż O(qn), bo w grę wchodzi set...

"węzły od y1 do roota ciągle pokazują starą wartość do v (10^18)"

Nie pokazują. Na samym początku "root'em" jest węzeł, w którym jest Bajtazar. To z tego punktu robimy DSF po całym grafie, i z wszystkich gałęzi wychodzących z węzła [1] dostaje informację, jaki jest maksymalny zysk, jeśli pójdzie w danym kierunku. A jak już gdzieś idzie, to tak jak napisałem wcześniej
"idąc tam, w każdym mieście podmienia dwie wartości: którą drogą teraz trzeba iść do Bajtazara, i jaki jest maksymalny zysk dla drogi, którą tu przyszedł."
Czyli idąc do v', będzie zostawiał za sobą w węzłach informację, że w v" jest zysk 10^16 (mniejszy niż w v' do którego aktualnie podąża)

" To rozwiązanie ma złożoność gorszą niż O(qn), bo w grę wchodzi set..."

Wiem, i właśnie dlatego
"Ja napisałem to inaczej, żeby ograniczyć ilość operacji O(log(n)) na setach. Mieszam konieczne operacje na setach z prostymi porównaniami. Kod jest brzydki, ale dużo szybszy. Idea jest jednak właśnie taka."

Nieco podobne zadanie, jak i rozwiązanie podobne do tego, które zaproponował pan Janusz, było na USA Computing Olympiad.
Tutaj treść:
http://www.usaco.org/index.php?page=viewproblem2&cpid=745

oraz omówienie:
http://www.usaco.org/current/data/sol_grass_platinum_open17.html

@Janusz

"Ja napisałem to inaczej, żeby ograniczyć ilość operacji O(log(n)) na setach. Mieszam konieczne operacje na setach z prostymi porównaniami. Kod jest brzydki, ale dużo szybszy. Idea jest jednak właśnie taka."

To już nie jest rozwiązanie na zdrowy rozum ;)