Jak rozwiązywać zadania na Olimpiadzie Informatycznej i Olimpiadzie Informatycznej Juniorów?

Olimpiada Informatyczna oraz jej odpowiednik dla szkół podstawowych od paru lat cieszą się dużym zainteresowaniem ze strony uczniów. Ciekawy temat, wespół z atrakcyjnymi nagrodami, zwracają uwagę wielu osób szukających konkursu, w którym mogłyby się wykazać. Niewielu uczestników jednak wie przed startem, jak dokładnie wyglądają zadania, z którymi będą się mierzyć. Nietypowa formuła, jaką ma Olimpiada Informatyczna, co roku zaskakuje nowych uczniów. W tym artykule przybliżymy nieco format zadań i ich rozwiązań oraz zastanowimy się, jak najlepiej się do nich przygotować.

Źródło: pl.freepik.com

Jak wyglądają zadania na Olimpiadzie Informatycznej i Olimpiadzie Informatycznej Juniorów?

Rozważając ogólnie różne konkursy i olimpiady, dostrzegamy, że co do zasady zadania często przyjmują pewną ustaloną formę. Jesteśmy przyzwyczajeni do pytań, które wymagają jednej poprawnej odpowiedzi, i klucza, które przewiduje pewne konkretne rozwiązanie. Olimpiady Informatyczne jednak znacząco odstępują od tej formuły, zarówno w kwestii formułowania odpowiedzi, jak i jej oceny.

Treści zadań na Olimpiadach Informatycznych z reguły przedstawiają pewną sytuację. Często napisane są w formie nieco niejasnej i wymijającej historyjki, która w samym swym rdzeniu uwzględnia pewien problem algorytmiczny. Zadaniem uczestników nie jest jednak po prostu rozwiązanie go dla jakichś konkretnych danych i zapisanie odpowiedzi. Zamiast tego wszyscy olimpijczycy mają do napisania program komputerowy, który będzie to robił za nich. To właśnie ten program stanowi rozwiązanie zadania i będzie podlegał ocenie.

W celu uściślenia zasad i ograniczeń, w treści umieszczone są sekcje określające w szczegółowy sposób format i limity wejścia i wyjścia, czyli danych, które zostaną programowi podane, oraz które oczekuje się, że program zwróci. Szczególnie istotne są limity ich dopuszczalnej wielkości, razem z limitami na ilość dostępnej pamięci programu. To one często dyktują, które rozwiązanie będzie poprawne, a które straci punkty.

Podział działania na trzy etapy

Tak więc każde zadanie stawia przed Olimpijczykami złożony problem, do którego nieraz samo podejście jest już wyzwaniem. Pracę, jaką wszyscy uczestnicy muszą wykonać, można podzielić na trzy etapy:

1. Rozpoznanie problemu. Zadania często są celowo napisane tak, żeby faktyczny problem był niejasny i trudny do zinterpretowania. To wprowadza dodatkową trudność do zadania w postaci konieczności dokładnego zrozumienia istoty zadania i rozpoznania zawartych w nim schematów.
2. Opracowanie algorytmu. Po zdefiniowaniu problemu postawionego w zadaniu, celem zawodników jest dobranie odpowiednich algorytmów i twierdzeń potrzebnych do rozwiązania zadania. Ten etap wymaga zarówno wiedzy teoretycznej, jak i praktycznej umiejętności modyfikowania znanych rozwiązań do celów konkretnego zadania.
3. Napisanie rozwiązania. Kiedy wiemy już, jakiego rozwiązania chcemy użyć, ostatnim krokiem jest napisanie programu który będzie to robił za nas. Ta część, chociaż najmniej teoretyczna, dalej jest wymagająca. Przy pisaniu kodu najłatwiej jest popełnić jakieś małe błędy. Należy jednak zawsze mieć na uwadze, że nawet takie np. błędy obliczeniowe nieraz prowadzą do dużych strat punktowych, ponieważ wpływają na każdy zwracany wynik.

Trzymając się tych kroków przy rozwiązywaniu zadania, można znacząco przyspieszyć tempo pracy, a tym samym szansę na sukces. Jest to szczególnie ważne w II i III etapie, gdy znaczenie może mieć każda minuta. Należy jednak pamiętać, że zadania olimpijskie są dalekie od schematyczności i żadna lista kroków nie będzie w stanie uwzględnić wszystkich możliwych scenariuszy.

Źródło: www.pexels.com

W jaki sposób oceniane są zadania Olimpijskie?

Jednym z przyciągającym najwięcej uwagi aspektów Olimpiad jest sposób oceniania rozwiązań. Tak jak wspomnieliśmy powyżej, Komitet Olimpijski odchodzi mocno od standardowej formuły klucza rozwiązań. Zamiast tego, zadania nie zakładają jednego konkretnego podejścia, a oceniana jest jedynie poprawność ostatecznie zwracanego wyniku, razem z paroma dodatkowymi czynnikami. Ta swoboda, którą oferują Olimpiady Informatyczne, przyciąga wielu chętnych, szczególnie tych, którzy lubią robić rzeczy po swojemu. Tak więc jak dokładnie oceniane są kody uczestników?

