Kolorowanka

Kontynuując wątek fajnych zadań na UVa Online Judge, tym razem zajmiemy się kolorowaniem szachownicy. No, pewnie brzmi to trochę niepoważnie: w końcu kto widział szachownicę, która nie byłaby już pokolorowana 🙂 Tym niemniej zadanie jest jak najbardziej na serio. Może już na samym początku przyznam się, że w rozwiązaniu użyjemy skojarzeń. W problemach, których rozwiązanie sprowadza się znalezienia skojarzenia/przepływu/cyrkulacji, zwykle najtrudniejsze jest zgadnięcie wystarczająco chytrego sposobu konstrukcji sieci, ale w tym przypadku cała trudność będzie polegać na czymś zupełnie innym.

Naszym celem jest pomalowanie pól szachownicy n\times n. Każdemu z pól powinniśmy przyporządkować jeden z n kolorów tak, aby kolory w żadnym wierszu ani żadnej kolumnie nie powtarzały się. Dodatkowo utrudniamy sobie życie mówiąc, że część z pól jest już pokolorowana, a dokładniej: otrzymujemy informację o kolorach wszystkich pól w lewym górnym fragmencie o rozmiarze R \times C. Autor co prawda obiecuje, że podany fragment zawsze będzie prawidłowo pomalowany, czyli kolory w wierszach i kolumnach nie będą się powtarzać (no, choć kto by mu tam wierzył), ale uzupełnienie ich do pokolorowanie do całej planszy może okazać się niemożliwe. W takim przypadku należy z całą stanowczością wypisać NIE.

Na początku zauważmy, że jeśli R=C=0, zadanie jest wręcz trywialne. W pierwszym wierszu wpisujemy 1,2,3,\ldots,n, a w każdym kolejnym kopiujemy poprzedni przesunięty cyklicznie o jedną pozycję. Ha.

Jeśli C=n, zadanie nie jest już trywialne, ale.. nie jest też trudne. Spróbujmy uzupełnić kolejny wiersz, czyli zwiększyć R o jeden. Co prawda można by się obawiać, że kiepski wybór jednego wiersza, choć lokalnie poprawny, utrudni nam życie dużo później, ale na szczęście wcale tak nie jest. Inaczej mówiąc, udowodnimy następujący lemat.

Lemat 1. Jeśli wszystkie pola w pierwszych R<n wierszach są pokolorowane w taki sposób, że kolory w żadnym wierszu i żadnej kolumnie nie powtarzają się, pokolorowanie można rozszerzyć do R+1 wierszy.

Dowód. Przyjrzyjmy się warunkom, które muszą spełniać kolory pól w kolejnym wierszu. Dla i-tego z nich mamy zbiór C(i) kolorów, które nie zostały jeszcze wykorzystane w danej kolumnie, przy czym wszystkie zbiory mają taką samą moc n-R, oraz każdy kolor c występuje w dokładnie n-R z nich. Chcemy wybrać x_i \in C(i) tak, aby x_i \neq x_j dla i\neq j. Dość łatwo dostrzec w tym momencie, że tak naprawdę chodzi nam o znalezienie pełnego skojarzenia w grafie dwudzielnym, w którym tworzymy jeden wierzchołek u_i dla każdego pola w kolejnym wierszu i jeden wierzchołek v_c dla każdego z n kolorów, a następnie łączymy u_i z v_c dla każdego c\in C(i), na przykład tak jak na poniższej ilustracji.

kolorowanka-graf

Co na pierwszy rzut oka może się wydawać dość zaskakujące, w tak skonstruowanym grafie zawsze można znaleźć pełne skojarzenie! Wynika to z twierdzenia Halla. Wybierając kolory w kolejnym wierszu zgodnie ze znalezionym skojarzeniem, dostajemy prawidłowe pokolorowanie pierwszych R+1 wierszy.

No, to było dość łatwe, prawda? Skoro tak, to może podobne rozumowanie dałoby się zastosować do rozwiązania całego zadania? Spróbujmy!

Lemat 2. Jeśli wszystkie pola w lewym górnym fragmencie o rozmiarach R\times C, C<n są pokolorowane w taki sposób, że kolory w żadnym wierszu i żadnej kolumnie nie powtarzają się, pokolorowanie można rozszerzyć do wszystkich pól w lewym górnym fragmencie o rozmiarach R\times C+1.

