Informatyczny kącik olimpijski

Bajtockie kółeczko

Tym razem omówimy zadanie Bajtockie kółeczko z pierwszego etapu zawodów drużynowych X Olimpiady Informatycznej Gimnazjalistów.

Problem (Bajtockie kółeczko). W Bajtocji znajduje się $n + 1$ miast (ponumerowanych kolejnymi liczbami naturalnymi od 0 do $|n$ ) oraz $|2n$ dróg pomiędzy nimi. Miasta o numerach z przedziału $|[1;n]$ znajdują się na okręgu, zaś miasto o numerze 0 (stolica) jest środkiem tego okręgu. Pomiędzy każdym miastem na okręgu oraz stolicą istnieje dwukierunkowe połączenie ( $ai$ oznacza czas przejazdu pomiędzy stolicą a $|i$ -tym miastem). Dodatkowo, pomiędzy każdymi dwoma sąsiednimi miastami na okręgu istnieje dwukierunkowe połączenie ( $b i$ oznacza czas przejazdu pomiędzy $i$ -tym miastem a miastem sąsiadującym z prawej strony). Naszym zadaniem jest zaplanowanie podróży po Bajtocji. W tym celu musimy wybrać miasto, z którego wyruszymy oraz miasta, które odwiedzimy. Podróż musi zaczynać się i kończyć w tym samym mieście. Każda droga oraz każde miasto (poza miastem, w którym zaczynamy i kończymy podróż) może zostać odwiedzone co najwyżej raz. Ile czasu potrwa najdłuższa taka podróż?

Naszym zadaniem, w terminologii grafowej, jest znalezienie cyklu o największej sumie wag krawędzi. Rozważmy dwa przypadki:

do cyklu nie należy wierzchołek 0 - wówczas mamy tylko jedną możliwość wyboru cyklu, którego suma wag krawędzi wynosi: $| b1 +b2 + ...,bn;$
do cyklu należy wierzchołek 0 - ten przypadek zostanie dokładnie opisany w dalszej części rozwiązania.

Rozwiązanie $|O$
Rozważamy przypadek, kiedy stolica należy do cyklu. W tym przypadku dokładnie dwie krawędzie incydentne ze stolicą należą do cyklu. Zauważmy, że dla ustalonych krawędzi incydentnych ze stolicą łatwo znaleźć najdłuższy cykl. Załóżmy, że do cyklu należą krawędzie: $(0,i)$ oraz $(0, j)$ dla $|i, j ∈[1;n]$ i $i < j.$ Wówczas istnieją dokładnie dwa cykle zawierające obie te krawędzi:

$C$ - zakładamy, że od $i$ -tego wierzchołka poruszamy się w lewo,
$Cp$ - zakładamy, że od $i |$ -tego wierzchołka poruszamy się w prawo.

Suma wag krawędzi cyklu $C |$ wynosi:

Wl = ai + bi− 1 + ...+ b1 + bn + ...+ b j + a j,

zaś suma wag krawędzi cyklu $|Cp$ wynosi:

Wp = ai +bi +...+ b j−1 + a j.

Zatem dla ustalonych krawędzi incydentnych ze stolicą (krawędzi do wierzchołków $i$ oraz $| j$ ) wynikiem jest $|max(Wl,Wp).$

Aby znaleźć cykl o największej sumie wag krawędzi, wystarczy rozpatrzyć każdą parę krawędzi incydentnych ze stolicą. Dla każdej takiej pary należy obliczyć wynik i spośród otrzymanych wyników wybrać maksimum. W ten sposób otrzymujemy rozwiązanie, które działa w czasie $|O(n$

Rozwiązanie $|O$
Zauważmy, że możemy w czasie stałym obliczać sumę wag krawędzi na spójnym fragmencie obwodu przy wykorzystaniu sum prefiksowych. Wówczas otrzymujemy rozwiązanie, które działa w czasie $O(n2).$

Rozwiązanie $|O$
Ustawmy wierzchołki, które znajdują się na obwodzie, w ciąg (jeden za drugim) oraz zduplikujmy otrzymany ciąg.

Niech $|Si$ oznacza odległość od wierzchołka numer $1$ do kolejnych kopii stolicy, dokładnie:

⎧⎪ i− 1 Si = ⎪⎨ ai + P j 1b j dla 1⩽ i⩽ n, ⎪⎪⎩ ai− n + Pn j 1b j + Pi− j 1 1−nb j dla n < i⩽ 2n.

Dla każdego całkowitego $i ∈[1;n]$ znajdujemy najdłuższy cykl, który zawiera krawędź $(0,i).$ Zauważmy, że długość tego cyklu wynosi: $| S j− Si + ai,$ dla takiego największego $| S j,$ że $| j ∈[i + 1;i + n− 1].$ Znalezienie największej takiej wartości w ciągu $|S$ można zrealizować drzewem przedziałowym (dlaczego?). Spośród wyników obliczonych dla każdego $|i∈[1;n]$ wybieramy największy. W ten sposób otrzymujemy rozwiązanie, które działa w czasie $| O(n$