Omówienie zadania Tomik poezji (II etap XXV OI)

Na początku uprościmy sobie trochę dane wejściowe. To, że pierwsza linijka każdego utworu jest tytułem, jest istotne tylko z punktu widzenia historyjki, podczas analizy zadania możemy traktować ją jak każdą inną. Wobec tego do długości każdego utworu dodamy 1, czyli zmienimy wartość \(a_i\) na \(a_i + 1\) dla każdego utworu.

Co więcej, jeżeli utwór będzie zawierał \(s\) lub więcej linijek (gdzie \(s\) jest liczbą linijek na stronie), to jeżeli wyrzucimy z niego \(s\) linijek, to będzie kończył się dokładnie w takim samym miejscu, tylko stronę wcześniej. A ponieważ nie interesuje nas długość tomiku w stronach, tylko dla każdego utworu interesuje nas, w którym miejscu strony on się kończył, tak więc możemy długość każdego utworu wziąć modulo \(s\). To spowoduje, że długość każdego utworu będzie liczbą z przedziału od 0 do \(s-1\).

Ponadto możemy też pozbyć się tego troszkę dziwnego przypadku utworów długości 0, bo zauważmy, że pochodzą one z utworów, które mają długość będącą wielokrotnością \(s\). Tak więc będą one zajmowały całe strony. Wobec tego możemy je wrzucić na sam początek tomiku i już więcej się nimi nie przejmować. Wobec tego długości utworów będą liczbami dodatnimi od 1 do \(s-1\).

Podzadanie 1

Omówmy rozwiązania brutalne, które będą systematycznie przeglądać przestrzeń wszystkich rozwiązań. Najprostszy do zaimplementowania algorytm będzie działał w czasie \(O(n! \cdot n)\). Po prostu będzie rozważał wszystkie permutacje uporządkowania utworów i dla każdej permutacji w czasie liniowym będzie obliczał jaki mamy wynik. Na końcu po prostu zwróci tę permutację, która da najmniej pustych linii. Zauważmy, że takie rozwiązanie już może dać nam częściowe punkty za pierwsze podzadanie.

Ponadto, dzięki posiadaniu takiego rozwiązania brutalnego, które na pewno daje prawidłowo odpowiedzi, będziemy mogli testować nasze pomysły na inne rozwiązania. To polega na tym, że generujemy sobie losowo dużą listę testów i dla każdego testu uruchamiamy nasze rozwiązanie brutalne oraz to rozwiązanie, o którym myślimy, że ma szansę działać. Następnie porównujemy odpowiedzi. Jeżeli dla dużej liczby testów nie znaleźliśmy rozbieżności w odpowiedziach, mamy szansę przypuszczać, że nasze rozwiązanie może być prawidłowe. Natomiast jeżeli taką rozbieżność znaleźliśmy, to mamy w ręku kontrprzykład, który może nam pozwolić znaleźć błąd w naszym rozumowaniu.

Inne rozwiązanie brutalne o złożoności \(O(2^n \cdot s \cdot n)\) jest oparte na programowaniu dynamicznym, w którym stanem jest maska bitowa dotychczas wykorzystanych utworów (\(2^n\) możliwości) oraz na której pozycji na ostatniej stronie, należy zacząć następny utwór (\(s\) możliwości). Następnie dla każdego takiego stanu po prostu testujemy rozszerzenie tego stanu o każdy utwór jeszcze niewykorzystany. To rozwiązanie będzie szybkie dla większych wartości \(n\), no przy czym tutaj wartość \(s\) również musi nie być za duża. No ale ponieważ liczba utworów w naszym tomiku może być rzędu nawet \(10^6\), więc potrzebujemy znaleźć o wiele szybsze rozwiązanie.

Podzadanie 2

Jeszcze raz spróbujmy dodawać nasze utwory w takiej kolejności, w jakiej występują na wejściu. Taką symulację dodawania utworów wykonać jest bardzo prosto. Będziemy musieli jedynie pamiętać liczbę \(w\) linijek tekstu, które występują na ostatniej stronie tomiku. W momencie, kiedy dodamy utwór o długości \(a\), będziemy musieli tę liczbę uaktualnić na \((w + a) \bmod s\).

