Przede wszystkim to zadania z rundy B były jakieś wyjątkowo trudne jak na rundę B. Po Skarbonce właściwie nie było nawet "średnich" zadań (może prócz Działki 2, ale w tym momencie wiele osób już się pewnie poddało).

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

Hmm, co do dogrywki, mogłoby się okazać że mało kto w niej wziął udział (nie dobiło by do 256).

A na przyszłość można by (zamiast losować) wprowadzić dodatkowe kryterium, np. czas wysłania zadania, długość kodu, czas wykonania, zajętość pamięci.

Ja w takim przypadku zarządziłbym po prostu dogrywkę. Zaserwować jedno dodatkowe zadanie, takie, że ma wiele prawidłowych rozwiązań, a nadesłane rozwiązania posortować od najlepszego do byle jakiego.

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

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.

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

@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?

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

IMHO zdrowy rozsądek > zasady
Jeśli miejsca 251-400 miałyby po tyle samo punktów to zupełnie zrozumiałe byłoby przyznanie tylko 250 koszulek. Podobnie gdyby było tylko 200 startujących z dodatnią liczbą punktów.

Na przyszłość warto wprowadzić zapis: Jeśli jest ex aequo na 256-tym miejscu, to losujemy odpowiednio dużo zremisowanych osób.

Ja to zrobiłem w czasie O(nlg^2n) i pamięci O(nlgn) z wykorzystaniem persistent segment tree. Dla każdego ucznia tworzę sobie nowe drzewo, które różni się w lgn węzłach od poprzedniego ucznia. W węzłach drzewa trzymam wartości hasha na odp przedziale tekstu.

Następnie robię zwykłe sortowanie liczb - porównanie dwóch liczb sprowadza się do znalezienia pierwszego elementu, na którym się różnią hashe i porównania elementów z tekstu na tej pozycji - obie te operacje na drzewach przedziałowych zajmują lg n, czyli całość nlgn porównań * lgn = O(nlg^2n).

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.

Wszyscy, którzy są sklasyfikowani na miejscach 1-256 w lidze B dostają koszulki. Nie można nie dać koszulki zawodnikowi, który ma miejsce < 257.

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?

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.