Olimpiada Informatyczna - jak się przygotować do zawodów algorytmicznych

Olimpiada Informatyczna - o co grasz

Olimpiadę Informatyczną prowadzi Fundacja Rozwoju Informatyki. To ogólnopolskie zawody w programowaniu i algorytmice, a nagrody są wyjątkowo namacalne: laureat i finalista są zwolnieni z matury z informatyki i mają na świadectwie wynik 100% na poziomie rozszerzonym. Finaliści zyskują wolny wstęp na studia informatyczne według uchwał poszczególnych uczelni, a najlepsi trafiają do reprezentacji Polski na Międzynarodowej Olimpiadzie Informatycznej.

Zanim zaczniesz, zerknij na dwa artykuły ogólne: czym jest olimpiada przedmiotowa i olimpiada a matura. Aktualne terminy i materiały znajdziesz przy Olimpiadzie Informatycznej w bazie. Poniżej piszemy o tym, jak realnie wygląda trening algorytmiczny.

To nie jest informatyka szkolna

Na lekcjach informatyki i na maturze duża część zadań dotyczy narzędzi: arkusza, bazy danych, prostych skryptów. Na olimpiadzie dostajesz opis problemu, ograniczenia na rozmiar danych i limit czasu, a twoim zadaniem jest wymyślić metodę, która się w tym limicie zmieści. Trzy różnice, które zmieniają sposób nauki:

• Rozwiązanie poprawne to za mało. Program, który daje dobre wyniki, ale liczy zbyt długo dla dużych danych, nie zalicza zadania.
• Nikt nie ocenia stylu ani interfejsu. Kod czyta automat: wczytuje wejście, porównuje wyjście z wzorcowym.
• Pomysł waży więcej niż implementacja. Większość czasu na zawodach spędzasz z kartką, a nie przy klawiaturze.

Algorytmy, struktury danych i złożoność

Kanon, który trzeba znać

Zestaw tematów, wokół których kręci się większość zadań olimpijskich, jest dość stały:

• sortowanie i wyszukiwanie binarne, w tym wyszukiwanie binarne po odpowiedzi,
• struktury danych: stosy, kolejki priorytetowe, zbiory i słowniki, drzewa przedziałowe, struktura zbiorów rozłącznych,
• grafy: przechodzenie wszerz i w głąb, najkrótsze ścieżki, drzewa rozpinające, sortowanie topologiczne,
• programowanie dynamiczne - od klasyki po dynamikę na drzewach i po podzbiorach,
• algorytmy zachłanne i dowodzenie, że zachłanność faktycznie działa,
• matematyka dyskretna i algorytmy tekstowe: kombinatoryka, arytmetyka modularna, haszowanie.

Ucz się w kolejności: najpierw zrozum ideę, potem zaimplementuj samodzielnie od zera, na końcu rozwiąż kilka zadań, w których dana technika jest tylko jednym z elementów.

Złożoność to twój kompas

Zanim napiszesz pierwszą linijkę, spójrz na ograniczenia w treści. Rozmiar danych mówi ci, jakiej klasy rozwiązania szukać: inne podejście wchodzi w grę przy kilkuset elementach, inne przy milionach. Ten jeden nawyk odróżnia startujących, którzy awansują, od tych, którzy piszą działający program o kilka rzędów wielkości za wolny. Pamiętaj też o limicie pamięci - potrafi wywrócić poprawny algorytm.

Jak pracuje system oceniający i co z tego wynika

Zawody odbywają się w systemie SIO2 - wysyłasz rozwiązanie, a ono jest uruchamiane na zestawie testów. To zmienia sposób pracy:

1. Czytaj format wejścia i wyjścia dosłownie. Nadmiarowa spacja czy brakujący znak końca linii potrafią zepsuć poprawne rozwiązanie.
2. Testuj przypadki brzegowe - dane najmniejsze z możliwych, wartości skrajne, powtórzenia, dane już posortowane, jeden element.
3. Uważaj na zakresy typów liczbowych. Przepełnienie przy mnożeniu dużych liczb to klasyczny błąd, którego kompilator ci nie zgłosi.
4. Pisz rozwiązanie wolne, ale pewne, i porównuj z nim wyniki właściwego programu na losowych danych - ta technika wyłapuje błędy, których nie widać w treści.
5. Sprawdź w regulaminie listę dopuszczonych języków i trenuj w tym, w którym będziesz startować; przy ciasnych limitach czasu wybór języka ma znaczenie.