Kiedy natrafimy na problem? Wtedy, kiedy ta nowa liczba wierszy będzie równa \(s - 1\) i nie przeanalizowaliśmy jeszcze wszystkich utworów. To oznacza, że została nam tylko jedna pusta linijka na ostatniej stronie i będziemy musieli ją pozostawić pustą, żeby tytuł nowego utworu nie został zapisany właśnie na ostatniej linijce.

Czyli podczas budowania kolejności utworów chcielibyśmy uniknąć sytuacji, kiedy po dodaniu utworu dostajemy \(w = s - 1\). Czy da się to zrobić? Jeżeli taka wartość \(s - 1\) pojawia się przy dodaniu utworu o długości \(a\) i ponieważ wszystkie utwory mają długość mniejszą niż \(s\) (bo uprościliśmy dane wejściowe), to nietrudno się przekonać, że jeżeli dodamy jakikolwiek utwór o długości \(a' \neq a\), to wtedy taka pusta linijka nie powstanie (reszta na pewno będzie różna niż \(s - 1\)). To oznacza, że dopóki w naszym zbiorze jeszcze nieprzydzielonych utworów mamy co najmniej dwa utwory o różnej długości, to znaczy, że będziemy mogli wybrać taki utwór, który nie spowoduje dodania pustej linijki.

Czyli algorytm może być następujący. Za każdym razem próbujemy dołożyć utwór o pewnej długości \(a\). Jeżeli dołożenie tej długości spowodowałoby powstanie pustej linijki, to wtedy wybieramy jakąś inną długość \(a'\) i to ją dokładamy. Całość powtarzamy.

Gdybyśmy byli w stanie zagwarantować, że za każdym razem mamy co najmniej dwie różne długości utworów do wyboru, to wtedy taki algorytm działałby poprawnie. Oczywiście musimy uwzględnić przypadek szczególny ostatniego utworu, bo tutaj pozostanie tylko jedna długość. Ale nie musimy się tym przejmować, bo nawet jeżeli ostatni utwór będzie się kończył wartością \(w\) równą \(s - 1\), to nam nie przeszkadza (ponieważ po nim już nic nie będziemy dodawać).

Ale jeżeli przyjrzymy się warunkowi, który występuje w drugim podzadaniu, czyli że wszystkie długości utworów są parami różne oraz nie większe niż \(s\), to okaże się, że ten warunek jest wystarczający na to, żeby nasze rozwiązanie zadziałało. Nawet po zmianie długości na \((a_i + 1) \bmod s\), te długości nadal będą parami różne, to znaczy, że nawet jeżeli pozostaną nam już w zbiorze dwie ostatnie długości, to one będą różne i na pewno będziemy mogli tak je ustawić, żeby dostać zero pustych linijek.

Wynika z tego, że w tym podzadaniu odpowiedź zawsze będzie 0 i znalezienie tej permutacji, która taką odpowiedź da, realizuje się prostym algorytmem o złożoności \(O(n)\).

Rozwiązanie wzorcowe

Niestety, w ogólności to rozwiązanie może nie działać, ponieważ może zdarzyć się sytuacja, w której w pewnym momencie zostaną nam utwory o tej samej długości. Wtedy nie będziemy mieli wyboru, będziemy musieli je umieszczać po kolei i być może to nas zmusi do wygenerowania jakiejś pustej linijki. Problem może wystąpić, gdy będziemy mieli dużo utworów o pewnej długości \(a\), ale zaczniemy tomik utworami o innych długościach, co spowoduje, że na końcu zostaniemy z niewykorzystanymi utworami o tej samej długości \(a\).

Wydaje się, że lepszym pomysłem, gdy mamy dużo utworów o tej samej długości \(a\), jest próbować zaczynać właśnie od nich, po to, żeby się ich jak najszybciej pozbyć. Moglibyśmy usprawnić nasze poprzednie rozwiązanie w taki sposób, żeby za każdym razem wybierać takie utwory, których jest aktualnie najwięcej. Możemy na kolejkę priorytetową wrzucić sobie pary \((l, a)\), gdzie \(l\) oznacza liczbę utworów o danej długości \(a\), a następnie w momencie, kiedy chcemy dodać nowy utwór, to wyciągamy z tej kolejki parę o największym \(l\) i próbujemy dodać utwór o długości \(a\).

Jeżeli się udało, to wrzucamy z powrotem na kolejkę parę \((l-1, a)\). Jeśli zaś się nie udało, a kolejka jest niepusta, to wyciągamy z niej drugą parę \((l',a')\) i wiemy, że na pewno utwór o długości \(a'\) da się dodać; czyli wrzucamy z powrotem pary \((l,a)\) oraz \((l'-1,a')\).

Natomiast jeżeli w kolejce została tylko para \((l,a)\), to już jesteśmy zmuszeni dodać \(l\) utworów długości \(a\), być może generując jakieś puste linijki.

Zauważmy, że nawet w takim ulepszonym algorytmie czasami będziemy zmuszeni do tego, żeby generować puste linijki, ponieważ istnieją testy, które wymagają niezerowej liczby pustych linijek, chociażby taki test, który będzie zawierał jedynie utwory o tej samej długości.

Taki usprawniony algorytm zadziała w czasie \(O(n \log n)\), ponieważ operacje na kolejce priorytetowej będziemy wykonywać w czasie logarytmicznym, ale dla chętnych zostawiamy zaimplementowanie tego algorytmu w czasie \(O(n + s)\) bez używania kolejki, ale za to wykorzystując sortowanie przez zliczanie.

Oczywiście wcale nie jest powiedziane, że dodanie do naszego algorytmu takiego usprawnienia spowoduje, że stanie się on poprawny. Ale w sytuacji, gdy mamy taki pomysł, warto napisać taki algorytm i przetestować go z rozwiązaniem brutalnym, które napisaliśmy wcześniej. Tutaj może czekać nas niespodzianka, bo okaże się, że nie będziemy w stanie wygenerować żadnego testu, na którym te rozwiązania się różnią. Wynika to bowiem z tego, że nasze rozwiązanie jest rzeczywiście poprawne.

Ale skąd właściwie mamy pewność, że rzeczywiście dla wszystkich możliwych testów rozwiązanie będzie dawało dobre odpowiedzi? Tutaj jest właśnie cała trudność związana z algorytmami zachłannymi (bo takiego rodzaju algorytm zapisaliśmy), że pomimo tego, że ostatecznie algorytm jest całkiem prosty, to wcale nie jest oczywiste, w jaki sposób na niego wpaść, a nie jest już absolutnie oczywiste, w jaki sposób udowodnić jego poprawność.

Reszta omówienia poświęcona jest na dowodzenie poprawności naszego rozwiązania. Co ciekawe, zrobimy to, przedstawiając zupełnie inny algorytm rozwiązujący to zadanie, a dopiero na końcu okaże się, że tak naprawdę kroki, które wykonują te dwa nasze algorytmy są identyczne. To dowiedzie poprawności również tego naszego algorytmu zachłannego.

Dowód poprawności

Przypomnijmy, że kłopot sprawiają nam testy, w których mieliśmy dużą liczbę utworów o takiej samej długości. Sformalizujemy to teraz i wprowadzimy pojęcie silnego lidera.

Element ciągu o długości \(n\) jest silnym liderem, jeśli występuje w ciągu więcej niż \(\frac{n+1}{2}\) razy. Pokażemy, że jeśli w ciągu nie ma silnego lidera, to istnieje kolejność, dla której nie generujemy żadnych pustych linijek. Przez indukcję po długości ciągu dowodzimy trochę silniejszej tezy: ,,jeśli w ciągu nie ma silnego lidera, to dla każdej liczby linijek (od 0 do \(s-2\)) już wykorzystanych na pierwszej stronie istnieje kolejność, dla której nie generujemy pustych linijek”. Dla dowodu niech \(a\) będzie liczbą linijek w utworach, która pojawia się najczęściej w ciągu. Jeśli dołożenie \(a\) nie powoduje generacji pustej linijki, to dokładamy \(a\), a resztę ciągu układamy z założenia indukcyjnego (bo nowy ciąg też nie będzie miał silnego lidera). W przeciwnym wypadku dokładamy dowolną wartość (to nie generuje nowej linijki), a po niej \(a\) (to też nie generuje) i resztę ciągu układamy z założenia indukcyjnego (nowy ciąg nie ma silnego lidera).

Pozostaje do rozważenia przypadek, gdy w ciągu jest silny lider; oznaczmy go przez \(a\). Na początek rozważmy przypadek, gdy \(NWD(a, s) \neq 1\). Wtedy dołożenie dowolnej liczby utworów \(a\) nie wygeneruje pustej linijki. Zaczynamy więc dokładać kolejne \(a\) i w pewnym momencie wystąpi sytuacja, że liczba \(a\) w pozostałej części ciągu wynosi dokładnie \(\lfloor \frac{n+1}{2} \rfloor\), czyli \(a\) właśnie przestał być silnym liderem w pozostałej części ciągu, ale żaden inny element jeszcze nim nie został. Wobec tego możemy przerwać w tym momencie i dla pozostałej części ciągu (bez silnego lidera) użyć poprzedniego algorytmu niegenerującego pustych linijek.

Teraz pozostał przypadek, gdy \(a\) i \(s\) są względnie pierwsze. Niech \(\ell\) będzie minimalną wartością, dla której \((a\cdot \ell) \bmod s = s-1\). Ustawmy reszty modulo \(s\) w ciąg \(r_0, \ldots, r_{s-1}\), gdzie \(r_i = (a\cdot (i + \ell - s + 1)) \bmod s\).

Zaczynamy z pewnego stanu, wejście do stanu \(r_{s-1}\) powoduje zwiększenie wyniku o \(1\), dołożenie \(a\) to przejście ze stanu \(r_i\) do stanu \(r_{i+1}\), dołożenie innej wartości to przejście ze stanu \(r_i\) do stanu innego niż \(r_{i+1}\) (w szczególności ze stanu \(r_{s-2}\) jest to przejście do stanu \(r_j\) dla \(j<s-2\)).

Mamy następującą obserwację: Załóżmy, że w optymalnym rozwiązaniu w pewnym momencie wchodzimy do stanu \(r_{s-1}\) dokładając wartość \(b\). Niech \(c\) będzie najwcześniejszą wartością różną od \(b\), którą dokładamy później. Jeśli taka wartość istnieje, to zamieniając w naszym rozwiązaniu miejscami \(b\) i \(c\) dostajemy nie gorsze rozwiązanie.

Z obserwacji wynika, że dopóki mamy więcej niż dwie różne wartości, to opłaca nam się jak najdłużej odwlekać wejście do stanu \(r_{s-1}\).

Rozważmy teraz następujący algorytm: dopóki mamy jakieś inne utwory niż \(a\), to idziemy utworami \(a\) w kierunku stanu \(r_{s-2}\), następnie jakimś innym utworem cofamy się. Ta faza nie generowała żadnych pustych linijek. Jeśli w którymkolwiek momencie pozostała część ciągu przestanie mieć silnego lidera, to znowu używamy do niej poprzedniego algorytmu i kończymy. W przeciwnym wypadku na koniec zostaną same utwory \(a\), dla których już nie mamy wyboru i musimy wygenerować tyle pustych linijek, ile potrzebują (w tym przypadku nieważna była kolejność, w jakiej wybieraliśmy inne utwory, bo zużyliśmy wszystkie).

Jeśli się dokładniej przyjrzymy, co się dzieje w powyższym algorytmie, to zawsze wybieraliśmy najczęstszą długość, jeśli nie generowała ona pustej linijki, a w przeciwnym przypadku – dowolną inną długość. W szczególności jest to równoważne algorytmowi zachłannemu opisanemu powyżej.