Informatyczny kącik olimpijski

Świąteczny łańcuch

Tym razem omówimy zadanie Świąteczny łańcuch, które rozwiązywali w tym roku uczestnicy drugiego etapu XXIII Olimpiady Informatycznej.

Rys. 1 Przykładowy łańcuch o $|n 10$ lampkach i czterech wymaganiach estetycznych $| 1,6,3 , 5,7,4 , 3,8,1$ oraz $|5,9,2 .$ Ostatnie wymaganie mówi, że lampki 5 i 9 muszą mieć ten sam kolor oraz lampki 6 i 10 muszą mieć ten sam kolor.

Zadanie jest następujące:

Zadanie. Należy zaprojektować łańcuch złożony z $| n$ różnokolorowych lampek, przy czym dane jest również $|m$ wymagań estetycznych, każde w postaci trójki liczb $|(ai,bi,ℓi)$ oznaczającej, że fragmenty łańcucha złożone z lampek o numerach ${ai,...,ai + ℓi− 1}$ oraz $| {bi,...,bi +ℓi− 1}$ muszą być jednakowe (Rys. 1). Łańcuch powinien być też jak najbardziej urozmaicony; innymi słowy, powinno być w nim jak najwięcej różnych kolorów lampek. Wartości $n$ i $m$ są rzędu $|106.$

Rys. 2 Graf odpowiadający wymaganiom z rysunku 1 Ma trzy spójne składowe $| 1,3,6,8,10 , 2,5,7,9$ oraz $|4 ,$ więc łańcuch może mieć co najwyżej 3 różne kolory lampek.

Rozwiązanie, za które można było zdobyć połowę punktów na konkursie, jest narzucające się. Zbudujmy graf o $|n$ wierzchołkach (ponumerowanych liczbami od 1 do $|n$ ), które odpowiadać będą kolejnym lampkom łańcucha. Teraz dla każdego wymagania estetycznego $(ai,bi,ℓi)$ łączymy krawędziami wierzchołki dla tych lampek, które muszą mieć ten sam kolor; innymi słowy, dla każdego $j = 0,1,...,ℓi− 1$ łączymy krawędzią wierzchołki $ai + j$ oraz $|b + j. i$ Zauważmy, że wszystkie lampki należące do jednej spójnej składowej grafu muszą mieć ten sam kolor. Z kolei lampki z różnych składowych mogą mieć różne kolory, więc aby zmaksymalizować liczbę kolorów w łańcuchu, należy każdej składowej przypisać inny kolor lampek (Rys. 2). To rozwiązanie działać będzie w czasie liniowym od wielkości skonstruowanego grafu. Jest zatem zbyt wolne, gdyż liczba krawędzi grafu może być bliska iloczynowi $n ⋅m,$ który może wynieść nawet $|1012.$

Zauważmy, że powyższe rozwiązanie jest wolne, jeśli istnieje dużo wymagań estetycznych o dużych długościach (wartościach $|ℓi$ ). Jednak w takim przypadku jest nieuniknione, że spora część wymagań będzie redundantna (tzn. będzie prowadziła do takich samych wymuszeń kolorów). W naszym przykładzie wymaganie $|(5,7,4)$ mówi, że fragmenty $|{5,6,7,8}$ i ${7,8,9,10}$ mają takie same kolory lampek, co może być spełnione tylko wtedy, gdy krótsze fragmenty ${5,6},{7, 8}$ oraz $|{9,10}$ mają te same kolory. Widać zatem, że wymaganie $(5,9,2)$ jest w tym przypadku zawsze spełnione. Chcielibyśmy usunąć takie redundantne wymagania. Ponadto, w przypadku wymagań o dużych długościach być może tylko część informacji z wymagania jest redundantna - w takim przypadku dobrym pomysłem mogłoby być podzielenie takiego wymagania na mniejsze kawałki.

Rys. 3 Zastąpienie wymagań dłuższych niż $2k 2$ w fazie $k 1.$

W szybszym rozwiązaniu wykorzystamy te dwa pomysły: będziemy sukcesywnie rozbijać wymagania na mniejsze i na bieżąco usuwać redundancje. Rozwiązanie będzie przebiegać w $⌊log n⌋+ 1 2$ fazach dla $k = ⌊log n ⌋,...,1,0. 2$ W fazie $|k$ -tej zakładamy, że wszystkie wymagania mają długość co najwyżej $|2k+1,$ a następnie każde wymaganie $(ai,bi,ℓi)$ o długości większej niż $|2k$ (czyli spełniającej $2k < ℓi ⩽2k+1$ ) zastępujemy dwoma wymaganiami o długości $2k$ (Rys. 3):

k k k k (ai,bi,2 ) oraz (ai +ℓi− 2 ,bi + ℓi− 2 ,2 ).

To spowoduje tymczasowy wzrost liczby wymagań, ale pozwoli nam usunąć redundancje wśród wymagań o długości $2k.$ Zbudujmy w tym celu graf $|Gk,$ w którym wierzchołki będą znów liczbami od 1 do $| n,$ ale będziemy mieli co najwyżej $| 2m$ krawędzi: dla każdego wymagania $|(ai,bi,2k)$ stworzymy krawędź łączącą wierzchołki $|ai$ oraz $|bi.$ Zauważmy teraz, że jeśli w grafie $Gk$ znajduje się cykl, to znaczy, że część wymagań o długości $2k$ daje redundantne informacje. Istotnie: cykl $| v1 v2 ... vs v1$ wymusza, że dla każdego $| k 0 ⩽ j < 2$ kolory lampek ze zbioru $|{vi + j 1⩽ i < s}$ są takie same. Jednak to samo wymuszenie uzyskujemy, jeśli usuniemy dowolne wymaganie odpowiadające krawędzi z tego cyklu. Powtarzając to rozumowanie dopóty, dopóki w grafie $| Gk$ istnieją cykle, możemy zmniejszyć zbiór wymagań długości $| k 2$ do zbioru liczącego $|n −1$ wymagań. Ten zbiór możemy znaleźć, wyznaczając dowolny las rozpinający grafu $Gk.$

Zatem na koniec fazy $|k$ -tej uzyskamy równoważny zbiór wymagań zawierający co najwyżej $m + n$ wymagań długości co najwyżej $|2k.$ Pojedynczą fazę możemy zaimplementować w czasie $|O(n + m).$ Tak więc po fazie $| k = 0$ uzyskamy równoważny zbiór $| m + n$ wymagań, z których każde jest długości 1. Dla takiego zbioru nasze pierwotne rozwiązanie zadziała w czasie liniowym. Ostatecznie złożoność czasowa algorytmu wyniesie $O((n +m) log n),$ a pamięciowa $|O(n + m).$