Omówienie zadania Turniej trójinformatyczny (III etap XXV OI)

Istotne informacje dotyczące wyników zawodników będziemy przedstawiać na skierowanym grafie, w którym wierzchołki reprezentują zawodników. Fakt, że zawodnik \(a\) wygrał w co najmniej dwóch konkurencjach z zawodnikiem \(b\), będziemy reprezentować za pomocą skierowanej krawędzi z wierzchołka \(a\) do wierzchołka \(b\).

Przekładając definicję Bajtazara na język teorii grafów, okazuje się, że zawodnik \(a\) moralnie zwycięża zawodnika \(b\), jeżeli istnieje w naszym grafie skierowana ścieżka od wierzchołka \(a\) do wierzchołka \(b\). Łatwo tę równoważność udowodnić po długości takiej najkrótszej ścieżki.

Co więcej, nasz graf ma skierowaną krawędź pomiędzy każdą parą wierzchołków (bo w wynikach konkurencji nie ma remisów, więc na trzy konkurencje zawsze któryś zawodnik wygrywa większość z nich). Okazuje się, że tytuł zadania zawiera lekki spoiler, ponieważ taki graf nazywa się właśnie turniejem.

Podzadania 1 i 2

Jedno z najprostszych implementacyjnie rozwiązań tego zadania polega na bezpośrednim zastosowaniu algorytmu Floyda–Warshalla. Algorytm ten w czasie \(O(n^3)\) znajduje najkrótsze skierowane ścieżki pomiędzy wszystkimi parami wierzchołków, tak więc można go wykorzystać do stwierdzenia, czy takie ścieżki w ogóle istnieją.

Algorytm uruchamiamy na macierzy sąsiedztwa naszego grafu, a po jego zakończeniu w macierzy tej będziemy mieli dla każdej skierowanej pary wierzchołków informację, czy istnieje między nimi ścieżka. Wobec tego każde zapytanie obsłużymy w czasie stałym, a całe rozwiązanie będzie miało złożoność \(O(n^3 + m)\).

Podzadanie 3

Oczywiste jest, że jeżeli istnieje skierowana krawędź z wierzchołka \(a\) do wierzchołka \(b\), to na zapytanie o parę \((a,b)\) możemy od razu odpowiedzieć twierdząco. W przeciwnym wypadku musimy stwierdzić, czy istnieje jakaś mniej bezpośrednia ścieżka z wierzchołka \(a\) do wierzchołka \(b\).

Skoro nie istnieje bezpośrednia krawędź z \(a\) do \(b\), a nasz graf jest turniejem, to znaczy, że na pewno istnieje bezpośrednia krawędź z wierzchołka \(b\) do wierzchołka \(a\). Tak więc wierzchołek \(a\) jest osiągalny z wierzchołka \(b\). Zatem pytanie o to, czy wierzchołek \(b\) jest osiągalny z wierzchołka \(a\) jest równoważne pytaniu, czy oba te wierzchołki znajdują się w tej samej silnie spójnej składowej.

Na początek wyznaczymy sobie podział naszego grafu na silnie spójne składowe. Możemy do tego użyć dowolnego algorytmu, ponieważ liczba krawędzi w naszym grafie jest rzędu \(O(n^2)\), więc nawet standardowe algorytmy na szukanie silnie spójnych składowych, które działają w czasie liniowym od wielkości grafu, będą tutaj działać w czasie \(O(n^2)\).

Gdy każdego wierzchołka poznamy numer jego silnie spójnej składowej, to każde zapytanie zrealizujemy w czasie stałym. Odpowiedź na zapytanie jest ,,tak”, jeżeli istnieje bezpośrednia krawędź z wierzchołka \(a\) do wierzchołka \(b\), a jeżeli takiej krawędzi nie ma, to wtedy, jeżeli te wierzchołki mają ten sam numer silnie spójnej składowej.

Czyli ostatecznie złożoność czasowa tego rozwiązania będzie wynosić \(O(n^2 + m)\).

