Etyka, Hedge i Octavia stoją na skraju jaru bez dna.
To jedyne, co dzieli ich od wieży,
która mieści drugi z trzech potężnych artefaktów.
Mają tylko chwilę, by do niej dotrzeć przed powrotem straży.
Z prawie pustym zbiornikiem paliwa Hedge nie może zabrać Etyki na drugą stronę,
jedyną opcją jest budowa mostu.
Na szczęście unoszące się nieopodal stosy kamieni to elementy mostu.
Wynalazła je Octavia i nazwała wiszącymi kamieniami.
Za pomocą energii aktywuj stos,
a same ułożą się nad jarem z każdym krokiem Etyki.
Jest oczywiście pewien haczyk.
Wiszące kamienie są stabilne jedynie, gdy są całkowicie symetryczne.
Co oznacza, że muszą stworzyć sekwencję,
która jest taka sama z przodu i z tyłu.
Pierwszy blok ze sterty jest losowy,
ale kolejne nakładają się na siebie, zachowując układ palindromu
jeśli się da.
Jeśli dotrą tam, gdzie palindrom nie jest możliwy,
most się zawali,
a ten, kto na nim stoi, spadnie do jaru.
Spójrzmy na przykład.
Ten stos stałby się stabilny.
Najpierw pozycję zajmują bloki A.
Potem B.
Na końcu blok C usadowiłby się pomiędzy dwoma B.
Załóżmy jednak, że jest jeszcze jeden blok A.
Najpierw rozkładają się dwa bloki A, potem B,
ale w ten sposób bloki A i C nie mają gdzie się podziać,
więc całość się rozpada.
Dzięki Węzłowi Mocy Hedge może aktywować pojedynczy stos bloków.
Jaką instrukcję powinna dać Etyka, by Hedge sprawnie odnalazł
i uruchomił stabilny stos palindromiczny?
Zatrzymaj, by znaleźć rozwiązanie.
Przykłady palindromów to ANNA, RACECAR czy MADAM IM ADAM.
Liczenie, jak często dana litera pojawia się w palindromie,
ujawni przydatny wzorzec.
Zatrzymaj, by znaleźć rozwiązanie.
Spróbujmy najpierw rozwiązania naiwnego.
Rozwiązanie naiwne to podejście proste, "na siłę", które nie jest zoptymalizowane,
ale wykona zadanie.
Rozwiązania naiwne przydają się do analizowania problemu
i jako podwaliny dla lepszych rozwiązań.
W tym przypadku naiwnym rozwiązaniem jest budowa stosu bloków
i próba wszystkich możliwych kombinacji,
by znaleźć palindrom czytając każdą wprzód i w tył.
Niestety to podejście
zajęłoby ogromnie dużo czasu.
Gdyby Hedge próbował jednej kombinacji na sekundę,
stos zaledwie 10 różnych bloków zająłby mu 42 dni.
To dlatego, że całkowity czas to silnia
liczby dostępnych bloków.
10 bloków to ponad 3 miliony kombinacji.
Rozwiązanie naiwne pokazuje, że potrzeba znacznie szybszego sposobu,
by sprawdzić czy dany stos może utworzyć palindrom.
Po pierwsze, intuicja podpowiada, że stos 10 różnych bloków
nigdy nie utworzy palindromu.
Dlaczego?
Pierwszy i ostatni blok nie będą identyczne,
jeśli nie ma dwóch takich samych bloków.
Kiedy więc dana sekwencja utworzy palindrom?
Jednym ze sposobów, by to ustalić jest analiza istniejących palindromów.
W ANNA są 2 A, 2 N.
W słowie RACECAR mamy 2 R, 2 A, 2C i 1 E.
Zwrot MADAM IM ADAM ma 4 M, 4 A, 2 D i 1 I.
Schemat ten pokazuje, że większość liter pojawia się
parzystą liczbę razy
i najwyżej 1 pojawia się tylko raz.
Czy to wystarczy?
Co by było gdyby słowo RACECAR miało 3 E zamiast 1?
Można by dodać E na każdym z końców i nadal utworzyć palindrom,
więc 3 jest ok.
Ale jeśli będziemy mieć 3 E i 3 C, ostatnie C nie będzie miało miejsca.
Tak więc, uogólniając,
najwyżej jedna litera może pojawić się nieparzystą ilość razy,
reszta musi być parzysta.
Hedge może policzyć litery w każdym stosie i uporządkować je w słownik,
co jest schludną metodą przechowywania informacji.
Za pomocą pętli można policzyć ile razy pojawia się nieparzysta liczba.
Jeśli są mniej niż 2 nieparzyste liczby, stos może stworzyć palindrom.
To podejście jest znacznie szybsze, niż rozwiązanie naiwne.
Zamiast złożoności typu silnia, mamy złożoność liniową.
Czasu przybywa
proporcjonalnie do liczby bloków, którymi dysponujemy.
Wystarczy napisać pętlę, dzięki której Hedge podejdzie do każdego stosu osobno
i zatrzyma się, gdy znajdzie właściwy.
Oto, co się dzieje:
Hedge jest szybki, ale taka liczba stosów zabiera dużo czasu.
Za dużo.
Etyka i Hedge są bezpieczni.
Ale Octavia nie ma tyle szczęścia.