Omówienie zadania Satelity (I etap XXXI OI)

Niech \(out_{i,j}\) dla \(1 \le i \le 2n, 1 \le j \le m\) oznacza ciąg, który mamy wypisać w zadaniu.

Każde z przedstawionych poniżej rozwiązań będzie opierało się na kolejnym dopisywaniu po jednej literce do każdej linijki wyjścia, aż otrzymamy rozwiązanie poprawne. Niech więc dla wygody \(col_j\) oznacza ciąg \(out_{1,j}, out_{2,j}, \ldots, out_{2n,j}\) - są to kolejne literki \(j\)-tej "kolumny" wyjścia.

Rozwiązanie jest poprawne, gdy:

Dla każdego połączenia \((v, u)\) satelity komunikują się, czyli istnieje kolumna \(c\), że \(c_v = c_u\) (istnieje takie \(1 \le j \le m\), że \(out_{v,j} = out_{u,j}\)). Jeżeli nie ma połączenia \((v, u)\) dla satelitów różnych firm, to się nie komunikują.
Satelity tej samej grupy komunikują się, czyli dla każdych \(1\le i,j\le n\) istnieje kolumna \(c\), że \(c_i = c_j\). Analogicznie dla \(n < i, j \le 2n\).
Satelity mają różne kody identyfikacyjne, czyli dla każdych \(1 \le i, j \le 2n\) istnieje kolumna \(c\), że \(c_i \ne c_j\).

Rozwiązanie o długości \(M=n+2\lceil \log_2 n\rceil\):

Najpierw zapewnimy, że dla każdego połączenia \((v, u)\) satelity komunikują się (oraz nie komunikują się gdy nie mają połączenia). Dla każdego satelity \(1 \le v \le n\) dodamy kolumnę, która wśród pierwszych \(n\) znaków ma same literki \(A\) poza \(v\)-tą literką, która ma wartość \(B\), zaś wśród drugich \(n\) znaków jest literka \(B\) na pozycji \(n+i\), gdy satelita \(n+i\) ma połączenie z satelitą \(v\), a literka \(C\) w przeciwnym przypadku.

Uzasadnienie: ponieważ literki \(A\) występują tylko wśród pierwszych \(n\) znaków oraz literki \(C\) występują tylko wśród drugich \(n\) znaków, to pary satelitów będą mieć taką samą literkę w \(j\)-tej kolumnie tylko wtedy, gdy będą to literki \(B\), czyli gdy pierwszy satelita ma numer \(j\), a drugi ma połączenie z satelitą \(j\).

Takie rozwiązanie niekoniecznie spełnia pozostałe warunki poprawnego rozwiązania. Teraz niezależnie dodamy \(\lceil \log_2 n\rceil\) kolumn, które jednocześnie sprawią, że satelity pierwszej grupy komunikują się oraz mają różne kody identyfikacyjne:

Dla każdego \(1 \le b \le \lceil\log_2 n\rceil\) dodamy kolumnę, której \(i\)-ty znak wynosi \(A\) jeżeli \(b\)-ty bit liczby \(i\) (zapisanej binarnie, numerując od zera) jest zapalony, oraz \(B\) w przeciwnym przypadku. Drugie \(n\) znaków to po prostu literki \(C\).

Uzasadnienie: gdy czytamy dodane kolumny od góry do dołu (czyli wierszami), \(i\)-ty wiersz będzie tworzyć \(i\)-tą liczbę \((1 \le i < n)\) w systemie binarnym, gdzie \(A\) oznacza bit \(1\), zaś \(B\) oznacza bit \(0\). Każde dwie różne liczby mają różną reprezentację w systemie binarnym oraz każde dwie różne liczby posiadają przynajmniej jeden wspólny bit.

Powtarzając taki algorytm dla drugiej grupy, kosztem kolejnych \(\lceil \log_2 n\rceil\) kolumn zapewnimy, że wszystkie warunki poprawnego rozwiązania zostaną spełnione.

Przykładowo, dla testu przykładowego \(0\) z treści zadania, skonstruujemy następujące wyjście (spacje zostały dodane dla rozróżnienia kolejnych faz algorytmu):

BAA BB CC

ABA AB CC

AAB BA CC

BCB CC BB

CCC CC AB

CBB CC BA

Rozwiązanie o długości \(M=n+2\):

W poprzednim rozwiązaniu najkosztowniejszą częścią było stworzenie oddzielnej kolumny ze zbiorem połączeń każdego satelity \(1 \le v \le n\). Zauważmy że gdy dwa satelity \(1 \le v, u \le n\) mają takie same połączenia do satelitów drugiej grupy, to ich kolumny można złączyć. Jeżeli wszystkie satelity mają różne zbiory połączeń, to taka optymalizacja na pierwszy rzut oka nic nie da, ale okaże się, że wtedy pozostała część algorytmu będzie wymagała mniej kolumn.

Konkretniej, zacznijmy od podzielenia satelitów \(1, 2, \dots, n\) na rozłączne zbiory \(L_1, L_2, \dots, L_l\) takie, że wszystkie satelity w \(L_i\) mają dokładnie takie same połączenia z satelitami drugiej grupy. Załóżmy też, że zbiory są posortowane nierosnąco względem ich rozmiarów, czyli \(|L_1| \ge |L_2| \ge \dots \ge |L_l|\) (będziemy korzystać przede wszystkim z założenia, że \(|L_1|\) jest największym rozmiarem zbioru). Analogicznie podzielmy satelity \(n+1, \dots, 2n\) na zbiory \(R_1, R_2, \dots, R_r\). Załóżmy, że \(l \le r\) (jeżeli tak nie jest, to możemy zamienić pierwszą grupę satelitów z drugą grupą).