Jak trenować przez rok

Algorytmiki nie da się nadrobić w tydzień, ale da się ją zbudować systematycznie. Wakacje i wrzesień to fundamenty: przejście przez kanon struktur danych i implementacja każdej z nich samodzielnie. Jesienią wchodzą zawody domowe - masz na nie sporo czasu, więc traktuj je jak projekt, a nie sprawdzian, i wracaj do zadania po dniu przerwy, zanim wyślesz ostateczną wersję. Zima to trening pod presją czasu, wiosna - zadania z finałów poprzednich lat. Szerszy plan roku opisaliśmy w poradniku jak przygotować się do olimpiady.

Do tego jedna zasada: po każdym nierozwiązanym zadaniu przeczytaj omówienie i zaimplementuj rozwiązanie wzorcowe samodzielnie. Przeczytanie pomysłu daje złudzenie zrozumienia; dopiero własna implementacja pokazuje, czy naprawdę go masz.

Etapy i formalności

Olimpiady przedmiotowe mają trzy etapy: szkolny jesienią, okręgowy zwykle w styczniu lub lutym oraz finał zwykle w marcu lub kwietniu. W Olimpiadzie Informatycznej etap pierwszy to zawody domowe - zadania rozwiązujesz online w systemie SIO2, a etap I obejmuje turę zdalną i turę szkolną.

Formalności są proste, ale trzeba ich dopilnować: szkolny koordynator rejestruje szkołę w systemie SIO2, a ty zakładasz własne konto i rozwiązujesz zadania etapu I. Udział jest bezpłatny. Terminy bieżącej edycji sprawdź w kalendarzu.

Olimpiada Informatyczna Juniorów - ścieżka dla szkoły podstawowej

Uczniowie klas IV-VIII startują w Olimpiadzie Informatycznej Juniorów, prowadzonej przez tę samą fundację. Informatyki nie ma na egzaminie ósmoklasisty, więc tytuł nie zwalnia z egzaminu - daje za to przyjęcie do wybranej szkoły średniej w pierwszej kolejności i celującą roczną ocenę z informatyki, a najlepsi jadą na Europejską Junior Olimpiadę Informatyczną.

Etap pierwszy łączy zadania rozwiązywane zdalnie w systemie SIO2 z dwiema częściami pisanymi w szkole pod opieką nauczyciela: testem i częścią praktyczną. Rejestrują się zarówno szkoła, jak i sam zawodnik. Więcej w poradnikach o olimpiadach dla uczniów szkoły podstawowej i o zwolnieniu z egzaminu ósmoklasisty.

Sztuczna inteligencja to osobne zawody

Jeśli bardziej niż algorytmika ciągnie cię uczenie maszynowe, sprawdź Olimpiadę Sztucznej Inteligencji prowadzoną przez Fundację Edukacji i Rozwoju Sztucznej Inteligencji. To najmłodsza z dużych olimpiad, oficjalnie wspierana przez Ministerstwo Edukacji Narodowej, z praktycznymi zadaniami z uczenia maszynowego rozwiązywanymi zdalnie na pierwszym etapie. Przydają się podstawy programowania w Pythonie, a rejestrujesz się samodzielnie.

Ważne rozróżnienie: to olimpiada tematyczna, więc nie zwalnia z matury. Finaliści i laureaci mają ułatwiony lub wolny wstęp na wybrane kierunki studiów, a najlepsi reprezentują Polskę na Międzynarodowej Olimpiadzie Sztucznej Inteligencji.

Częste błędy - i pierwszy krok

• Kodowanie przed myśleniem - bez oszacowania złożoności łatwo napisać rozwiązanie, które nigdy nie przejdzie dużych testów.
• Trening wyłącznie na łatwych zadaniach - komfortowe zadania budują pewność siebie, ale nie poziom.
• Ignorowanie przypadków brzegowych - najwięcej straconych punktów bierze się z danych minimalnych i skrajnych, a nie z trudnej logiki.
• Czytanie rozwiązań zamiast ich implementowania - zrozumienie pomysłu to dopiero połowa drogi.

Zacznij od jednego zadania z archiwum: oszacuj złożoność, zapisz pomysł na kartce, dopiero potem usiądź do kodu. Pozycję Olimpiady Informatycznej dodaj do ulubionych, terminy śledź w kalendarzu, a pozostałe zawody przejrzyj w bazie olimpiad.