Omówienie zadania Steganografia (III etap XXXIII OI)
Treść zadania
Dany jest napis złożony z \(26\) małych liter alfabetu angielskiego o długości \(n \leq 200\,000\). Naszym zadaniem jest utworzenie tablicy bitów o rozmiarze \(k \times k\), \(k = 1000\) w taki sposób, żeby po przepermutowaniu wierszy oraz kolumn tej tablicy być w stanie odzyskać oryginalną wiadomość.
Podzadanie \(n \leq 4\)
Zauważmy, że po przepermutowaniu wierszy i kolumn tablicy nie zmienia się w niej liczba bitów ustawionych na \(1\). Potraktujmy napis jako liczbę zapisaną w systemie o podstawie \(27\) (\(26\) liter alfabetu + znak końca napisu). Zauważmy, że ta liczba nie przekracza \(27^4 < 1\,000\,000\), co pozwala nam ustawić dokładnie tyle bitów w tablicy na \(1\).
Podzadanie \(n \leq 35\)
Skorzystamy z faktu, że jeśli wiersz \(w_i\) w wyniku przepermutowania wierszy i kolumn tablicy został przeniesiony na pozycję \(j\), to wiersz \(w_i\) oryginalnej tablicy zawiera tyle samo jedynek, co wiersz \(w_j\) nowej tablicy. Możemy więc wykorzystać liczbę jedynek w wierszu do przechowania informacji, która umożliwi jego identyfikację w przepermutowanej tablicy. Korzystając z pierwszych \(35\) wierszy, zakodujemy w każdym parę: (indeks wiersza, znak), ustawiając odpowiednią liczbę bitów na \(1\). Potrzebujemy zakodować indeksy \(35\) wierszy, a liczba potrzebnych nam znaków wynosi \(27\) (\(26\) liter alfabetu oraz znak końca napisu), co daje \(35 \cdot 27 = 945\) możliwych par do zakodowania, co mieści się w limicie zapalonych bitów w wierszu (maksymalnie \(k = 1000\) bitów).
Kodowanie wiadomości
Pierwszym krokiem, który musimy wykonać, aby w pełni rozwiązać zadanie, jest zakodowanie wiadomości tekstowej w postaci ciągu bitów. Możemy w tym celu zakodować każdy znak po kolei, reprezentując litery alfabetu angielskiego jako liczby od \(1\) do \(26\). Liczba \(0\) może oznaczać koniec napisu – jeśli natrafimy na nią podczas odczytywania, to znaczy, że jest to koniec wiadomości. Do zakodowania każdego znaku będziemy potrzebować \(5\) bitów. Daje to razem \(5 \cdot n\) bitów potrzebnych do zakodowania wiadomości i wystarcza do zaliczenia podzadań, w których \(n \leq 190\,000\).
Aby uzyskać komplet punktów za zadanie, musimy zakodować napis bardziej efektywnie. Użyjemy pierwszych \(18\) bitów do zakodowania długości napisu (ponieważ \(2^{18} > 200\,000\)). Następnie będziemy grupować kolejne litery w bloki po \(4\) znaki. Każdy taki blok będziemy traktować jako liczbę zapisaną w systemie o podstawie \(26\). Aby zakodować dany blok, zamienimy odpowiadającą mu liczbę na system binarny – będziemy potrzebować do tego \(\lceil \log_2{26^4} \rceil = 19\) bitów. W ten sposób jesteśmy w stanie zakodować napis o długości \(n\) przy użyciu \(18 + \lceil \frac{n}{4} \rceil \cdot 19\) bitów, co dla \(n = 200\,000\) wynosi \(950\,018 < 980 \cdot 980\).
Co jeśli permutowane są tylko wiersze tablicy?
Aby odczytać wiadomość, musimy odzyskać kolejność wierszy. Możemy wykorzystać ostatnie \(10\) kolumn do zapisania indeksów wierszy, a na pozostałym obszarze zakodować wiadomość. Aby odzyskać wiadomość, musimy najpierw odczytać indeksy wierszy. Dzięki temu możemy przywrócić tablicę do oryginalnego stanu i odczytać zakodowaną wiadomość.
Podzadanie \(n \leq 20\,000\)
Ponownie skorzystamy z faktu, że jeśli wiersz \(w_i\) w wyniku przepermutowania wierszy i kolumn tablicy został przeniesiony na pozycję \(j\), to wiersz \(w_i\) oryginalnej tablicy zawiera tyle samo jedynek, co wiersz \(w_j\) nowej tablicy. Chcemy, aby wraz z rosnącymi indeksami wierszy rosła liczba jedynek w wierszu. Zakodujemy wiadomość, korzystając z pierwszych \(323\) wierszy i pierwszych \(333\) kolumn. Dodatkowo zakodujemy indeksy pierwszych \(333\) kolumn w wierszach o numerach od \(324\) do \(332\). Następnie dla wszystkich wierszy o numerach od \(1\) do \(332\) wypełnimy je taką liczbą jedynek, aby wraz z rosnącymi numerami wierszy rosła również liczba jedynek w wierszu. Formalnie, dla wiersza \(w_i\), niech liczba zapalonych bitów w pierwszych \(333\) polach \(w_i\) wynosi \(b_i\), wtedy należy ustawić dokładnie \(333 - b_i + i\) bitów na \(1\) w kolumnach o indeksach od \(334\) do \(1000\) w wierszu \(w_i\). Następnie uzupełnimy jeszcze wiersz o numerze \(333\) tak, żeby w pierwszych \(333\) kolumnach były wpisane zera, a w pozostałych jedynki – posłuży on do oznaczenia pierwszych \(333\) kolumn. W wierszach o numerach od \(667\) do \(1000\) wpisujemy same jedynki.
Aby odzyskać wiadomość, powinniśmy posortować wiersze według liczby jedynek w danym wierszu. Następnie przechodzimy po wszystkich kolumnach i sprawdzamy, czy w danej kolumnie w wierszu o numerze \(333\) jest wpisane \(0\) – jeśli nie, to pomijamy tę kolumnę, jeśli tak, to odczytujemy z niej indeks kolumny. W ten sposób odzyskaliśmy zarówno kolejność wierszy, jak i kolejność kolumn, w których zakodowany był napis, co pozwala bez problemu odczytać wiadomość.
Rozwiązanie wzorcowe
Użyjemy obszaru o rozmiarze \(980\times980\) do zakodowania wiadomości. Dla każdego z wierszy o numerach od \(1\) do \(990\) w kolumnach o numerach od \(991\) do \(1000\) wpiszemy indeks tego wiersza (indeksując od 1). Następnie dla każdej z kolumn o numerach od \(1\) do \(980\) w wierszach o numerach od \(981\) do \(990\) wpiszemy indeks tej kolumny (ponownie indeksujemy od 1). Dla każdego z wierszy o numerach od \(1\) do \(990\) w kolumnach o numerach od \(981\) do \(990\) wpiszemy same jedynki (każda z tych \(10\) kolumn będzie więc zawierać dokładnie \(990\) jedynek). Ostatnie \(10\) wierszy użyjemy do zakodowania pozycji \(10\) ostatnich kolumn – odpowiadających za indeksy wierszy, tak aby można było je bez problemu odnaleźć po przepermutowaniu wierszy i kolumn tablicy. W wierszu \(991\) wpiszemy zera na wszystkich pozycjach poza ostatnią kolumną, w wierszu \(992\) będą zera na wszystkich pozycjach poza ostatnimi dwiema kolumnami i tak dalej aż do ostatniego wiersza.
Program dekodujący odzyska najpierw indeksy ostatnich \(10\) wierszy z oryginalnej tablicy. Ostatnim wierszem będzie ten, który ma dokładnie \(10\) jedynek, przedostatnim ten, który ma ich dokładnie \(9\), itd. Zauważmy, że są one wyznaczone jednoznacznie, ponieważ każdy wiersz o numerze mniejszym niż \(991\) ma co najmniej \(11\) jedynek (\(10\) dodaliśmy w kolumnach od \(981\) do \(990\) oraz co najmniej jeden zapalony bit pojawia się w indeksie wiersza).
Jedyne pole wiersza \(991\) z oryginalnej tablicy, w którym wpisane jest \(1\), wyznacza ostatnią kolumnę z oryginalnej tablicy. Podobnie dwa pola z jedynkami z wiersza \(992\) wskazują nam dwie ostatnie kolumny z oryginalnej tablicy, trzy pola z jedynkami z wiersza \(993\) wskazują trzy ostatnie kolumny, itd. Stosując to rozumowanie, możemy odzyskać 10 ostatnich kolumn z oryginalnej tablicy oraz ich kolejność.
Następnie, mając odzyskane ostatnie \(10\) kolumn, jesteśmy w stanie odczytać indeksy wierszy od \(1\) do \(990\) i następnie z wierszy od \(981\) do \(990\) odczytujemy indeksy kolumn od \(1\) do \(980\) (odrzucamy \(10\) kolumn od \(981\) do \(990\), w których jest dokładnie \(990\) jedynek), co pozwala nam już odzyskać całą wiadomość.