Dowód. Dla j-tego pola w kolejnej kolumnie, której początkowy fragment długości R chcemy pokolorować, mamy zbiór C(j) kolorów, które nie zostały jeszcze wykorzystane w danym wierszu. Wszystkie zbiory mają taką samą moc n-C, ale czy dalej jest tak, że każdy kolor występuje w tylu samych z nich? Niestety, nie zawsze…

…ale tak naprawdę wystarczy nam, że każdy kolor występuje w co najwyżej n-C zbiorach, czyli tak naprawdę, że do tej pory został użyty przynajmniej R+C-n razy. Jeśli faktycznie tak jest, każdy lewy wierzchołek ma stopień n-C, a każdy prawy co najwyżej n-C, a więc znów z twierdzenia Halla dostajemy pełne skojarzenie (choć tym razem pełne oznacza tylko tyle, że skojarzone są wszystkie lewe wierzchołki), a z niego prawidłowe pokolorowanie większego fragmentu R \times C+1.

Co jednak, jeśli jakiś kolor został użyty mniej niż R+C-n razy? Taka sytuacja jest w gruncie rzeczy dość prosta, a mianowicie nie da się rozszerzyć aktualnego pokolorowania. Faktycznie, takiego koloru możemy użyć jeszcze co najwyżej n-R + n-C razy, czyli niezależnie jak mocno będziemy się starać, nie użyjemy go n razy w pokolorowaniu całej planszy. A, nie da się ukryć, jest to konieczne.

Nie jest to jeszcze koniec dowodu. Może się bowiem zdarzyć, że co prawda wszystkie kolory były użyte dostatecznie wiele razy w początkowym fragmencie, ale nie jest to prawdą po rozszerzeniu pokolorowania. Ab uniknąć takiej sytuacji wystarczy zapewnić, że użyjemy każdego koloru, który występował do tej pory dokładnie R-C-n razy. Inaczej mówiąc, nasze skojarzenie powinno kojarzyć wszystkie prawe wierzchołki o stopniu równym n-C. Czy jest to możliwe? Pewnie! Na pewno istnieje jakieś skojarzenie, który kojarzy wszystkie takie wierzchołki (znów korzystamy tutaj z twierdzenia Halla). Takie skojarzenie niekoniecznie musi być pełne, ale możemy je do takiego rozszerzyć.

Udowodniliśmy więc następujący lemat.

Lemat 2′ (tym razem poprawny). Jeśli wszystkie pola w lewym górnym fragmencie o rozmiarach R\times C, C<n są pokolorowane w taki sposób, że kolory w żadnym wierszu i żadnej kolumnie nie powtarzają się, oraz każdy kolor został użyty przynajmniej R+C-n razy, pokolorowanie można rozszerzyć do wszystkich pól w lewym górnym fragmencie o rozmiarach R\times C+1.

W zasadzie daje nam to efektywne rozwiązanie całego zadania. Na poczatku sprawdzamy, czy każdy kolor występuje w podanym częsciowym pokolorowaniu dostatecznie wiele razy. Jeśli tak, używamy n-C razy lematu 2′, a potem n-R razy lematu 1. W każdym z nich musimy tylko skonstruować najliczniejsze skojarzenie w grafie dwudzielnym (no, choć w przypadku lematu 2′ musi być to skojarzenie, które dodatkowo nasyca pewne wskazane wierzchołki), co bez większych problemów może byc wykonane w czasie \mathcal{O}(n^3). Co w zasadzie wystarcza do rozwiązania zadania, ale pozostawia pewien niedosyt. Ciężko uwierzyć, że \mathcal{O}(n^4) to najlepsza możliwość złożoność dla tak ładnego problemu.

Zacznim zabierzemy się do zbijania czasu działania, przyjrzyjmy się jeszcze raz lematowi 2′. Dość niepokojące może się wydawać to, że byliśmy zmuszeni nałożyć dodatkowy warunek na znajdowane tam skojarzenia. Można jednak popatrzeć na całą procedurę w trochę inny sposób: znajdowanie kolejnych skojarzeń to nic innego, jak kolorowanie krawędziowe! Inaczej mówiąc, dla danego fragmentu R\times C konstruujemy w opisany wyżej sposób graf dwudzielny, sprawdzamy, czy stopnie wierzchołków po prawej stronie nie przekraczają n-C, a następnie znajdujemy w nim n-C rozłączne skojarzenia, które w sumie pokrywają cały zbiór krawędzi. To, że stopnie prawych wierzchołków mogą być różne, jest odrobinę niewygodne. Zauważmy jednak, że zawsze możemy dorzucić n-R wirtualnych lewe wierzchołków, które połączymy (jakkolwiek) z prawymi, których stopnie są mniejsze niż n-C. Kolorowanie krawędziowe otrzymanego grafu w oczywisty sposób daje nam kolorowanie tego pierwotnego. Co więcej, nowy graf jest regularny: stopien każdego wierzchołka jest równy dokładnie n-C (czyli z twierdzenia Halla od razu wynika, że można go pokolorować krawędziowo n-C kolorami). Po bliższym przyjrzeniu się procedurze z lematu 1, wykonywane tam operacje to też nic innego jak kolorowanie krawędziowe regularnego grafu dwudzielnego!

