Omówienie zadania Remont (III etap XXVI OI)

Specyfikacja problemu

W zadaniu mamy dane słowo \(a=a_1\ldots a_n\) nad alfabetem \(\{1,\ldots,n\}\) i musimy sprawdzić, czy da się je pokryć za pomocą parami różnych podsłów długości 2 (tzw. 2-słowami). Wystąpienia 2-słów mogą na siebie nachodzić.

Rozwiązanie wykładnicze

W najprostszym rozwiązaniu przeglądamy każdy podzbiór \(X\) zbioru pozycji \(\{1,\ldots,n-1\}\) i sprawdzamy, czy możemy w wybranych pozycjach ustawić początki szukanych 2-słów. Niech \(X=\{x_1,x_2,\ldots,x_m\}\) przy czym \(x_1 < x_2 < \dots < x_m\). Wystarczy sprawdzić, czy wszystkie pozycje słowa \(a\) są pokryte – tj. czy \(x_1=1\), \(x_m=n-1\) oraz dla każdego \(i \in \{1,\ldots,m-1\}\), \(x_{i+1}-x_i \le 2\) – oraz czy wszystkie wybrane słowa, tj. słowa postaci \(a_{x_i}a_{x_i+1}\) dla \(i \in \{1,\ldots,m\}\), są parami różne. Pierwszy z tych warunków sprawdzamy w czasie \(O(n)\). W drugim warunku wystarczy posortować słowa, co możemy wykonać w czasie \(O(n)\) algorytmem sortowania pozycyjnego (albo w czasie \(O(n \log n)\) za pomocą wbudowanego algorytmu sortowania). Ostatecznie złożoność to \(O(2^n n)\). Takie rozwiązanie pozwalało zaliczyć pierwsze podzadanie.

Szybsze rozwiązania wykładnicze

Bardziej efektywne rozwiązanie można otrzymać, przeglądając tylko podzbiory \(X\), dla których wybrane 2-słowa pokrywają wszystkie pozycje słowa. Takie zbiory spełniają warunek, że z każdych dwóch kolejnych liczb ze zbioru \(\{1,\ldots,n-1\}\) wybieramy co najmniej jedną. Można udowodnić, że takich podzbiorów jest tyle, ile wynosi \((n-1)\)-wsza liczba Fibonacciego, czyli asymptotycznie \(\phi^{n-1}\) dla \(\phi=\frac{1+\sqrt{5}}{2}\). Otrzymujemy rozwiązanie o złożoności \(O(\phi^n n) = O(1.62^n n)\).

Można jeszcze lepiej. Wystarczy dodatkowo zauważyć, że do zbioru \(X\) nie opłaca nam się nigdy wybrać trzech liczb pod rząd, gdyż wtedy wzięcie wystąpień zaczynających się na pierwszej i trzeciej z tych pozycji pokrywa ten sam zbiór pozycji w słowie, a używa jednego 2-słowa mniej. Tak więc podzbiór \(X\) możemy konstruować, rozważając kolejno liczby \(i \in \{1,\ldots,n-1\}\) i podejmując zawsze jedną z dwóch decyzji:

• \(i \in X\), \(i+1 \not\in X\)
• \(i \in X\), \(i+1 \in X\), \(i+2 \not\in X\).

Każda z powyższych decyzji ustala przynależność do zbioru \(X\) dla co najmniej dwóch kolejnych indeksów. Każdy zbiór \(X\) możemy zatem ustalić za pomocą co najwyżej \(n/2\) decyzji. Otrzymujemy rozwiązanie o złożoności \(O(2^{n/2} n)\).