Wtedy wystarczy na początku dodać \(l\) kolumn, gdzie \(i\)-ta kolumna spełnia: wśród pierwszych \(n\) znaków znajduje się literka \(B\) na pozycji \(v\) gdy \(v \in L_i\) oraz literka \(A\) w przeciwnym przypadku, zaś wśród drugich \(n\) znaków jest literka \(B\) na pozycji \(n+i\), gdy satelita \(n+i\) ma połączenie z pierwszym satelitą \(L_{i,0}\) ze zbioru \(L_i\), a literka \(C\) w przeciwnym przypadku (przy czym nie ma znaczenia, czy patrzymy na połączenie satelity \(L_{i,0}\) z satelitą \(n+i\), czy innego satelity ze zbioru \(L_i\) z satelitą \(n+i\), bo wszystkie satelity \(L_i\) mają taki sam zbiór połączeń).

Teraz ponownie postąpimy analogicznie do poprzedniego rozwiązania, przy czym będziemy potrzebowali tylko \(\lceil \log_2 |L_1| \rceil\) kolumn, zamiast \(\lceil \log_2 n \rceil\). Główną obserwacją tego podejścia jest, że tej fazy algorytmu nie trzeba wykonywać na satelitach z różnych zbiorów \(L\), a wystarczy wykonać niezależnie tylko wśród satelitów w tych samych zbiorach.

Dla kolejnej, \(b\)-tej kolumny (\(1 \le b \le \lceil \log_2 |L_1| \rceil\)) postąpimy następująco: rozważmy oddzielnie zbiory \(L_i\) i z każdego takiego (jakkolwiek uporządkowanego) zbioru \(L_i\) weźmy wszystkie elementy (satelity) o takich indeksach (z zakresu od \(0\) do \(|L_i|-1\) włącznie), których \(b\)-ty bit jest zapalony. Jeżeli wzięliśmy satelitę o numerze \(v\), to \(v\)-ta literka kolumny będzie wynosić \(B\), oraz \(A\) w przeciwnym przypadku. Drugie \(n\) znaków to po prostu literki \(C\). Gdy \(|L_1| = 1\), czyli gdy \(|L_1|=|L_2|=\ldots=|L_n|=1\), to nie dodamy żadnej kolumny.

Analogicznie postępujemy z drugą grupą satelitów kosztem \(\lceil \log_2 |R_1| \rceil\) kolumn. Przy czym jeżeli \(|R_1|=1\), to taka faza nie doda żadnych kolumn, a trzeba jeszcze jakoś zezwolić na komunikację między satelitami z takiej samej grupy, więc w takim przypadku można jeszcze dodać kolumnę, która wśród pierwszych \(n\) literek ma same literki \(A\), zaś wśród drugich \(n\) literek ma same literki \(B\).

Formalny dowód poprawności takiego rozwiązania pominiemy. Znacznie łatwiej jest się przekonać co do jego poprawności, po prostu rozrysowując rozwiązanie na kartce oraz porównując fazy tego rozwiązania do analogicznych faz poprzedniego rozwiązania.

Ale za to formalnie udowodnimy, że takie rozwiązanie mieści się w limicie \(n+2\) kolumn.

Niech \(\alpha = n + 1 - l\). Zachodzi \(|L_1| + (l - 1) \le \sum |L_i| = n\), więc \(|L_1| \le \alpha\). Dla łatwiejszego przypadku \(|R_1|=1\) mamy \(m \le \lceil \log_2 \alpha \rceil + l + 1 = \lceil \log_2 \alpha \rceil + (n + 1 - \alpha) + 1 = (\lceil \log_2 \alpha \rceil - \alpha + 1) + (n + 1)\), co mieści się w limicie \(M=n+2\), ponieważ funkcja \(f(x) = x - \lceil \log_2 x \rceil - 1\) jest nieujemna.

Dla trudniejszego przypadku \(|R_1|\neq 1\) mamy \(m=\lceil \log_2 |L_1|\rceil + \lceil\log_2|R_1|\rceil + l\). Ponieważ \(|R_1|\le n+1-r\) oraz \(l\le r\), to także \(|R_1|\le\alpha\). Dlatego \(m\le 2\lceil\log_2\alpha\rceil+l = (2\lceil\log_2\alpha\rceil-\alpha)+(n+1)\).

Funkcja \(f(x)=x-2\lceil\log_2 x\rceil\) dla naturalnych \(x\) spełnia \(f(x)=-1\) dla \(x\in\{3,5\}\) oraz \(f(x)\ge 0\) dla pozostałych \(x\). To wystarcza do udowodnienia, że \(m\le n+2\).

Rozwiązanie o długości \(M=n+1\):

Poprzednie rozwiązanie mieściło się w tym limicie gdy zachodziło \(\alpha \notin \{3,5\}\). Zastanówmy się jak poprawić to rozwiązanie w przypadku \(\alpha \in \{3,5\}\). W tym przypadku nierówności opisane powyżej są równościami, a z tego można wywnioskować, że \(l=r=n+1-\alpha\) oraz \(|L_1|=\alpha, |R_1|=\alpha\), a z tego też wynika, że rozmiary zbiorów \(L_i\) oraz \(R_i\) poza \(L_1\) oraz \(R_1\) wynoszą dokładnie \(1\). W takich przypadkach można zauważyć i przeanalizować, że można złączyć dwie kolumny. Tak dokładniej, nie trzeba dodawać jednej kolumny, która odpowiada za sprawienie, aby druga grupa satelitów miała różne kody i mogła się nawzajem komunikować. Można usunąć tę odpowiadającą za \(b=1\) i zmodyfikować pierwszą kolumnę, aby spełniała obie role.