Kurs przygotowujący do przygotowywania się do Olimpiady Informatycznej

 

Ten artykuł ma być mini-kursem uczącym na czym polega przygotowywanie się do Olimpiady Informatycznej.

Poruszę tutaj różne kwestie takie jak:

– na czym polegają zadania

– gdzie znajdować zadania

– co jest potrzebne do rozwiązywania zadań

– zarys teorii przydatnej przy rozwiązywaniu zadań

 

MOTYWACJA

 

Być może nie potrzebujesz dodatkowej motywacji oraz motywowanie innych nie jest rzeczą prostą, zależy w dużej mierze od jednostki.

Napiszę tutaj tylko jedną rzecz. Zadania z OIa są trudne. Patrząc na statystyki, do finału OIa dochodzi jedynie około 100 osób, z kilkuset tysięcy uczniów. Oczywiście nie wszyscy są zainteresowaniu informatyką, a w szczególności algorytmiką.

Patrząc dalej na statystyki międzynarodowej olimpiady IOI, Polska wypada bardzo dobrze na świecie.

Ranking krajów Olimpiady Informatycznej

 

Oznacza to, że dojście do finału OIa to całkiem niezłe osiągnięcie na skalę międzynarodową 😮

Przyjrzyjmy się teraz wynikom finału ostatniej edycji OIa.

 

Już w czołówce widać, że chociażby laureaci I miejsca z dołu tabeli zdobyli tylko trochę więcej niż 60\% punktów.

 

Jak popatrzymy jednak na finalistów z dołu, okaże się, że udało im się zdobyć jedynie 20-30% punktów. Wcale nie jest to wyjątkowa sytuacja.

Zadania na OIu są trudne, nawet w skali międzynarodowej. Nie warto się zatem przejmować, gdy podczas przygotowań coś nie wychodzi, gdy zadania zdają się być za trudne i nie jest się w stanie wiele samemu wymyślić. To normalne i niemal wszyscy doświadczają tego samego. Sam pamiętam jak zaczynałem od rozwiązywania zadań na SPOJu i gdy pierwszy raz pisałem pętle wewnątrz innej pętli, w głowie mi się kręciło od prób wyobrażenia tego co się w ogóle ma dziać. Z treningiem wszystko staje się łatwiejsze w myśl starej zasady:

Trening czyni mistrza 😀

 

NA CZYM POLEGA OLIMPIADA INFORMATYCZNA?

 

Olimpiada Informatyczna to programowanie + algorytmika. Na każdym etapie dane jest kilka zadań algorytmicznych do których należy napisać program, rozwiązujący je. Jako, że wiele osób ma pojęcie czym jest OI, to na tym zakończę wprowadzenie 😜

 

Na czym polega rozwiązywanie zadań z OIa?

 

Większość zadań podpada pod pewną kategorię. O kategoriach i ogólnie o teorii będzie później.

Przykładowo zadanie mogą wymagać:

-wykorzystania programowania dynamicznego

-wykorzystania algorytmów na grafach

-zastosowania strategii dziel i zwyciężaj

Zwykle podczas rozwiązywania zadań wybiera się drogę, którą chce się obrać. Przykładowo postanawia się, że “na początku spróbujmy programowania zachłannego”. Oczywiście często trzeba zmieniać podejścia, gdy pewne nie wypaliło, jednak wraz ze zdobywanym doświadczeniem i wiedzą, coraz łatwiej jest odgadywać, czego mniej więcej dane zadanie będzie wymagało.

Sama wiedza i doświadczenie jednak często nie wystarczają, ponieważ autorzy zadań starają się dostarczać zadania jak najbardziej unikalne, nowe przynajmniej pod kilkoma względami.

Dlatego niemal zawsze trzeba najpierw zauważyć pewne nietrywialne własności występujące w zadaniu, które pozwolą zastosować już bardziej typowe algorytmy, struktury danych lub strategie. Potem pozostaje implementacja. Rozwiązywanie zadań z mojego doświadczenia, sprowadza się właśnie do tego.

Mimo, że wiedza bardzo się przydaje podczas rozwiązywania zadań oraz bez odpowiedniej wiedzy rozwiązanie niektórych zadań może być trudne, to nawet gdy się wie, że nie posiada się pewnej wiedzy czasem warto samemu próbować tą wiedzę odkryć. Tak wiedza to często nic innego jak bardziej skomplikowane własności występujące w zadaniach.

 

Jak przebiega przygotowywanie się do OIa?

 

A dokładniej: jak może wyglądać wzrost umiejętności na przestrzeni czasu?

Przygotowywanie się do OIa często można podzielić na trzy początkowe etapy:

Etap I Wszystko jest nowe, oraz zdobywa się dużo podstawowej wiedzy, a zadania głównie wymagają właśnie wiedzy

Etap II posiada się już dużo podstawowej wiedzy, a zadania zaczynają być mniej klasyczne. Wymagają więcej myślenia, a nie samej wiedzy

Etap III  Posiada się dużo wiedzy i doświadczenia, a zadania zaczynają się powtarzać

Aby dostać się do II etapu OIa, nie potrzeba bardzo dużo, zwłaszcza gdy ma się w otoczeniu osoby również startujące. Próg dostania się do finału OIa oszacowałbym na poziomie między II, a III etapem opisanym powyżej. Liczby widoczne z lewej strony wykresu odpowiadają rankingowi na CodeForces.

 

Skąd brać materiały i zadania do nauki?

 

Informatycy spędzają dużo czasu przy komputerze, dużo czasu w internecie, oraz nie mają problemu z tworzeniem oprogramowań i różnych witryn. Przekształca się to w fakt, że w internecie można znaleźć bardzo dużo nawet darmowych materiałów do nauki. Istnieje również wiele stron oferujących zadania, na których można trenować, a nawet stron organizujących regularne contesty, które formą przypominają samą Olimpiadę Informatyczną.

Przykładowe strony oferujące takie contesty:

-codeforces.com

-codechef.com

-atcoder.jp

Niekoniecznie optymalnym, ale bardzo bezpośrednim sposobem na przygotowanie się do OIa jest regularne branie udziału we wszystkich contestach oraz próba osiągnięcia jak najwyższego rankingu.

 

WIEDZA

 

Istnieje kilka głównych działów algorytmiki/matematyki, które przydają się przy rozwiązywaniu zadań. Oto przykładowa rozpiska podstawowych zagadnień z której można korzystać podczas nauki:

Klasyczne techniki algorytmiczne

– Tablicowanie

– Dwa wskaźniki / gąsienica

– Wyszukiwanie binarne

– Algorytmy brutalne

– Szybkie potęgowanie

– Trik pod pierwiastkiem

– Meet-in-the-middle

– Struktury danych

– Programowanie zachłanne

– Programowanie dynamiczne

– Teoria grafów

– Algorytmy tekstowe

– Geometria obliczeniowa

Przydatne działy matematyki

– Teoria liczb

– Kombinatoryka

– Prawdopodobieństwo

– Teoria gier

– Algebra liniowa

 

Podsumowanie – przygotowanie do Olimpiady Informatycznej

Mamy nadzieję, że po lekturze tego artykułu temat przygotowań do Olimpiady Informatycznej skrywa przed Wami mniej tajemnic. Zachęcamy do wzięcia udziału w kursach Indeksu w Kieszeni, gdzie oprócz wyselekcjonowanych zadań otrzymujecie możliwość bieżącego kontaktu z laureatem!

Indeks w Kieszeni
kontakt@indekswkieszeni.pl