Zauważmy też, że nie musimy trzymać wszystkich \(O(n^2)\) krawędzi naszego grafu w pamięci. Możemy je w czasie stałym wyznaczać w locie na podstawie wyników z konkurencji. Tak więc złożoność pamięciowa tego rozwiązania może być liniowa.

Pełne rozwiązanie

Będziemy chcieli wykorzystać ten sam pomysł, co w poprzednim algorytmie, tylko teraz będziemy musieli szybciej wyznaczyć podział grafu na silnie spójne składowe. Zrobimy to, wykorzystując ciekawy fakt dotyczący turniejów, a mianowicie w każdym grafie będącym turniejem istnieje ścieżka Hamiltona, to znaczy ścieżka przechodząca przez każdy wierzchołek dokładnie raz. Jak sprawnie znaleźć taką ścieżkę pokażemy za chwilę, a teraz pokażemy algorytm, który będzie z istnienia tej ścieżki korzystał.

Jeżeli rozważymy pewną ścieżkę Hamiltona w naszym grafie, to wyznacza ona pewien porządek na wierzchołkach tego grafu. Jeżeli narysujemy sobie wierzchołki tego grafu w tym porządku, to \(n - 1\) krawędzi ze ścieżki będzie prowadziło między kolejnymi parami wierzchołków w prawo. Pozostałe krawędzie w grafie mogą również prowadzić w prawo, z tym że one nie będą dla nas ciekawe, ponieważ nie wnoszą żadnej nowej informacji odnośnie silnie spójnych składowych. Interesujące za to będą krawędzie w lewo, bo każda taka krawędź powoduje, że wszystkie wierzchołki na ścieżce pomiędzy końcami tej krawędzi będą znajdowały się w jednej silnie spójnej składowej.

Z tego wynika, że każda silnie spójna składowa będzie tworzyła pewien przedział wierzchołków na ścieżce. Podobnie jak krawędzie w prawo nie wnosiły nam żadnej nowej informacji, tak samo duża część krawędzi w lewo będzie niosła informacje redundantne. Jeżeli popatrzymy sobie na krawędzie wychodzące w lewo z jakiegoś ustalonego wierzchołka, to każda z tych krawędzi daje nam informację, jak daleko w lewo może rozciągać się silnie spójna składowa zawierająca ten wierzchołek, i najwięcej informacji daje nam tutaj krawędź, która prowadzi jak najbardziej w lewo, czyli do najwcześniejszego wierzchołka na ścieżce. Wystarczy więc, że dla każdego wierzchołka wyznaczymy najdłuższą krawędź idącą w lewo.

Jeżeli wyznaczymy taką najdalszą krawędź dla każdego wierzchołka, to podziału na silnie spójne składowe dokonamy jednym przejściem po wierzchołkach od strony prawej do lewej. Na początek bierzemy skrajnie prawy wierzchołek i wrzucamy go do jego silnie spójnej składowej. Dla każdego kolejnego wierzchołka patrzymy na krawędzie idące w lewo. Jeżeli takie krawędzie są, to patrzymy, gdzie się kończą i rozszerzamy silnie spójną składową do ich lewych końców. Jeżeli w skrajnie prawym wierzchołku silnie spójnej składowej nie ma takich krawędzi, to zamykamy składową i w kolejnym wierzchołku otwieramy nową. Całe przejście będzie działać w czasie \(O(n)\).

Najdalsze krawędzie w lewo

Każdemu wierzchołkowi \(v\) przypiszemy jego numer \(h(v)\) w kolejności na ścieżce Hamiltona. Przypomnijmy, że w grafie istnieje krawędź z wierzchołka \(a\) do wierzchołka \(b\), kiedy zawodnik \(a\) wygra w co najmniej dwóch konkurencjach z zawodnikiem \(b\). Na chwilę załóżmy dla uproszczenia, że wygrywa on w pierwszych dwóch konkurencjach.

Wyniki tych konkurencji dla poszczególnych zawodników możemy przedstawić jako punkty na płaszczyźnie. Na osi poziomej będziemy mieli wynik z pierwszej konkurencji, a na osi pionowej wynik z drugiej konkurencji, czyli każdemu wierzchołkowi \(v_i\) odpowiada punkt \((x_i,y_i)\).

