1 00:00:21,937 --> 00:00:26,612 Etyka, Hedge i Octavia stoją na skraju jaru bez dna. 2 00:00:26,612 --> 00:00:29,302 To jedyne, co dzieli ich od wieży, 3 00:00:29,302 --> 00:00:32,950 która mieści drugi z trzech potężnych artefaktów. 4 00:00:32,950 --> 00:00:37,930 Mają tylko chwilę, by do niej dotrzeć przed powrotem straży. 5 00:00:37,930 --> 00:00:42,635 Z prawie pustym zbiornikiem paliwa Hedge nie może zabrać Etyki na drugą stronę, 6 00:00:42,635 --> 00:00:46,265 jedyną opcją jest budowa mostu. 7 00:00:46,265 --> 00:00:50,920 Na szczęście unoszące się nieopodal stosy kamieni to elementy mostu. 8 00:00:50,920 --> 00:00:54,946 Wynalazła je Octavia i nazwała wiszącymi kamieniami. 9 00:00:54,946 --> 00:00:57,498 Za pomocą energii aktywuj stos, 10 00:00:57,498 --> 00:01:02,014 a same ułożą się nad jarem z każdym krokiem Etyki. 11 00:01:02,014 --> 00:01:05,592 Jest oczywiście pewien haczyk. 12 00:01:05,592 --> 00:01:10,251 Wiszące kamienie są stabilne jedynie, gdy są całkowicie symetryczne. 13 00:01:10,251 --> 00:01:12,511 Co oznacza, że muszą stworzyć sekwencję, 14 00:01:12,511 --> 00:01:16,774 która jest taka sama z przodu i z tyłu. 15 00:01:16,774 --> 00:01:18,944 Pierwszy blok ze sterty jest losowy, 16 00:01:18,944 --> 00:01:22,604 ale kolejne nakładają się na siebie, zachowując układ palindromu 17 00:01:22,604 --> 00:01:23,894 jeśli się da. 18 00:01:23,894 --> 00:01:26,774 Jeśli dotrą tam, gdzie palindrom nie jest możliwy, 19 00:01:26,774 --> 00:01:28,325 most się zawali, 20 00:01:28,325 --> 00:01:31,814 a ten, kto na nim stoi, spadnie do jaru. 21 00:01:31,814 --> 00:01:33,452 Spójrzmy na przykład. 22 00:01:33,452 --> 00:01:35,912 Ten stos stałby się stabilny. 23 00:01:35,912 --> 00:01:38,912 Najpierw pozycję zajmują bloki A. 24 00:01:38,912 --> 00:01:39,982 Potem B. 25 00:01:39,982 --> 00:01:43,672 Na końcu blok C usadowiłby się pomiędzy dwoma B. 26 00:01:43,672 --> 00:01:47,122 Załóżmy jednak, że jest jeszcze jeden blok A. 27 00:01:47,122 --> 00:01:50,242 Najpierw rozkładają się dwa bloki A, potem B, 28 00:01:50,242 --> 00:01:53,612 ale w ten sposób bloki A i C nie mają gdzie się podziać, 29 00:01:53,612 --> 00:01:56,072 więc całość się rozpada. 30 00:01:56,072 --> 00:02:00,742 Dzięki Węzłowi Mocy Hedge może aktywować pojedynczy stos bloków. 31 00:02:00,742 --> 00:02:05,076 Jaką instrukcję powinna dać Etyka, by Hedge sprawnie odnalazł 32 00:02:05,076 --> 00:02:08,127 i uruchomił stabilny stos palindromiczny? 33 00:02:08,127 --> 00:02:18,097 Zatrzymaj, by znaleźć rozwiązanie. 34 00:02:18,097 --> 00:02:23,558 Przykłady palindromów to ANNA, RACECAR czy MADAM IM ADAM. 35 00:02:23,558 --> 00:02:27,288 Liczenie, jak często dana litera pojawia się w palindromie, 36 00:02:27,288 --> 00:02:29,820 ujawni przydatny wzorzec. 37 00:02:29,820 --> 00:02:34,651 Zatrzymaj, by znaleźć rozwiązanie. 38 00:02:34,651 --> 00:02:38,141 Spróbujmy najpierw rozwiązania naiwnego. 39 00:02:38,141 --> 00:02:42,849 Rozwiązanie naiwne to podejście proste, "na siłę", które nie jest zoptymalizowane, 40 00:02:42,849 --> 00:02:44,829 ale wykona zadanie. 41 00:02:44,829 --> 00:02:48,320 Rozwiązania naiwne przydają się do analizowania problemu 42 00:02:48,320 --> 00:02:51,754 i jako podwaliny dla lepszych rozwiązań. 43 00:02:51,754 --> 00:02:55,524 W tym przypadku naiwnym rozwiązaniem jest budowa stosu bloków 44 00:02:55,524 --> 00:02:57,714 i próba wszystkich możliwych kombinacji, 45 00:02:57,714 --> 00:03:01,751 by znaleźć palindrom czytając każdą wprzód i w tył. 46 00:03:01,751 --> 00:03:03,231 Niestety to podejście 47 00:03:03,231 --> 00:03:05,724 zajęłoby ogromnie dużo czasu. 48 00:03:05,724 --> 00:03:08,574 Gdyby Hedge próbował jednej kombinacji na sekundę, 49 00:03:08,574 --> 00:03:13,772 stos zaledwie 10 różnych bloków zająłby mu 42 dni. 50 00:03:13,772 --> 00:03:17,602 To dlatego, że całkowity czas to silnia 51 00:03:17,602 --> 00:03:19,744 liczby dostępnych bloków. 52 00:03:19,744 --> 00:03:23,344 10 bloków to ponad 3 miliony kombinacji. 53 00:03:23,344 --> 00:03:27,624 Rozwiązanie naiwne pokazuje, że potrzeba znacznie szybszego sposobu, 54 00:03:27,624 --> 00:03:31,217 by sprawdzić czy dany stos może utworzyć palindrom. 55 00:03:31,217 --> 00:03:35,933 Po pierwsze, intuicja podpowiada, że stos 10 różnych bloków 56 00:03:35,933 --> 00:03:37,353 nigdy nie utworzy palindromu. 57 00:03:37,353 --> 00:03:38,143 Dlaczego? 58 00:03:38,143 --> 00:03:41,064 Pierwszy i ostatni blok nie będą identyczne, 59 00:03:41,064 --> 00:03:43,424 jeśli nie ma dwóch takich samych bloków. 60 00:03:43,424 --> 00:03:48,436 Kiedy więc dana sekwencja utworzy palindrom? 61 00:03:48,436 --> 00:03:52,916 Jednym ze sposobów, by to ustalić jest analiza istniejących palindromów. 62 00:03:52,916 --> 00:03:56,170 W ANNA są 2 A, 2 N. 63 00:03:56,170 --> 00:04:01,056 W słowie RACECAR mamy 2 R, 2 A, 2C i 1 E. 64 00:04:01,056 --> 00:04:07,786 Zwrot MADAM IM ADAM ma 4 M, 4 A, 2 D i 1 I. 65 00:04:07,786 --> 00:04:10,926 Schemat ten pokazuje, że większość liter pojawia się 66 00:04:10,926 --> 00:04:12,700 parzystą liczbę razy 67 00:04:12,700 --> 00:04:15,980 i najwyżej 1 pojawia się tylko raz. 68 00:04:15,980 --> 00:04:17,090 Czy to wystarczy? 69 00:04:17,090 --> 00:04:20,350 Co by było gdyby słowo RACECAR miało 3 E zamiast 1? 70 00:04:20,350 --> 00:04:24,060 Można by dodać E na każdym z końców i nadal utworzyć palindrom, 71 00:04:24,060 --> 00:04:25,900 więc 3 jest ok. 72 00:04:25,900 --> 00:04:31,964 Ale jeśli będziemy mieć 3 E i 3 C, ostatnie C nie będzie miało miejsca. 73 00:04:31,964 --> 00:04:34,684 Tak więc, uogólniając, 74 00:04:34,684 --> 00:04:38,780 najwyżej jedna litera może pojawić się nieparzystą ilość razy, 75 00:04:38,780 --> 00:04:41,846 reszta musi być parzysta. 76 00:04:41,846 --> 00:04:46,160 Hedge może policzyć litery w każdym stosie i uporządkować je w słownik, 77 00:04:46,160 --> 00:04:48,885 co jest schludną metodą przechowywania informacji. 78 00:04:48,885 --> 00:04:53,464 Za pomocą pętli można policzyć ile razy pojawia się nieparzysta liczba. 79 00:04:53,464 --> 00:04:58,964 Jeśli są mniej niż 2 nieparzyste liczby, stos może stworzyć palindrom. 80 00:04:58,964 --> 00:05:02,684 To podejście jest znacznie szybsze, niż rozwiązanie naiwne. 81 00:05:02,684 --> 00:05:06,104 Zamiast złożoności typu silnia, mamy złożoność liniową. 82 00:05:06,104 --> 00:05:07,674 Czasu przybywa 83 00:05:07,674 --> 00:05:10,384 proporcjonalnie do liczby bloków, którymi dysponujemy. 84 00:05:10,384 --> 00:05:14,374 Wystarczy napisać pętlę, dzięki której Hedge podejdzie do każdego stosu osobno 85 00:05:14,374 --> 00:05:18,529 i zatrzyma się, gdy znajdzie właściwy. 86 00:05:18,529 --> 00:05:19,918 Oto, co się dzieje: 87 00:05:19,918 --> 00:05:23,964 Hedge jest szybki, ale taka liczba stosów zabiera dużo czasu. 88 00:05:23,964 --> 00:05:25,320 Za dużo. 89 00:06:17,897 --> 00:06:19,577 Etyka i Hedge są bezpieczni. 90 00:06:19,577 --> 00:06:22,000 Ale Octavia nie ma tyle szczęścia.