Przeskocz do treści

Delta mi!

Loading

Informatyczny kącik olimpijski

Świąteczny łańcuch

Tomasz Idziaszek

o artykule ...

  • Publikacja w Delcie: październik 2016
  • Publikacja elektroniczna: 2 października 2016
  • Wersja do druku [application/pdf]: (57 KB)

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

obrazek

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.

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.

obrazek

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.

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.

obrazek

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

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).