Tak naprawdę to rozwiązanie ma nieco lepszą złożoność. Niech \(T(n-1)\) oznacza liczbę podzbiorów zbioru \(\{1,\ldots,n-1\}\), które możemy uzyskać za pomocą powyższych decyzji. Zachodzi równanie rekurencyjne \(T(n-1)=T(n-3)+T(n-4)\). Za pomocą ogólnych metod rozwiązywania rekurencji liniowych – wykraczających poza zakres tego omówienia – można otrzymać, że asymptotycznie \(T(n)=O(1.33^n)\), czyli nieco lepiej niż \(2^{n/2}=(\sqrt{2})^n < 1.42^n\). Zarówno poprzednie oszacowanie złożoności, jak i oszacowanie \(O(1.33^n n)\) pozwalają stwierdzić, że takie rozwiązanie powinno przechodzić pierwsze dwa podzadania.

Jeszcze inne rozwiązanie dzieli 2-słowa \(a_ia_{i+1}\) występujące w ciągu \(a\) na grupy według równości. Następnie na wszystkie możliwe sposoby wybieramy z każdej grupy po jednym wystąpieniu 2-słowa i sprawdzamy, czy te wystąpienia pokrywają całe słowo \(a\). Jaka jest złożoność takiego rozwiązania? Niech \(c_1,\ldots,c_g\) oznaczają rozmiary grup wystąpień, czyli \(c_i\) to liczba wystąpień \(i\)-tego typu 2-słowa. Wtedy rozwiązanie działa w czasie \(O(c_1 \cdots c_g \cdot n)\).

Jak duży może być ten iloczyn? Intuicyjnie widać, że im więcej małych grup rozmiaru większego niż 1, tym większy iloczyn. Okazuje się, że największy iloczyn otrzymujemy, dzieląc \(n-1\) na grupy rozmiaru 3 (przy czym pozostałe na końcu 2 lub 4 elementy pozostawiamy osobno). Można to uzasadnić w ten sposób, że jeśli \(m \ge 5\), to \((m-3) \cdot 3=3m-9 > m\). Tak więc dopóki \(m \ge 5\), opłaca się \(m\) dzielić na trójki. Na końcu pozostaje \(m \in \{0,2,4\}\). Otrzymanych trójek nie opłaca się na nic zamieniać – ani na dwójki, gdyż \(2^3 < 3^2\), ani na czwórki, które działają po prostu jak para dwójek, ani tym bardziej na liczby większe niż 4, co już zauważyliśmy powyżej.

Otrzymujemy zatem rozwiązanie o złożoności \(O(3^{n/3}n)=O(1.45^n n)\). Jest to tylko nieco gorzej niż poprzednio, więc i tak wystarczało do rozwiązania pierwszych dwóch podzadań.

Rozwiązanie oparte o 2-SAT

Wielomianowe rozwiązania zadania można otrzymać za pomocą redukcji do problemu 2-SAT (formalnie, problemu 2-CNF SAT). W problemie \(k\)-SAT mamy daną formułę logiczną w postaci koniunkcji klauzul. Każda z klauzul jest alternatywą co najwyżej \(k\) literałów, z których każdy jest zmienną lub jej negacją. Przez \(N\) oznaczamy liczbę zmiennych, a przez \(M\) liczbę alternatyw w formule. Problem 2-SAT można rozwiązać w czasie \(O(N+M)\) za pomocą algorytmu grafowego; patrz np. rozwiązanie zadania Spokojna komisja z VIII OI albo opis w języku angielskim.

Oto nasza redukcja. Dla każdego \(i \in \{1,\ldots,n-1\}\) wprowadzamy zmienną logiczną \(x_i\), która oznacza, czy wybieramy 2-słowo \(a_ia_{i+1}\). Każdą pozycję słowa \(a\) musimy pokryć 2-słowem, zatem dla każdego \(i \in \{1,\ldots,n-1\}\) tworzymy klauzulę \[x_{i} \lor x_{i+1}.\] Po drugie, każde 2-słowo możemy wybrać tylko raz, zatem dla każdych \(i,j \in \{1,\ldots,n-1\}\) takich że \(a_ia_{i+1}=a_ja_{j+1}\) tworzymy klauzulę \[x_i \Rightarrow \neg x_j.\] Implikację \(p \Rightarrow q\) da się przedstawić jako alternatywę \(\neg p \lor q\), co daje nam formułę w postaci 2-SAT.

