[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:21.94,0:00:26.61,Default,,0000,0000,0000,,Etyka, Hedge i Octavia\Nstoją na skraju jaru bez dna.
Dialogue: 0,0:00:26.61,0:00:29.30,Default,,0000,0000,0000,,To jedyne, co dzieli ich od wieży,
Dialogue: 0,0:00:29.30,0:00:32.95,Default,,0000,0000,0000,,która mieści drugi z trzech\Npotężnych artefaktów.
Dialogue: 0,0:00:32.95,0:00:37.93,Default,,0000,0000,0000,,Mają tylko chwilę, by do niej dotrzeć\Nprzed powrotem straży.
Dialogue: 0,0:00:37.93,0:00:42.64,Default,,0000,0000,0000,,Z prawie pustym zbiornikiem paliwa Hedge\Nnie może zabrać Etyki na drugą stronę,
Dialogue: 0,0:00:42.64,0:00:46.26,Default,,0000,0000,0000,,jedyną opcją jest budowa mostu.
Dialogue: 0,0:00:46.26,0:00:50.92,Default,,0000,0000,0000,,Na szczęście unoszące się nieopodal\Nstosy kamieni to elementy mostu.
Dialogue: 0,0:00:50.92,0:00:54.95,Default,,0000,0000,0000,,Wynalazła je Octavia\Ni nazwała wiszącymi kamieniami.
Dialogue: 0,0:00:54.95,0:00:57.50,Default,,0000,0000,0000,,Za pomocą energii aktywuj stos,
Dialogue: 0,0:00:57.50,0:01:02.01,Default,,0000,0000,0000,,a same ułożą się nad jarem\Nz każdym krokiem Etyki.
Dialogue: 0,0:01:02.01,0:01:05.59,Default,,0000,0000,0000,,Jest oczywiście pewien haczyk.
Dialogue: 0,0:01:05.59,0:01:10.25,Default,,0000,0000,0000,,Wiszące kamienie są stabilne jedynie,\Ngdy są całkowicie symetryczne.
Dialogue: 0,0:01:10.25,0:01:12.51,Default,,0000,0000,0000,,Co oznacza, że muszą stworzyć sekwencję,
Dialogue: 0,0:01:12.51,0:01:16.77,Default,,0000,0000,0000,,która jest taka sama z przodu i z tyłu.
Dialogue: 0,0:01:16.77,0:01:18.94,Default,,0000,0000,0000,,Pierwszy blok ze sterty jest losowy,
Dialogue: 0,0:01:18.94,0:01:22.60,Default,,0000,0000,0000,,ale kolejne nakładają się na siebie,\Nzachowując układ palindromu
Dialogue: 0,0:01:22.60,0:01:23.89,Default,,0000,0000,0000,,jeśli się da.
Dialogue: 0,0:01:23.89,0:01:26.77,Default,,0000,0000,0000,,Jeśli dotrą tam, gdzie palindrom\Nnie jest możliwy,
Dialogue: 0,0:01:26.77,0:01:28.32,Default,,0000,0000,0000,,most się zawali,
Dialogue: 0,0:01:28.32,0:01:31.81,Default,,0000,0000,0000,,a ten, kto na nim stoi, spadnie do jaru.
Dialogue: 0,0:01:31.81,0:01:33.45,Default,,0000,0000,0000,,Spójrzmy na przykład.
Dialogue: 0,0:01:33.45,0:01:35.91,Default,,0000,0000,0000,,Ten stos stałby się stabilny.
Dialogue: 0,0:01:35.91,0:01:38.91,Default,,0000,0000,0000,,Najpierw pozycję zajmują bloki A.
Dialogue: 0,0:01:38.91,0:01:39.98,Default,,0000,0000,0000,,Potem B.
Dialogue: 0,0:01:39.98,0:01:43.67,Default,,0000,0000,0000,,Na końcu blok C\Nusadowiłby się pomiędzy dwoma B.
Dialogue: 0,0:01:43.67,0:01:47.12,Default,,0000,0000,0000,,Załóżmy jednak,\Nże jest jeszcze jeden blok A.
Dialogue: 0,0:01:47.12,0:01:50.24,Default,,0000,0000,0000,,Najpierw rozkładają się\Ndwa bloki A, potem B,
Dialogue: 0,0:01:50.24,0:01:53.61,Default,,0000,0000,0000,,ale w ten sposób bloki A i C\Nnie mają gdzie się podziać,
Dialogue: 0,0:01:53.61,0:01:56.07,Default,,0000,0000,0000,,więc całość się rozpada.
Dialogue: 0,0:01:56.07,0:02:00.74,Default,,0000,0000,0000,,Dzięki Węzłowi Mocy Hedge\Nmoże aktywować pojedynczy stos bloków.
Dialogue: 0,0:02:00.74,0:02:05.08,Default,,0000,0000,0000,,Jaką instrukcję powinna dać Etyka,\Nby Hedge sprawnie odnalazł
Dialogue: 0,0:02:05.08,0:02:08.13,Default,,0000,0000,0000,,i uruchomił stabilny stos palindromiczny?
Dialogue: 0,0:02:08.13,0:02:18.10,Default,,0000,0000,0000,,Zatrzymaj, by znaleźć rozwiązanie.
Dialogue: 0,0:02:18.10,0:02:23.56,Default,,0000,0000,0000,,Przykłady palindromów to ANNA,\NRACECAR czy MADAM IM ADAM.
Dialogue: 0,0:02:23.56,0:02:27.29,Default,,0000,0000,0000,,Liczenie, jak często dana litera\Npojawia się w palindromie,
Dialogue: 0,0:02:27.29,0:02:29.82,Default,,0000,0000,0000,,ujawni przydatny wzorzec.
Dialogue: 0,0:02:29.82,0:02:34.65,Default,,0000,0000,0000,,Zatrzymaj, by znaleźć rozwiązanie.
Dialogue: 0,0:02:34.65,0:02:38.14,Default,,0000,0000,0000,,Spróbujmy najpierw rozwiązania naiwnego.
Dialogue: 0,0:02:38.14,0:02:42.85,Default,,0000,0000,0000,,Rozwiązanie naiwne to podejście proste,\N"na siłę", które nie jest zoptymalizowane,
Dialogue: 0,0:02:42.85,0:02:44.83,Default,,0000,0000,0000,,ale wykona zadanie.
Dialogue: 0,0:02:44.83,0:02:48.32,Default,,0000,0000,0000,,Rozwiązania naiwne przydają się\Ndo analizowania problemu
Dialogue: 0,0:02:48.32,0:02:51.75,Default,,0000,0000,0000,,i jako podwaliny dla lepszych rozwiązań.
Dialogue: 0,0:02:51.75,0:02:55.52,Default,,0000,0000,0000,,W tym przypadku naiwnym rozwiązaniem\Njest budowa stosu bloków
Dialogue: 0,0:02:55.52,0:02:57.71,Default,,0000,0000,0000,,i próba wszystkich możliwych kombinacji,
Dialogue: 0,0:02:57.71,0:03:01.75,Default,,0000,0000,0000,,by znaleźć palindrom\Nczytając każdą wprzód i w tył.
Dialogue: 0,0:03:01.75,0:03:03.23,Default,,0000,0000,0000,,Niestety to podejście
Dialogue: 0,0:03:03.23,0:03:05.72,Default,,0000,0000,0000,,zajęłoby ogromnie dużo czasu.
Dialogue: 0,0:03:05.72,0:03:08.57,Default,,0000,0000,0000,,Gdyby Hedge próbował\Njednej kombinacji na sekundę,
Dialogue: 0,0:03:08.57,0:03:13.77,Default,,0000,0000,0000,,stos zaledwie 10 różnych bloków\Nzająłby mu 42 dni.
Dialogue: 0,0:03:13.77,0:03:17.60,Default,,0000,0000,0000,,To dlatego, że całkowity czas to silnia
Dialogue: 0,0:03:17.60,0:03:19.74,Default,,0000,0000,0000,,liczby dostępnych bloków.
Dialogue: 0,0:03:19.74,0:03:23.34,Default,,0000,0000,0000,,10 bloków to ponad 3 miliony kombinacji.
Dialogue: 0,0:03:23.34,0:03:27.62,Default,,0000,0000,0000,,Rozwiązanie naiwne pokazuje,\Nże potrzeba znacznie szybszego sposobu,
Dialogue: 0,0:03:27.62,0:03:31.22,Default,,0000,0000,0000,,by sprawdzić czy dany stos może\Nutworzyć palindrom.
Dialogue: 0,0:03:31.22,0:03:35.93,Default,,0000,0000,0000,,Po pierwsze, intuicja podpowiada,\Nże stos 10 różnych bloków
Dialogue: 0,0:03:35.93,0:03:37.35,Default,,0000,0000,0000,,nigdy nie utworzy palindromu.
Dialogue: 0,0:03:37.35,0:03:38.14,Default,,0000,0000,0000,,Dlaczego?
Dialogue: 0,0:03:38.14,0:03:41.06,Default,,0000,0000,0000,,Pierwszy i ostatni blok\Nnie będą identyczne,
Dialogue: 0,0:03:41.06,0:03:43.42,Default,,0000,0000,0000,,jeśli nie ma dwóch takich samych bloków.
Dialogue: 0,0:03:43.42,0:03:48.44,Default,,0000,0000,0000,,Kiedy więc dana sekwencja\Nutworzy palindrom?
Dialogue: 0,0:03:48.44,0:03:52.92,Default,,0000,0000,0000,,Jednym ze sposobów, by to ustalić\Njest analiza istniejących palindromów.
Dialogue: 0,0:03:52.92,0:03:56.17,Default,,0000,0000,0000,,W ANNA są 2 A, 2 N.
Dialogue: 0,0:03:56.17,0:04:01.06,Default,,0000,0000,0000,,W słowie RACECAR mamy 2 R, 2 A, 2C i 1 E.
Dialogue: 0,0:04:01.06,0:04:07.79,Default,,0000,0000,0000,,Zwrot MADAM IM ADAM\Nma 4 M, 4 A, 2 D i 1 I.
Dialogue: 0,0:04:07.79,0:04:10.93,Default,,0000,0000,0000,,Schemat ten pokazuje,\Nże większość liter pojawia się
Dialogue: 0,0:04:10.93,0:04:12.70,Default,,0000,0000,0000,,parzystą liczbę razy
Dialogue: 0,0:04:12.70,0:04:15.98,Default,,0000,0000,0000,,i najwyżej 1 pojawia się tylko raz.
Dialogue: 0,0:04:15.98,0:04:17.09,Default,,0000,0000,0000,,Czy to wystarczy?
Dialogue: 0,0:04:17.09,0:04:20.35,Default,,0000,0000,0000,,Co by było gdyby słowo RACECAR\Nmiało 3 E zamiast 1?
Dialogue: 0,0:04:20.35,0:04:24.06,Default,,0000,0000,0000,,Można by dodać E na każdym z końców\Ni nadal utworzyć palindrom,
Dialogue: 0,0:04:24.06,0:04:25.90,Default,,0000,0000,0000,,więc 3 jest ok.
Dialogue: 0,0:04:25.90,0:04:31.96,Default,,0000,0000,0000,,Ale jeśli będziemy mieć 3 E i 3 C,\Nostatnie C nie będzie miało miejsca.
Dialogue: 0,0:04:31.96,0:04:34.68,Default,,0000,0000,0000,,Tak więc, uogólniając,
Dialogue: 0,0:04:34.68,0:04:38.78,Default,,0000,0000,0000,,najwyżej jedna litera może pojawić się\Nnieparzystą ilość razy,
Dialogue: 0,0:04:38.78,0:04:41.85,Default,,0000,0000,0000,,reszta musi być parzysta.
Dialogue: 0,0:04:41.85,0:04:46.16,Default,,0000,0000,0000,,Hedge może policzyć litery w każdym stosie\Ni uporządkować je w słownik,
Dialogue: 0,0:04:46.16,0:04:48.88,Default,,0000,0000,0000,,co jest schludną metodą\Nprzechowywania informacji.
Dialogue: 0,0:04:48.88,0:04:53.46,Default,,0000,0000,0000,,Za pomocą pętli można policzyć\Nile razy pojawia się nieparzysta liczba.
Dialogue: 0,0:04:53.46,0:04:58.96,Default,,0000,0000,0000,,Jeśli są mniej niż 2 nieparzyste liczby,\Nstos może stworzyć palindrom.
Dialogue: 0,0:04:58.96,0:05:02.68,Default,,0000,0000,0000,,To podejście jest znacznie szybsze,\Nniż rozwiązanie naiwne.
Dialogue: 0,0:05:02.68,0:05:06.10,Default,,0000,0000,0000,,Zamiast złożoności typu silnia,\Nmamy złożoność liniową.
Dialogue: 0,0:05:06.10,0:05:07.67,Default,,0000,0000,0000,,Czasu przybywa
Dialogue: 0,0:05:07.67,0:05:10.38,Default,,0000,0000,0000,,proporcjonalnie do liczby bloków,\Nktórymi dysponujemy.
Dialogue: 0,0:05:10.38,0:05:14.37,Default,,0000,0000,0000,,Wystarczy napisać pętlę, dzięki której\NHedge podejdzie do każdego stosu osobno
Dialogue: 0,0:05:14.37,0:05:18.53,Default,,0000,0000,0000,,i zatrzyma się, gdy znajdzie właściwy.
Dialogue: 0,0:05:18.53,0:05:19.92,Default,,0000,0000,0000,,Oto, co się dzieje:
Dialogue: 0,0:05:19.92,0:05:23.96,Default,,0000,0000,0000,,Hedge jest szybki, ale taka liczba\Nstosów zabiera dużo czasu.
Dialogue: 0,0:05:23.96,0:05:25.32,Default,,0000,0000,0000,,Za dużo.
Dialogue: 0,0:06:17.90,0:06:19.58,Default,,0000,0000,0000,,Etyka i Hedge są bezpieczni.
Dialogue: 0,0:06:19.58,0:06:22.00,Default,,0000,0000,0000,,Ale Octavia nie ma tyle szczęścia.