Ulubione zadania mistrzów, Zostań zawodnikiem, Dla zawodników

Znajdowanie otoczki wypukłej jest jednym z podstawowych problemów w geometrii obliczeniowej. Fakt, że w ciągu ostatnich 50 lat powstało bardzo wiele publikacji na temat tego zagadnienia świadczy o jego znaczeniu w dziedzinie algorytmiki. W niniejszym artykule zajmiemy się znajdowaniem otoczki wypukłej na płaszczyźnie.

Podstawową strukturą danych wykorzystywaną w algorytmach tekstowych jest drzewo trie (czyt. tri lub traj). Jest to kolejne rozwiązanie dla problemu wyszukiwania wzorca (i nie tylko). Z drzew trie korzystamy, gdy liczba zapytań jest na tyle duża, że nie opłaca się użycie klasycznych metod takich jak KMP czy BM (szczególnie gdy tekst wejściowy składa się ze sporej liczby słów). Drzewa te nadają się np. do sprawdzania poprawności pisowni.

W tym roku mieliśmy dla Was 6 zadań. Każde z nich w dwóch wersjach, basic i professional, różniących się limitami na dane wejściowe. W niektórych zadaniach (Mona Lisa, Drużyna) wersja professional wymagała rozwiązania o lepszej złożoności czasowej, w niektórych (Nobel, Mrówki) chcieliśmy w ten sposób sprawdzić czy umiecie udowodnić poprawność Waszego algorytmu, a w jeszcze innych (Połącz kropki, To może być toczeń) zmiana limitów sprawiała, że zadanie wymagało diametralnie innego podejścia.

W 2009 roku udało mi się dostać do reprezentacji Polski na Bałtycką Olimpiadę Informatyczną. Zadaniem, które sprawiło mi najwięcej radości (chociażby dlatego, że udało mi się je rozwiązać pomimo tego, że początkowo wydawało mi się dość trudne), było beetle. Jest na tyle ciekawe, że chciałabym je Wam przedstawić.

czyli krótki podręcznik dobrego złodzieja.

O tym kiedy wolno być zachłannym, a kiedy wybieranie tego co najlepsze nie zawsze popłaca, co musimy wiedzieć pakując swój plecak lub wydając resztę oraz jak znaleźć optymalne rozwiązanie nie uciekając się się do magii.

Drzewa zrównoważone to niezwykle przydatne struktury danych. Można ich użyć np. do tworzenia słowników, w których kluczowym jest wykonywanie wszystkich operacji w jak najlepszym czasie. Strukturą, którą będziemy się zajmowali w niniejszym artykule jest drzewiec (z ang. treap), który łączy w sobie cechy binarnego drzewa przeszukiwań i kopca (również binarnego).

Znajdowanie najkrótszej ścieżki w grafie ma wiele wariantów. Przyjrzyjmy się takiemu: statek kosmiczny podróżuje między galaktykami - niektóre podróże są kosztowne czasowo - wehikuł po prostu leci przez przestrzeń kosmiczną. Ale ma też czasem możliwość skorzystać z tuneli czasoprzestrzennych - nie dość, że zmienia położenie, to jeszcze cofa się w czasie. Jak wtedy znaleźć najszybszą drogę z jednej galaktyki do drugiej?

Umiejętność wyszukiwania mostów i punktów artykulacji przydaje się nie tylko w konkursach algorytmicznych. Wszędzie tam, gdzie mamy do czynienia ze strukturą grafu np. sieć dróg, torów kolejowych, kabli internetowych wiedza zawarta w niniejszym artykule okazuje się niezbędna. Można śmiało powiedzieć, że temat, którym się będziemy zajmować to kolejny ważny krok na drodze do zostania mistrzem teorii grafów.

Problem najdłuższego wspólnego podciągu jest niezwykle istotny zarówno z punktu widzenia informatyki, jak i pozornie odłegłych od niej dziedzin nauki - np. biologii. Niezależnie od tego czy chcemy skutecznie podpowiadać poprawną pisownię, czy może szukamy podobieństw w strukturze dwóch łańcuchów DNA, algorytmy obliczające najdłuższy wspólny podciąg okażą się niesłychanie przydatne.

Algorytm przeszukiwania w głąb ( ang. depth first search ) jest jedną z najprostszych metod przechodzenia po grafie. Jednocześnie, metoda ta jest używana jako podstawa do wielu bardziej skomplikowanych algorytmów grafowych. Z tego powodu wiedza na temat przechodzenia grafu w głąb jest niezbędna dla osób rozpoczynających swoją przygodę z algorytmiką.

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.

„Głupiec i mędrzec nie widzą tego samego drzewa.” - mawiał William Blake. Drzewa dostarczają życiodajnego tlenu, w słoneczny dzień służą cieniem, a ich abstrakcyjne odpowiedniki są nieodzownym elementem arsenału dobrego programisty. Tylko, no właśnie, o czym dokładnie mowa i jak się do tego zabrać? W poszukiwaniu kilku klasycznych problemów informatycznych dotyczących drzew zapraszam do... Puszczy Amazońskiej.

 skrócie BST (ang. binary search tree), jak sama nazwa wskazuje, ma strukturę drzewa binarnego. Tego typu drzewa stosuje się do szybkiego wyszukiwania jak również do realizacji bardziej abstrakcyjnych struktur danych. Uważam, że każda osoba chcąca zgłębić tajniki algorytmiki powinna zaznajomić się z drzewem BST, ponieważ jest to jedna z podstawowych struktur danych.

W niniejszym artykule przedstawimy parę pojęć i zagadnień, dzięki którym będziemy mogli w konkretny sposób opisywać problemy, a także w łatwy sposób rozwiązywać je. Mowa tu o grafach. [Początki tej dziedziny sięgają XVIII wieku, kiedy to właśnie za pomocą tej struktury – grafu – udało się rozwiązać problem pewnego spaceru]. Zapraszam zatem do lektury!

    Geometria jest dziedziną matematyki, która zazwyczaj budzi rozmaite, najcześciej przeciwstawne uczucia. Jedni uważają ja za nudną - tym się dziwię. Inni dostrzegają piękno zajmowania się obiektami geometrycznymi, wymagającego pomysłowości, cierpliwości i nieraz chwili iluminacji.

Arytmetyka modularna jest kolejnym narzędziem matematycznym ułatwiającym infomatykom rozwiązywanie problemów algorytmicznych.

W informatyce - podobnie jak w życiu - niektóre problemy łatwiej rozwiązać, a inne trudniej. W niniejszym artykule pokażemy jak problem trudny rozwiązać za pomocą problemów łatwiejszych. Problemem jakim się zajmiemy będzie liczenie elementów sumy zbiorów.

Kopiec jest to tablicowa struktura danych mająca duże znaczenie w algorytmice, jako że jest podstawą dla bardziej skomplikowanych obiektów. Jeśli chcesz bliżej poznać tą przypominającą drzewo strukturę, to niniejszy artykuł jest dla Ciebie.