0:00:21.937,0:00:26.612
Etyka, Hedge i Octavia[br]stoją na skraju jaru bez dna.

0:00:26.612,0:00:29.302
To jedyne, co dzieli ich od wieży,

0:00:29.302,0:00:32.950
która mieści drugi z trzech[br]potężnych artefaktów.

0:00:32.950,0:00:37.930
Mają tylko chwilę, by do niej dotrzeć[br]przed powrotem straży.

0:00:37.930,0:00:42.635
Z prawie pustym zbiornikiem paliwa Hedge[br]nie może zabrać Etyki na drugą stronę,

0:00:42.635,0:00:46.265
jedyną opcją jest budowa mostu.

0:00:46.265,0:00:50.920
Na szczęście unoszące się nieopodal[br]stosy kamieni to elementy mostu.

0:00:50.920,0:00:54.946
Wynalazła je Octavia[br]i nazwała wiszącymi kamieniami.

0:00:54.946,0:00:57.498
Stos aktywuje się za pomocą energii,

0:00:57.498,0:01:02.014
a elementy same ułożą się nad jarem[br]z każdym krokiem Etyki.

0:01:02.014,0:01:05.592
Jest oczywiście pewien haczyk.

0:01:05.592,0:01:10.251
Wiszące kamienie są stabilne jedynie,[br]gdy są całkowicie symetryczne.

0:01:10.251,0:01:12.511
Co oznacza, że muszą stworzyć sekwencję,

0:01:12.511,0:01:16.774
która jest taka sama z przodu i z tyłu.

0:01:16.774,0:01:18.944
Pierwszy blok ze sterty jest losowy,

0:01:18.944,0:01:22.604
ale kolejne nakładają się na siebie,[br]zachowując układ palindromu

0:01:22.604,0:01:23.894
jeśli się da.

0:01:23.894,0:01:26.774
Jeśli dotrą tam, gdzie palindrom[br]nie jest możliwy,

0:01:26.774,0:01:28.325
most się zawali,

0:01:28.325,0:01:31.814
a ten, kto na nim stoi, spadnie do jaru.

0:01:31.814,0:01:33.452
Spójrzmy na przykład.

0:01:33.452,0:01:35.912
Ten stos stałby się stabilny.

0:01:35.912,0:01:38.912
Najpierw pozycję zajmują bloki A.

0:01:38.912,0:01:39.982
Potem B.

0:01:39.982,0:01:43.672
Na końcu blok C[br]usadowiłby się pomiędzy dwoma B.

0:01:43.672,0:01:47.122
Załóżmy jednak,[br]że jest jeszcze jeden blok A.

0:01:47.122,0:01:50.242
Najpierw rozkładają się[br]dwa bloki A, potem B,

0:01:50.242,0:01:53.612
ale w ten sposób bloki A i C[br]nie mają gdzie się podziać,

0:01:53.612,0:01:56.072
więc całość się rozpada.

0:01:56.072,0:02:00.742
Dzięki Węzłowi Mocy Hedge[br]może aktywować pojedynczy stos bloków.

0:02:00.742,0:02:05.076
Jaką instrukcję powinna dać Etyka,[br]by Hedge sprawnie odnalazł

0:02:05.076,0:02:08.127
i uruchomił stabilny stos palindromiczny?

0:02:08.127,0:02:18.097
Zatrzymaj, by znaleźć rozwiązanie.

0:02:18.097,0:02:23.558
Przykłady palindromów to ANNA,[br]RACECAR czy MADAM IM ADAM.

0:02:23.558,0:02:27.288
Liczenie, jak często dana litera[br]pojawia się w palindromie,

0:02:27.288,0:02:29.820
ujawni przydatny wzorzec.

0:02:29.820,0:02:34.651
Zatrzymaj, by znaleźć rozwiązanie.

0:02:34.651,0:02:38.141
Spróbujmy najpierw rozwiązania naiwnego.

0:02:38.141,0:02:42.849
Rozwiązanie naiwne to podejście proste,[br]"na siłę", które nie jest zoptymalizowane,

0:02:42.849,0:02:44.829
ale wykona zadanie.

0:02:44.829,0:02:48.320
Rozwiązania naiwne przydają się[br]do analizowania problemu

0:02:48.320,0:02:51.754
i jako podwaliny dla lepszych rozwiązań.

0:02:51.754,0:02:55.524
W tym przypadku naiwnym rozwiązaniem[br]jest budowa stosu bloków

0:02:55.524,0:02:57.714
i próba wszystkich możliwych kombinacji,

0:02:57.714,0:03:01.751
by znaleźć palindrom[br]czytając każdą wprzód i w tył.

