Posortujmy elementy tablicy. Spróbujmy policzyć wynik programowaniem dynamicznym. Często opłaca nam się przeprawiać osobę najszybszą z ostatnią osobą. To jednak nie zawsze jest optymalne.

Jest jeszcze drugi rodzaj ruchu -- możemy wziąć dwie najwolniejsze osoby, a latarkę wrócą wcześniej przewiezieni najszybsi. Z tego już można napisać programowanie dynamiczne, które dostaje 100 pkt.

Zasymulujmy turniej raz i spójrzmy, kto wygrał. Co możemy o nim powiedzieć?

Kluczowa obserwacja: Niech W będzie wygranym w turnieju. Wówczas osoba X może wygrać turniej wtedy i tylko wtedy, gdy istnieje ciąg X -> Y -> ... -> W, gdzie strzałki oznaczają: "Jest w stanie wygrać z". Dowód idzie dość prosto -- wyobraźmy sobie kolejność meczy gdzie W wygrywa, usuńmy wszystkie mecze z zawodnikami "X, Y, ..., W", a następnie dorzućmy na koniec turnieju w odwrotnej kolejności (tak, żeby na końcu X został niepokonany).

Teraz mamy już proste zadanie grafowe -- chcemy sprawdzić, dla których wierzchołków X istnieje ścieżka z X do W. To oczywiście oznacza, że istnieje ścieżka z W do X w grafie z odwróconymi krawędziami. Można więc puścić BFSa. Krawędzi jest jednak pesymistycznie O(n^2). Co teraz?

Możemy trzymać zbiór wszystkich nieodwiedzonych wierzchołków. Przeglądając jakiś wierzchołek Q w bfsie będziemy po prostu patrzeć, do których z tych wierzchołków da się dojść z Q. A da się wtedy i tylko wtedy, gdy taki nowy wierzchołek nie jest na liście Q. To pozwala nam w miarę łatwo zasymulować tę procedurę setem lub przy pomocy struktury find & union.

Jest jedna obserwacja, która praktycznie rozwala całe zadanie. Dla danego k przedział <a; b> jest dobry wtedy i tylko wtedy, gdy średnia na tym przedziale jest >= k, czyli suma większa niż (b-a+1)*k. Łatwo wykazać, że to warunek konieczny i pokazać algorytm, który przekłada klocki żeby było w porządku.

Poprzednia obserwacja wystarcza już do uzyskania dużej liczby punktów za mn log n w zasadzie jakkolwiek. Żeby to zbić do liniówki potrzebujemy jeszcze jednej obserwacji — jeśli szukamy przedziału o średniej >= k, to możemy od każdej liczby odjąć k, a następnie szukać najdłuższego przedziału o nieujemnej sumie. Na to ostatnie istnieje banalny zachłanny algorytm liniowy, zwany algorytmem Kadane'a.

Możemy potraktować tę sytuację jako graf, a kolejne przejścia jako krawędzie.

Mamy jakiś prosty podproblem tekstowy — to haszowanie lub funkcja prefiksowa od KMP.

Mamy jeszcze jakiś prosty podproblem grafowy — a, jak wiadomo, wszystko na ścieżkach w dowolnych grafach robi się w n^3 log M potęgowaniem macierzy. Pełne rozwiązanie w książeczce OI.

Skoro chcemy podzielić wierzchołki na dwie grupy to interesować nas będą grafy dwudzielne.

Zauważmy, że dwie autostrady reprezentowane przez odcinki (a1, a2) i (b1, b2) nie mogą być zbudowane po jednej stronie wtedy i tylko wtedy, gdy te odcinki zahaczają się (czyli zachodzi a1 < b1 < a2 < b2 lub b1 < a1 < b2 < a2). Z tego możemy już zbudować graf, który pesymistycznie ma O(n²) krawędzi i puścić na nim zwykłego dfsa do dwudzielnego grafu.

Wystarczy tylko przyspieszyć proces wyszukiwania krawędzi tak jak robiliśmy to w zadaniu turniej. Będziemy trzymać zbiór nieodwiedzonych wierzchołków, a następnie sprowadzimy szukanie krawędzi do zadania na drzewo przedziałowe.

Powiedzmy, że obsługujemy przedział <a, b> w bfsie i chcemy znaleźć krawędzie (oczywiście tylko wśród wierzchołków, których BFS jeszcze nie odwiedził). Wówczas (jeden z przypadków, drugi analogicznie) interesują nas odcinki, których lewy koniec leży w <a+1, b-1> a prawy koniec gdzieś po prawej stronie w <b+1, inf>. Wobec tego, możemy znaleźć maksymalny prawy koniec na przedziale <a+1, b-1> (i tu drzewo). Jeśli tworzy krawędź, to go usuniemy i wrzucimy na kolejkę, a w przeciwnym wypadku żaden z tych przedziałów nie może tworzyć krawędzi z naszym. Każdy odcinek wrzucimy i usuniemy co najwyżej raz, a zapytań na drzewie będzie O(nlogn) i taka jest też złożoność całego algorytmu.

Wśród dziwacznych operacji i wzorów warto zawsze napisać rozwiązanie brutalne, a potem zobaczyć co się dzieje. Napisz bruta i zobacz co się dzieje :)))))

Można zauważyć dwie zależności, które pozwalają nam napisać efektywne rozwiązanie. Więcej w książeczce 10 OI.