Omówienie zadania Plan metra (I etap XXV OI)

W zadaniu mamy dane dwa ciągi:

• \(d_i\) – odległość (cena biletu do) wierzchołka \(i\) od wierzchołka \(1\) dla \(2 \le i \le n-1\)
• \(l_i\) – odległość (cena biletu do) wierzchołka \(i\) od wierzchołka \(n\) dla \(2 \le i \le n-1\)

Na podstawie tych danych chcemy ustalić, czy opisują one jakieś krawędziowo-ważone drzewo. Jeśli tak, chcemy wypisać krawędzie dowolnego drzewa pasującego do otrzymanego opisu.

Początkowe obserwacje

Jako że w zadaniu chcemy otrzymać dowolne drzewo pasujące do opisu, postaramy się skonstruować je w jak najprostszy sposób.

Przypatrzmy się ścieżce z wierzchołka \(1\) do wierzchołka \(n\). Okazuje się, że możemy rozważać tylko drzewa, w których każdy wierzchołek leży na ścieżce z \(1\) do \(n\) albo jest połączony krawędzią z wierzchołkiem z tej ścieżki. Dowód jest dosyć prosty:

Rozważmy drzewo zgodne z opisem zadanym przez ciągi \(l\) i \(d\), które jednak nie jest w formie zaproponowanej powyżej. Musi wtedy istnieć liść \(x\) \(\notin \{1, n\}\), który nie jest połączony krawędzią z żadnym wierzchołkiem ze ścieżki. Niech \(y\) będzie wierzchołkiem ze ścieżki, który jest najbliższy do \(x\).

Możemy teraz usunąć jedyną krawędź, którą ma \(x\) oraz dodać krawędź z \(y\) do \(x\) o długości ścieżki z \(y\) do \(x\). W ten sposób zachowujemy odległości \(x\) do wierzchołków \(1\) i \(n\), a powstały graf nadal jest drzewem. Wykonując tę operację wiele razy dochodzimy od dowolnej odpowiedzi do odpowiedzi w pożądanej formie.

Podzadanie \(n \leq 10\), \(l_i, d_i \leq 200\)

W tym podzadaniu możemy sprawdzić każdą potencjalną długość ścieżki z \(1\) do \(n\). Konstrukcja dla długości \(x\) wygląda następująco:

Na początek szukamy wszystkich wierzchołków, które leżą na ścieżce z \(1\) do \(n\). Są to te, dla których zarówno \(d_i\) jak i \(l_i\) są mniejsze od \(x\). Aby otrzymać kolejność musimy je posortować po \(l_i\)

Teraz dla każdego wierzchołka spoza ścieżki szukamy wierzchołka ze ścieżki, z którym może on być połączony krawędzią. Jeśli wierzchołek \(i\) ma być połączony z wierzchołkiem \(j\), to długość krawędzi musi być równa \(d_i - d_j\). Musi ona jednak również być równa \(l_i - l_j\) oraz być większa od 0. Więc przy próbie dodania krawędzi między \(i\) oraz \(j\) sprawdzamy równość \(d_i - d_j = l_i - l_j\) oraz nierówność \(d_i > d_j\)

Jeśli próba takiej konstrukcji nie powiodła się to próbujemy jeszcze raz dla większego \(x\). W przeciwnym wypadku mamy odpowiedź.

Rozwiązanie to działa więc w czasie \(O(z \cdot n^2)\), gdzie \(z\) to zakres długości potencjalnej ścieżki.

Podzadanie \(n \leq 3000\)

Okazuje się, że łatwo jesteśmy w stanie pozbyć się \(z\) ze złożoności. Wystarczy zastanowić się jak wygląda ścieżka z \(1\) do \(n\). Mamy do rozważenia 2 przypadki:

1. Wierzchołki \(1\) i \(n\) są połączone krawędzią.
2. Na ścieżce z \(1\) do \(n\) jest co najmniej jeden wierzchołek pośredni.

1. Wierzchołki \(1\) i \(n\) są połączone krawędzią.

W tym przypadku rozwiązanie jest bardzo proste. Niech \(x\) będzie długością krawędzi z \(1\) do \(n\). Każdy wierzchołek musi być połączony krawędzią z wierzchołkiem \(1\) lub \(n\). Oczywiście będzie połączony z tym, do którego ma bliżej.

A więc wierzchołek \(i\), dla którego \(d_i < l_i\) jest połączony krawędzią długości \(d_i\) z wierzchołkiem \(1\). Musi wtedy zachodzić \(l_i = x + d_i\), bo ścieżka z \(n\) do \(i\) składa się z krawędzi z \(n\) do \(1\) oraz z \(1\) do \(i\). Analogicznie dla wierzchołków połączonych krawędzią z wierzchołkiem \(n\) dostajemy \(d_i = x + l_i\).

Musimy więc tylko sprawdzić, czy dla każdego wierzchołka wartość \(|l_i - d_i|\) jest taka sama. Będzie to x, czyli długość krawędzi z \(1\) do \(n\). Złożoność w tym przypadku to \(O(n)\).

2. Na ścieżce z \(1\) do \(n\) jest co najmniej jeden wierzchołek pośredni.

Zauważmy, że możemy jednoznacznie wyznaczyć wierzchołki z tej ścieżki. Będą na niej leżały tylko te wierzchołki, dla których wartość \(d_i + l_i\) jest minimalna - bardziej formalnie \(i\) leży na ścieżce wtedy i tylko wtedy, gdy \(d_i + l_i = \min(l_j + d_j \, | \, 2 \leq j \leq n - 1)\). Jest tak dlatego, że dla każdego wierzchołka spoza tej ścieżki, \(d_i + l_i\) zawiera w sobie długość ścieżki powiększoną o długości dodatkowych krawędzi.

Możemy teraz ponownie zastosować metodę z poprzedniego podzadania do odnalezienia dla każdego wierzchołka spoza ścieżki wierzchołka, z którym może być połączony krawędzią.

Złożoność tego przypadku oraz całego rozwiązania jest wynosi \(O(n^2)\).

Pełne rozwiązanie

Ulepszymy teraz znajdowanie wierzchołka ze ścieżki, do którego chcemy połączyć wierzchołek spoza ścieżki.

Wcześniej, dla każdego wierzchołka \(i\) spoza ścieżki, sprawdzaliśmy czy może być połączony z wierzchołkiem \(j\) ze ścieżki, za pomocą warunku \(d_i - d_j = l_i - l_j\). Ta równość jest jednak równoważna następującej: \(d_i - l_i = d_j - l_j\). Jest to dużo lepszy warunek, ponieważ po obu stronach równości mamy wartości dotyczące tylko jednego wierzchołka.

Możemy zatem dla każdego wierzchołka ze ścieżki zapamiętać wartość \(d_i - l_i\) i dla każdego wierzchołka spoza ścieżki sprawdzić czy istnieje wierzchołek na ścieżce, który ma taką samą wartość. Co więcej, nie musimy już sprawdzać czy \(d_i > d_j\), ponieważ wynika to ze sposobu wyboru wierzchołków na ścieżce.

Zapamiętywanie możemy zrealizować na przykład za pomocą unordered_map. Zarówno dorzucenie wartości \(d_i - l_i\) jak i zapytanie o tę wartość działa średnio w czasie stałym.

Zagwarantuje to nam złożoność czasową rozwiązania \(O(n \log n)\). Logarytm występuje tu ze względu na konieczność posortowania wierzchołków na ścieżce.