Fajnie. Czyli tak naprawdę możemy zapomnieć o oryginalnym problemie i skoncentrować się na kolorowaniu krawędziowym d-regularnego grafu dwudzielnego na n wierzchołkach. Wiemy już, że łatwo osiągnąć tutaj złożoność \mathcal{O}(d nm)=\mathcal{O}(d^2n^2) aplikując n razy najprostszy algorytm znajdujący pełne skojarzenie w grafie dwudzielnym. No, pewnie można by nawet użyć trochę szybszego algogrytmu Hopcrofta-Karpa, i osiągnąć czas \mathcal{O}(dn^{2.5}). Spróbujemy jednak trochę szybciej.

Załóżmy, że mieliśmy szczęście, i nasze d jest parzyste. Co z tego wynika? No, wszystkie wierzchołki w naszym grafie mają wtedy parzyste stopnie, a więc… uwaga… istnieje w nim cykl Eulera. Czyli tak naprawdę można rozbić pierwotny d-regularny graf na dwa \frac{d}{2}-regularne! Kolorowanie krawędziowe tych mniejszych w oczywisty sposób daje nam szukane rozwiązanie. No dobra, ale co jeśli d nie jest parzyste?

Wtedy znajdujemy jedno pełne skojarzenie i wyrzucamy je z grafu. W ten sposób zmniejszymy d o jeden, czyli stanie się ono parzyste, i będziemy mogli zastosowac sztuczkę z cyklem Eulera. Jest to właściwie cały algorytm. Pozostaje oszacować jego czas działania. Pamiętając, że skojarzenie w d-regularnym grafie dwudzielnym możemy (prosto) skonstruować w czasie \mathcal{O}(dn^2), a cykl Eulera można znaleźć w czasie liniowym, otrzymujemy następującą rekurencję:

\begin{array}{rcl} T(n,1) & = & \mathcal{O}(n) \\ T(n,2d) & = & 2T(n,d)+\mathcal{O}(nd) \\ T(n,2d+1) & = & 2T(n,d)+\mathcal{O}(dn^2) \end{array}

która rozwiązuje się do \mathcal{O}(n^2d\log d)=\mathcal{O}(n^3\log n). Jeśli do znajdowania skojarzenia zastosujemy szybszy algorytm o złożoności \mathcal{O}(dn^{1.5}), cały czas działania spadnie do \mathcal{O}(n^{1.5}d\log d)=\mathcal{O}(n^{2.5} \log n). Czy można lepiej? Można! Otóż okazuje się, że w regularnych grafach dwudzielnych pełnych skojarzeń można szukać dużo, dużo szybciej. A nawet w czasie liniowym (!). Jest to jednak dość skomplikowane, spróbujemy więc inaczej.

Zauważmy, że jeśli tylko d nie jest zbyt duże, czyli R i C są bliskie n, powyższe rozwiązanie działa w czasie dość bliskim \mathcal{O}(n^2), czyli liniowym względem rozmiaru danych wejściowych. A jeśli d jest duże.. no właśnie co wtedy? Można odnieść wrażenie, że duża liczba krawędzi tylko ułatwia znalezienie skojarzenia. Co ciekawe, w pewnym sensie rzeczywiście tak jest.

Pokażemy, że skojarzenie w dowolnym d-regularnym grafie dwudzielnym może być znalezione w czasie \mathcal{O}(nd + n^{1.5}\log d).

Lemat 3. Dla dowolnego d-regularnego grafu dwudzielnego \left\langle V,E\right\rangle można skonstruować w czasie \mathcal{O}(nd) nowy graf dwudzielny \left\langle V,E'\right\rangle taki, że |E'| \leq n\log d, E' \subseteq E, w którym na pewno istnieje pełne skojarzenie.

