Algorytmika

W tym artykule opowiem nieco o zupełnie odmiennym od standardowego podejściu do tworzenia struktur danych ─ strukturach trwałych, a także przedstawię implementacje kilku najpopularniejszych struktur ─ stosów, drzew wyszukiwań binarnych i kolejek ─ w wersji trwałej.

W tym artykule prezentuję rozwiązania trzech zadań ze SPOJa. Wszystkie pochodzą z (dość długiego) cyklu "Answer these queries" i (mimo dość podobnie wyglądających sformułowań) wymagają połączenia kilku różnych, i to dość nietrywialnych, pomysłów. Ze względu na zróżnicowany poziom trudności lekturę polecam zarówno początkującym, jak i starym wyjadaczom.

Każdy może czasem potrzebować k-tego elementu w n-wierzchołkowym drzewie. Przedstawimy kilka sposobów, mniej lub bardziej efektywnych, jak go znaleźć. Po drodze dowiemy się dlaczego STL wcale nie jest taki fajny, jak szukać mediany i że oszczędzanie połowy pracy na każdej operacji daje świetne efekty.

Pisząc ten artykuł postanowiłem, że nie zdradzę ani jednego rozwiązania, bo odebrałbym Wam dużo radości. Nie mam ulubionego zadania, ani nie umiem opowiedzieć poruszającej historii na temat zawodów, mogę jednak podzielić się próbką problemów, których rozwiązania na zawsze utkwiły mi w głowie. Oto one, wraz z delikatnymi podpowiedziami.

Dłuższą chwilę zastanawiałem się jak nie zacząć tekstu od frazy ,,moim ulubionym zadaniem''.  Poszło łatwiej niż sądziłem, gdyż Pająki (o których jest ten artykuł), są jednym z zadań, które dostarczyły mi głównie mnóstwo frustracji, choć również jeszcze więcej satysfakcji z oszukania systemu. Opisane w tym artykule rozwiązanie zadania wydaje się ciekawe, gdyż redukuje problem grafowy do problemu wyszukiwania wzorca (a nie — jak to zwykle bywa — na odwrót). Ale zacznijmy od początku.

Nie jest to może moje ulubione zadanie (nie wygrałem dzięki jego rozwiązaniu żadnych zawodów :), ale na pewno jest bardzo fajnym przykładem użycia dość ogólnej techniki, którą warto znać. Także dlatego, że w dość zaskakujący sposób pojawia się w niej geometria obliczeniowa (mam nadzieję, że nie zniechęci to Was to dalszej lektury...), mimo że zadanie na pierwszy (a nawet na drugi) rzut oka nie ma nic wspólnego z geometrią. Ale po kolei...

Jednym z najciekawszych zadań spośród tych, nad którymi miałem okazję się chwilę zastanawiać, są Krasnoludki. Problem pochodzi z obozu treningowego na IOI drużyny reprezentującej Rumunię, a odnalazłem o nim informację poprzez wpis na blogu Mihai'a Pătraşcu (na którym można znaleźć także wiele innych ciekawych problemów!).

Jednym z moich ulubionych zadań algorytmicznych jest Password Suspects z ACM World Finals 2008. Kapitan naszej drużyny przydzielił mi je wtedy mówiąc, że „to chyba jest dość proste”. Po dokładnym przeczytaniu treści tego oraz innych zadań, które miałem rozwiązać tamtego dnia uznałem, że to jednak nie jest zupełnie trywialne i póki co zajmę się innym, prostszym. Niestety, początek tego konkursu był dla nas nieudany i po około półtorej godziny zaczęliśmy być już mocno z tyłu.

Zanim przejdziemy do treści i opisu rozwiązania, kilka informacji o zadaniu. Możecie je znaleźć na SPOJu (tutaj), umieścił je tam Qu Jun, ale nie jestem pewien, czy to on jest jego autorem. Niektórzy pewnie zauważyli dziwny pogrubiony napis na dole strony, w pewnym sensie to ja jestem jego sprawcą.

W tym artykule przedstawiam jedno z ulubionych zadań mojego autorstwa. Zostało ono użyte na zawodach CEPC '03 (Central European Programming Contest) jako zadanie F (chociaż w trakcie pracy było nazywane raczej foo — skrót od Football). Dla pierwszej drużyny, która wysłała prawidłowe rozwiązanie, była ufundowana dodatkowa nagroda — piłka nożna. Podczas całych zawodów udało się to trzem drużynom: z Akademii Górniczo-Hutniczej, z Uniwersytetu Wrocławskiego, i z Uniwersytetu Warszawskiego.

Jednym z moich ulubionych zadań z konkursów informatycznych są ,,Autostrady'' z II etapu X Olimpiady Informatycznej 2002/2003. Jego treść (obrana z historyjki) wygląda mniej więcej tak:

Na prostej wybrano punktów ponumerowanych od do według ich kolejności występowania na tej prostej. Danych jest par punktów, które należy połączyć łukami. Każdy taki łuk musi przebiegać w całości po jednej stronie prostej.

W maju 2008 roku w Las Vegas odbyły się zawody TopCoder Open 2008. W eliminacjach online turnieju algorytmicznego wzięło udział ponad 1700 zawodników, z czego do finałów w Las Vegas zakwalifikowało się 72 osoby.

Zadanie polega na jak najszybszym pomalowaniu prostokątnej planszy o m wierszach oraz n kolumnach. Dla każdego z mn pól planszy znany jest kolor, na który trzeba to pole pomalować. Pola mogą być malowane wielokrotnie, przy czym dane pole za każdym razem musi być malowane tym samym kolorem (docelowym). Do malowania możemy wykorzystać następujące operacje: