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

@Krzysztof: sprytne, aczkolwiek wysokości dla wiersza 0 nie musiałeś wysyłać, miałbyś 99 wiadomości mniej (dla porównania ja miałem 99*750 wiadomości po 400 bajtów, czyli danych tyle samo ale w mniejszych paczkach).

Wygląda na to że scenariusz Piotrka się sprawdza. Po 4 rundzie miejsca 163-388 są ex aequo (10p. za 1B i 3p. za 2B). Po 5. rundzie już raczej 94 osoby nie przekroczą 13 punktów. W takim razie organizatorzy będą musieli dorobić 132 koszulki (plus tym co w 5 rundzie przekroczą 12 punktów), albo 94 nie dać (minus tym co w 5 rundzie przekroczą 13 punktów).

Struktura rozwiązania jest dość podobna do algorytmu KMR, może to pomoże w wyobrażeniu sobie tych operacji.

Weźmy taki problem: mamy m dwuelementowych ciągów i dość niewiele (k1+k2=k) zmian (innymi słowy n=2 i więcej elementów niż zmian). Możliwych różnych dwuelementowych ciągów jest k+1. Posortujmy je i każdemu ciągowi przypiszmy jego indeks. Teraz mamy m jednoelementowych ciągów i k zmian w nim, bez straty informacji. Jeśli będziemy śledzić tylko zmiany to potrafimy taką operację wykonać w O(k).

Wróćmy do wyjściowego problemu. Połączmy parami każde dwa kolejne indeksy 1..n, redukując zagadnienie z n do n/2 w zamortyzowanym czasie O(m), ponieważ każda zmiana występuje tylko w jednej z wybranych par. Po O(log n) takich kroków dostaniemy n=1 a zmiany będą mówiły jakie są indeksy w posortowanym ciągu, czyli całość zajmuje O(m log n).

Podzieliłem planszę na 100 x 100 kwadratów. Instancja a wylicza wysokości w kolumnie a, oraz wyniki w wierszu a. Wysokości dla górnego wiersza kwadratu (a, b) są wysyłane od instancji b do instancji a, bezpośrednio. Mam dokładnie 9900 wiadomości, 99 per węzeł, każda wielkości <= 3KB (nie licząc sumowania wyniku). Każdy worker robi dokładnie to samo i chyba najmniej danych jest przesyłane ze wszystkich rozwiązań tutaj, natomiast dość dużo wiadomości. Trwa 7s na najwolniejszym teście.

Jak w temacie

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.

Tak - można dodać wiele liczb do kolejki i następnie wysłać je wszystkie w jednej wiadomości. Również z tym pojawił się problem, gdy na raz wysyłało się zbyt dużą ilość danych (ponad 64 KB). U mnie każda maszyna przesyłała jednorazowo 750 liczb, w sumie przesyłając cały wiersz (w 100 wiadomościach) przez 8 faz, czyli ok 800 wiadomości.

Dublin!

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.

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)

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

CAR dla k < 3 dał mi 3 punkty
BAN w czasie O(nq) dał mi 2 punkty

Koledzy, dopiero teraz jak spojrzałem na "Ograniczenia" w zadaniu to mnie oświeciło i chyba cały czas źle rozumiałem działanie biblioteki do przesyłania wiadomości. Myślałem, że w jednej wiadomości można przesłać tylko pojedynczą wartość Int/Char/LL. Teraz czytając Wasze rozwiązania domyśliłem się, że można wielokrotnie wywołać PutInt przed wywołaniem Send i to spowoduje wysłanie wielu Intów w jednej paczce?

Z tego powodu zakładałem, że nie jesteśmy w stanie propagować tablicy wysokości (jest długości 75000), bo nie wystarczy nam komunikatów. Dlatego w moim rozwiązaniu każdy węzeł liczył od zera tablicę wysokości, a dopiero właściwy algorytm ze stosem działał na podzbiorze działki. Takie podejście kosztowało mnie niestety stratę 9pkt.

Jak się robi to zadanie?