Dowód. Będziemy stopniowo przerabiać E w kolejnych fazach. Na dobry początek każdej z oryginalnych krawędzi przyporządkowujemy wagę 1. W i-tej fazie patrzymy się na wszystkie krawędzie o wadze dokładnie 2^i. Tak długo, jak można z nich utworzyć cykl, wyrzucamy z tego cyklu co drugą krawędź, oraz podwajamy wagi pozostałych krawędzi. Widać, że suma wag przyległych do dowolnego wierzchołka nie zmienia się, czyli pozostaje równa d. Ponadto, po zakończeniu i-tej fazy nie możemy mieć więcej niż 2n-1 krawędzi o wadze 2^i, czyli w końcowym grafie jest ich nie więcej niż (2n-1)\log d. Ekstra. Ale ten końcowy graf ma wagi na krawędziach, co wydaje się dość dziwaczne. O tych wagch możemy myśleć jako o krotnościach krawędzi, co od razu daje nam (z twierdzenia Halla), że w końcowym grafie na pewno istnieje pełne skojarzenie. Teraz wystarczy już tylko zauważyć, że takie skojarzenie nie może przecież użyć więcej niż jednej krawędzi łączącej tą samą parę wierzchołków, czyli pełne skojarzenie istnieje też w grafie, który otrzymamy z końcowego po zignorowaniu wag.

Pozostaje jeszcze uważne przyjrzeć się złożoności całej procedury. Przy odrobinie zawziętości wykrywanie i usuwanie cykli można wykonać w czasie proporcjonalnym do liczby krawędzi. W i-tej fazie nie może ich być więcej niż \frac{nd}{2^i}, skąd otrzymujemy, że czas działania całej redukcji jest tak naprawdę liniowy. Lub, jeśli ktoś tak woli, \mathcal{O}(nd).

Łącząc powyższy lemat z algorytmem Hopcrofta-Karpa otrzymamy, że pełne skojarzenie w d-regularnym grafie dwudzielnym może być skonstruowane w czasie \mathcal{O}(nd+n^{1.5}\log d). Wydaje się to fajne, ale niestety nie zawsze jest użyteczne. Tym niemniej, jest przydatne, gdy nasze d jest dość duże.

Teraz wypada jeszcze raz przyjrzeć się wspomnianej wcześniej rekurencji. Jeśli wstawimy w niej uzyskany przed chwilą czas działania.. niestety, nie będzie zbyt wesoło. Tym niemniej, możemy z niej wywnioskować, że kolorowanie krawędziowe d-regularnego grafu dwudzielnego można zredukować do kolorowania \frac{d}{d'} różnych d'-regularnych grafów dwudzielnych w czasie \mathcal{O}(nd'\log\frac{d}{d'}+n^{1.5}\frac{d}{d'}\log d). Wybierając d'=n^{0.5} otrzymamy więc, że w czasie \mathcal{O}(n^2\log n) zredukujemy oryginalny problem do kolorowania pewnej liczby regularnych grafów dwudzielnych (na tym samym zbiorze wierzchołków) stopnia d'\leq n^{0.5}. Ale czy powinniśmy się z tego cieszyć?

Powinniśmy! Okazuje się to bowiem być dość łatwe, jeśli przypomnimy sobie o sztuczce z cyklem Eulera. Tak naprawdę pozwala nam ona znaleźć kolorowanie grafu, który jest 2^k regularny, w czasie \mathcal{O}(n 2^k k). Czyli dość szybko. No, oczywiście d' nie musi być potęgą dwójki. Przetwórzmy więc pierwszy z naszych grafów w czasie \mathcal{O}(n^{1.5}d'\log d')=\mathcal{O}(n^2\log n), otrzymując d' skojarzeń. Teraz możemy dorzucić do kolejnego z grafów tyle z tych skojarzeń, że stanie się on 2^k regularny! I przetworzyć go korzystając z rekurencyjnej dekompozycji na kolejne cykle Eulera. A następnie czynność powtórzyć (bo przecież znów dysponujemy pewną liczbą skojarzeń, a nawet mamy ich teraz jeszcze więcej, bo aż 2d'). Łatwo się przekonać, że sumaryczny czas działania to w najgorszym możliwym wypadku \mathcal{O}(n^2\log n). Czyli całkiem blisko \mathcal{O}(n^2). Nieźle, prawda? 🙂

Sztuczkę, której użyliśmy w Lemacie 3, podobno nazywa się sparsyfikacją. Już niedługo popatrzymy (uważnie) na zupełnie inne zadanie, w której też można jej użyć.

Reklamy

2 myśli nt. „Kolorowanka

  1. Megafajne to jest, czyli sparsyfikacja pojawia się jednak na contestach ;).
    W czym robisz ilustracje w stylu szachownica albo tamten graf?

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s