0:03:01.751,0:03:03.231
Niestety to podejście

0:03:03.231,0:03:05.724
zajęłoby ogromnie dużo czasu.

0:03:05.724,0:03:08.574
Gdyby Hedge próbował[br]jednej kombinacji na sekundę,

0:03:08.574,0:03:13.772
stos zaledwie 10 różnych bloków[br]zająłby mu 42 dni.

0:03:13.772,0:03:17.602
To dlatego, że całkowity czas to silnia

0:03:17.602,0:03:19.744
liczby dostępnych bloków.

0:03:19.744,0:03:23.344
10 bloków to ponad 3 miliony kombinacji.

0:03:23.344,0:03:27.624
Rozwiązanie naiwne pokazuje,[br]że potrzeba znacznie szybszego sposobu,

0:03:27.624,0:03:31.217
by sprawdzić czy dany stos może[br]utworzyć palindrom.

0:03:31.217,0:03:35.933
Po pierwsze, intuicja podpowiada,[br]że stos 10 różnych bloków

0:03:35.933,0:03:37.353
nigdy nie utworzy palindromu.

0:03:37.353,0:03:38.143
Dlaczego?

0:03:38.143,0:03:41.064
Pierwszy i ostatni blok[br]nie będą identyczne,

0:03:41.064,0:03:43.424
jeśli nie ma dwóch takich samych bloków.

0:03:43.424,0:03:48.436
Kiedy więc dana sekwencja[br]utworzy palindrom?

0:03:48.436,0:03:52.916
Jednym ze sposobów, by to ustalić[br]jest analiza istniejących palindromów.

0:03:52.916,0:03:56.170
W ANNA są 2 A, 2 N.

0:03:56.170,0:04:01.056
W słowie RACECAR mamy 2 R, 2 A, 2C i 1 E.

0:04:01.056,0:04:07.786
Zwrot MADAM IM ADAM[br]ma 4 M, 4 A, 2 D i 1 I.

0:04:07.786,0:04:10.926
Schemat ten pokazuje,[br]że większość liter pojawia się

0:04:10.926,0:04:12.700
parzystą liczbę razy

0:04:12.700,0:04:15.980
i najwyżej 1 pojawia się tylko raz.

0:04:15.980,0:04:17.090
Czy to wystarczy?

0:04:17.090,0:04:20.350
Co by było gdyby słowo RACECAR[br]miało 3 E zamiast 1?

0:04:20.350,0:04:24.060
Można by dodać E na każdym z końców[br]i nadal utworzyć palindrom,

0:04:24.060,0:04:25.900
więc 3 jest ok.

0:04:25.900,0:04:31.964
Ale jeśli będziemy mieć 3 E i 3 C,[br]ostatnie C nie będzie miało miejsca.

0:04:31.964,0:04:34.684
Tak więc, uogólniając,

0:04:34.684,0:04:38.780
najwyżej jedna litera może pojawić się[br]nieparzystą ilość razy,

0:04:38.780,0:04:41.846
reszta musi być parzysta.

0:04:41.846,0:04:46.160
Hedge może policzyć litery w każdym stosie[br]i uporządkować je w słownik,

0:04:46.160,0:04:48.885
co jest schludną metodą[br]przechowywania informacji.

0:04:48.885,0:04:53.464
Za pomocą pętli można policzyć[br]ile razy pojawia się nieparzysta liczba.

0:04:53.464,0:04:58.964
Jeśli są mniej niż 2 nieparzyste liczby,[br]stos może stworzyć palindrom.

0:04:58.964,0:05:02.684
To podejście jest znacznie szybsze,[br]niż rozwiązanie naiwne.

0:05:02.684,0:05:06.104
Zamiast złożoności typu silnia,[br]mamy złożoność liniową.

0:05:06.104,0:05:07.674
Czasu przybywa

0:05:07.674,0:05:10.384
proporcjonalnie do liczby bloków,[br]którymi dysponujemy.

0:05:10.384,0:05:14.374
Wystarczy napisać pętlę, dzięki której[br]Hedge podejdzie do każdego stosu osobno

0:05:14.374,0:05:18.529
i zatrzyma się, gdy znajdzie właściwy.

0:05:18.529,0:05:19.918
Oto, co się dzieje:

0:05:19.918,0:05:23.964
Hedge jest szybki, ale taka liczba[br]stosów zabiera dużo czasu.

0:05:23.964,0:05:25.320
Za dużo.

0:06:17.897,0:06:19.577
Etyka i Hedge są bezpieczni.

0:06:19.577,0:06:22.000
Ale Octavia nie ma tyle szczęścia.