Na ocenę ma wpływ parę aspektów. Najważniejszym z nich jest oczywiście poprawność zwracanego rozwiązania. Żeby jednak zrozumieć dokładnie, co to znaczy, trzeba wiedzieć, co się dzieje po stronie Systemu Informatycznego Olimpiady. Każde zadanie posiada załącznik: zbiór testów w postaci plików wejściowych i wyjściowych. Są to odpowiednio dane podawane do zadania oraz oczekiwana odpowiedź. Dodatkowo, najczęściej testy są pogrupowane w tzw. “paczki”, czyli zestawy testów posiadających pewne dodatkowe ograniczenia. Typowo, są one opisane w treści zadania.

Zadania na Olimpiadzie Informatycznej: kryteria oceny

Program oceniający rozwiązania bierze kod uczestnika i uruchamia go na wszystkich testach dołączonych do zadania. Wykonanie kodu jest mierzone pod względem używanej pamięci i czasu, w jakim program obliczył odpowiedź. Następnie wyznaczana jest ilość punktów do przyznania za paczkę testów na podstawie następujących rzeczy:

1. Poprawność odpowiedzi: żeby uzyskać punkty za paczkę testów, wszystkie odpowiedzi w testach muszą być poprawne. Ocena jest w tym przypadku zero-jedynkowa, albo wyjście programu jest identyczne z wzorcowym, albo traktuje się je jako niepoprawne;
2. Poprawne wykonanie programu: czasami zdarza się, że kod zawiera w sobie błędy, które nie pozwolą na dalsze wykonanie. Wtedy zadanie otrzymuje komunikat RE (runtime error) i nie dostaje żadnych punktów za paczkę testów;
3. Pamięć użyta przez program: każde zadanie ma wyznaczony limit pamięci dostępnej dla rozwiązania. Ten limit jest sztywny i przekroczenie go oznacza utratę wszystkich punktów za rozwiązanie;
4. Czas wykonania programu: zadania mają również limit czasowy. Ten limit działa jednak odrobinę inaczej, ponieważ nie jest oceniany jako wartość binarna i może mieć wpływ na utratę tylko części punktów. Punkty za daną paczkę są przyznawane zgodnie z wykresem widocznym poniżej. Ten rysunek, wzięty z oficjalnej strony Olimpiady Informatycznej, pokazuje, w jaki sposób liczba punktów jest uzależniona od czasu wykonania programu. Tak więc, żeby uzyskać maksymalny wynik, nasz program musi się wykonywać w czasie równym maksymalnie połowie podanego limitu czasu. Przekroczenie ograniczenia oznacza utratę wszystkich punktów.

Te cztery aspekty decydują o ocenie zadania i przyznaniu punktów za poszczególne paczki. Zauważmy, że nie ma tutaj nic na temat samego kodu rozwiązania! On sam nie podlega ocenie, jedynie rezultaty, jakie zwraca. Mimo to należy pamiętać, że wszystkie rozwiązania są sprawdzane pod kątem plagiatu, a fakt, że kod nie jest oceniany, nie oznacza, że nikt się mu nie przygląda.

Źródło: www.pexels.com

Zadania na Olimpiadzie Informatycznej: najważniejsza jest praktyka!

Powyższy artykuł wyczerpuje temat jak rozwiązywać zadania na Olimpiadzie Informatycznej i Olimpiadzie Informatycznej Juniorów. Trzeba jednak pamiętać, że nic nie przygotuje nas lepiej do tego wyzwania niż praktyka i rozwiązywanie takich ćwiczeń. Dlatego bardzo istotne jest zapoznanie się z platformami, na których takie zadania są dostępne. 

Najbardziej rozpoznawalną z nich jest strona Szkopuł. To na niej właśnie dostępne są wszystkie zadania z poprzednich edycji Olimpiad, innych konkursów oraz obszerny zbiór pozostałych nieskategoryzowanych zadań. Warto od tego zacząć, ponieważ są tam też zadania o dużo niższym poziomie trudności, co pozwala na płynne wdrożenie się w świat Olimpiad. Drugim dobrym źródłem jest strona Codeforces. Jest to anglojęzyczna witryna, na której organizowane są cotygodniowe konkursy w podobnej formie co Olimpiada. Te dwa źródła stanowią bardzo dobrą podstawę do wykorzystywania poznanych algorytmów w praktyce, na faktycznych zadaniach.

W Indeksie w Kieszeni wszystkie zagadnienia tłumaczymy w zrozumiały i przystępny dla ucznia sposób. Szukasz skutecznego przygotowania do Olimpiady Informatycznej lub Olimpiady Informatycznej Juniorów? Jeżeli tak, to zachęcamy do zapoznania się z naszą ofertą kursów!