Np. dla ciągu \(a=2,2,2,3,2,3,1\) z testu przykładowego otrzymujemy formułę:

\[(x_1 \lor x_2) \land (x_2 \lor x_3) \land (x_3 \lor x_4) \land (x_4 \lor x_5) \land (x_5 \lor x_6) \land (x_1 \Rightarrow \neg x_2) \land (x_2 \Rightarrow \neg x_1) \land (x_3 \Rightarrow \neg x_5) \land (x_5 \Rightarrow \neg x_3).\]

Uzyskana formuła zawiera \(N=n-1\) zmiennych i składa się z \(M=\Theta(n^2)\) klauzul. Formułę możemy skonstruować, jak poprzednio, za pomocą sortowania 2-słów występujących w słowie \(a\) w czasie \(O(n)\). W ten sposób otrzymujemy rozwiązanie zadania działające w czasie \(O(N+M+n)=O(n^2)\), które przechodziło pierwsze trzy podzadania.

Szybsze rozwiązanie oparte o 2-SAT

By poprawić złożoność czasową rozwiązania, musimy zmniejszyć liczbę klauzul drugiego typu, których jest w pesymistycznym przypadku kwadratowo wiele. Aby to zrobić, stworzymy zmienne i klauzule pomocnicze, dla każdego różnego 2-słowa występującego w słowie \(a\). Niech \(y_1,\ldots,y_m\) oznaczają wszystkie zmienne spośród \(x_1,\ldots,x_{n-1}\) odpowiadające wystąpieniom danego 2-słowa \(u\) w słowie \(a\). Wprowadzamy dwa typy zmiennych:

• \(p_i\) dla \(i \in \{1,\ldots,m\}\), która oznacza, że nie wybieramy żadnego z pierwszych \(i\) wystąpień 2-słowa \(u\);
• \(s_i\) dla \(i \in \{1,\ldots,m\}\), która oznacza, że nie wybieramy żadnego z wystąpień 2-słowa \(u\) od \(i\)-tego wzwyż.

Musimy się upewnić, że jeśli wybieramy jedno wystąpienie \(u\), to nie wybieramy żadnego innego. W tym celu tworzymy następujące typy implikacji:

• Jeśli wybieramy wystąpienie \(i\)-te, \(i \in \{1,\ldots,m\}\), to nie wybieramy żadnego z wystąpień \(1,\ldots,i-1\) ani \(i+1,\ldots,m\): \[(y_i \Rightarrow p_{i-1}) \land (y_i \Rightarrow s_{i+1}).\] W zapisie powyżej, implikacji z \(p_0\) i \(s_{m+1}\) po prostu nie tworzymy.
• Musimy zapisać faktyczne znaczenie zmiennych \(p_i\), \(i \in \{1,\ldots,m\}\): \[(p_i \Rightarrow \neg y_i) \land (p_i \Rightarrow p_{i-1}).\] Podobnie jak powyżej, pomijamy implikację \(p_1 \Rightarrow p_0\).
• Analogicznie musimy zapisać znaczenie zmiennych \(s_i\): \[(s_i \Rightarrow \neg y_i) \land (s_i \Rightarrow s_{i+1}).\]

Ostatecznie mamy \(N \le 3(n-1)\) zmiennych i \(M=O(n)\) klauzul. Otrzymujemy rozwiązanie wzorcowe działające w czasie \(O(N+M+n)=O(n)\).

Epilog

Można by się zastanowić, co by było, gdyby w tym zadaniu wałki były np. 3-kolorowe. Problem 3-SAT (i, ogólnie, problemy \(k\)-SAT dla większej wartości \(k\)) jest NP-zupełny, czyli bardzo możliwe, że nie da się go rozwiązać w czasie wielomianowym. To sugeruje, że naszego problemu z dłuższymi wałkami może nie dać się rozwiązać w czasie wielomianowym. W istocie, problem z wałkami o długości co najmniej 3 jest NP-zupełny, co zostało udowodnione przez Alzamel i in..