276061651

Rozdział 1

Przedmowa

Najstarszym akademickim konkursem programistycznym jest International Collegiate Pro-gramming Contest organizowany przez Association for Computing Machinery (w skrócie ACM, oficjalna strona konkursu — http://icpc.baylor.edu/icpc/). Pierwsze zawody finałowe odbyły się 2 lutego 1977 roku w Atlancie, w Stanach Zjednoczonych (stan Georgia). Na początku lat dziewięćdziesiątych w eliminacjach do tego konkursu brało udział około 400 drużyn, z których 25 kwalifikowało się co roku do finału. Dziś o 70 - 80 miejsc w finałach walczy ponad 4000 drużyn z 1600 uczelni całego świata. Wzrost liczby uczestników świadczy o ogromnej popularności konkursu, której towarzyszy zwiększający się stopień przygotowania drużyn oraz trudność zadań.

Światowej rangi konkursem, organizowanym dla uczniów szkół średnich, jest Międzynarodowa Olimpiada Informatyczna (strona konkursu — http://www.ioinformatics.org/), która została po raz pierwszy zorganizowana w 1989 roku. W konkursie tym bierze udział po czterech reprezentantów z każdego kraju, wybieranych w ramach olimpiad narodowych. Oprócz tych, cieszących się wieloletnią tradycją konkursów, powstaje wiele nowych, takich jak TopCoder, Google Codę Jam czy Imagine Cup.

Udział w konkursach dla uczniów oraz studentów staje się nieodzownym elementem nauki algorytmiki. Nieustannie podwyższający się poziom konkursów przynosi ze sobą różne metodologie przygotowywania się do zawodów oraz specjalne techniki pisania programów. Ich celem jest minimalizacja ilości czasu potrzebnego na rozwiązanie zadania, przy jednoczesnym unikaniu jak największej liczby ewentualnych błędów. Ze względu na ograniczony czas trwania konkursów, ich uczestnicy nie mogą sobie pozwolić na tworzenie rozwiązań wszystkich zadań od zera. W wielu przypadkach muszą wykorzystywać pomysły zastosowane w podobnych zadaniach, rozwiązywanych już wcześniej, co pozwala im zaoszczędzić trochę czasu.

Książka ta jest swego rodzaju podręcznikiem do algorytmiki. Nie zawiera ona jednak wnikliwego opisu algorytmów wraz z ich analizą złożoności oraz dowodem poprawności. Jest to kolekcja implementacji różnych algorytmów, bardzo przydatnych podczas zawodów oraz zbiór zadań pozwalający na przećwiczenie ich wykorzystania w praktyce.

Znaczącą część grona czytelników stanowić będą zapewne osoby zainteresowane zwiększeniem swoich umiejętności w zakresie szybkiego implementowania rozwiązań zadań algorytmicznych w języku C++. Lektura niniejszej książki na pewno wpłynie pozytywnie na szybkość rozwiązywania zadań podczas takich konkursów jak Olimpiada Informatyczna. Jej użyteczność jest tym większa na konkursach typu ACM ICPC, podczas których dozwolone jest korzystanie z literatury. Wiele algorytmów z tej książki może zostać po prostu przepisanych do implementowanych podczas zawodów programów. Prezentowane tutaj algorytmy zostały tak napisane, aby ich adaptacja — w celu wykorzystania w różnych zadaniach — była jak

7