Wszystkie wierzchołki \(v_j\), z którymi \(v_i\) wygrywa bezpośrednio za pomocą pierwszej i drugiej konkurencji, muszą mieć dalsze miejsca w tych konkurencjach, wobec tego reprezentujące je punkty \((x_j,y_j)\) muszą znajdować się na prawo i powyżej od punktu \((x_i,y_i)\), czyli w ćwiartce, której dolnym lewym rogiem jest \((x_i,y_i)\). Interesuje nas ten punkt z ćwiartki, którego wierzchołek \(v_j\) jest najwcześniej na ścieżce Hamiltona, czyli ma najmniejszy numer \(h(v_j)\).

Wyznaczenie najmniejszych numerów z ćwiartek dla wszystkich wierzchołków możemy zrobić dwuwymiarowym drzewem przedziałowym w czasie \(O(n \log^2 n)\) albo zamiataniem i jednowymiarowym drzewem przedziałowym w czasie \(O(n \log n)\). Sortujemy punkty malejąco po \(y_j\) i w takiej kolejności wrzucamy je do drzewa przedziałowego na pozycję określoną przez \(x_j\) i z wagą równą \(h(v_j)\). Tuż przed wrzuceniem wierzchołka \(v_i\) do drzewa, odpytujemy się o minimum na sufiksie zaczynającym się za pozycją \(x_i\).

W ten sposób znajdziemy najdłuższe krawędzie w lewo generowane przez wyniki dla pierwszej i drugiej konkurencji. Aby znaleźć pozostałe krawędzie, uruchamiamy ten sam algorytm z zamiataniem i drzewem przedziałowym dla konkurencji drugiej i trzeciej, a potem jeszcze raz dla konkurencji pierwszej i trzeciej. W sumie uruchamiamy go trzy razy.

Tak więc całe rozwiązanie zadania będzie działało w czasie \(O(n \log n + m)\), o ile będziemy w stanie znaleźć w czasie \(O(n \log n)\) ścieżkę Hamiltona w turnieju.

Ścieżka Hamiltona w turnieju

Istnieje bardzo sprytna metoda znajdowania ścieżki Hamiltona w turnieju, wykorzystująca do tego sortowanie przez scalanie, czyli algorytm merge sort. Tak jak w tym algorytmie, używamy metody dziel i zwyciężaj, czyli dzielimy zbiór wierzchołków grafu na dwa w miarę liczne podzbiory i w obu tych podgrafach, z których każdy jest również turniejem, znajdujemy rekurencyjnie ścieżkę Hamiltona. Następnie w fazie scalania będziemy przeplatać ze sobą te dwie ścieżki, aby utworzyć ścieżkę Hamiltona w całym grafie.

Łączenie ścieżek będziemy wykonywać tak samo jak w algorytmie merge sort, tylko teraz zamiast porównywania liczb będziemy patrzyli na skierowania krawędzi. Na początku patrzymy na skierowanie krawędzi, która łączy początkowe wierzchołki \(a\) i \(b\) dwóch ścieżek. Jeżeli ta krawędź jest skierowana \(a\to b\), to \(a\) stanie się początkiem scalonej ścieżki (a w przeciwnym wypadku początkiem stanie się \(b\)). Następnie usuwamy go z jego starej ścieżki i pozostałe części ścieżek łączymy rekurencyjnie.

Poprawność algorytmu wynika z tego, że będziemy utrzymywali następujący niezmiennik. Algorytm będzie usuwał wierzchołki z początków ścieżek \(A\) i \(B\) oraz łączył je tworząc nową ścieżkę wynikową \(S\). Za każdym razem będziemy mieli spełnione założenie, że końcowy wierzchołek ścieżki \(S\) można rozszerzyć o początkowy wierzchołek reszty ścieżki \(A\) lub początkowy wierzchołek reszty ścieżki \(B\).

Podsumowując, algorytm zadziała w czasie \(O(n \log n)\) – dokładnie w takim samym jak sortowanie przez scalanie.