Dwa zadania z finału Olimpiady Informatycznej Juniorów

Czyli krótka opowieść o tym, które zadania są dla (trenujących) zdolnych dzieci łatwe, a które nie?

• 25.04.2025
• 10 min czytania

Spis treści

Zbliżamy się do końca roku szkolnego. Zdecydowana większość olimpiad przedmiotowych jest już za nami, a uczniowie, którzy brali w nich udział mogą teraz złapać trochę oddechu i zacząć się przygotowywać do kolejnych edycji. Jeszcze przed świętami wielkanocnymi mogłem z bliska obserwować finał Olimpiady Informatycznej Juniorów, z którą jestem blisko związany. Chociaż wydawało mi się, że zestaw zadań na ten rok jest trudniejszy niż rok temu, dwaj zwycięzcy nie mieli dla mnie litości i w obu dniach konkursowych zdobyli komplet punktów. Gratulacje dla nich. Zadania nie były aż takie łatwe dla pozostałych zawodników, jednak zaskoczyło mnie to, na których konkretnie zadaniach tracili oni punkty. I o tym będzie dzisiejszy wpis.

(Zdjęcie z miniaturki pochodzi ze strony oij.edu.pl, a autorem jest Bartosz Kostka.)

Zasady Olimpiady

Być może nie wszyscy Czytelnicy tego bloga dokładnie znają zasady tej Olimpiady, streszczę je więc tutaj. Podczas dwóch czterogodzinnych sesji (odbywających się w dwóch różnych dniach), w warunkach kontrolowanej samodzielności, finaliści mieli do rozwiązania po trzy zadania. Treść każdego zadania składa się z około dwóch stron: na początku jest opisana pewna historyjka, która luźnym językiem opisuje pewien problem obliczeniowy, który trzeba będzie rozwiązać. Ten problem będzie rozwiązywał komputer, a zadaniem zawodnika jest ten komputer nauczyć. Dalsza część opisu zadania składa się z nieco bardziej formalnej części, gdzie opisane jest w jakim formacie podane są dane, w jakim formacie należy podać odpowiedź. Na samym końcu treści zazwyczaj znajduje się kilka przykładów, żeby upewnić się, że zawodnik rozumie o czym jest zadanie.

Należy wymyślić algorytm (sposób rozwiązania) oraz zaimplementować go w jednym z dostępnych języków programowania (na chwilę pisania tego wpisu jest to C++ lub Python). Program ten będzie następnie wielokrotnie uruchomiony w specjalnym zautomatyzowanym środowisku, w którym zostaną do niego podane różne dane wejściowe. Sprawdzane jest wtedy, czy program wyprodukował prawidłowe odpowiedzi dla tych danych, ile pamięci zużył program i ile to trwało czasu. Zawodnicy znają wynik swoich rozwiązań jeszcze w trakcie konkursu, zaraz po wysłaniu (po może kilkunastu sekundach) wiedzą ile punktów jest warte ich rozwiązanie. Każde zadanie można wysłać wielokrotnie, a do klasyfikacji brany jest pod uwagę najwyższy wynik zgłoszenia z każdego zadania. Olimpiada w wersji dla juniorów jest przeznaczona dla uczniów szkół podstawowych (do ósmej klasy), jest też wariant dla uczniów szkół ponadpodstawowych. Strona małej olimpiady jest tutaj, zaś strona dużej olimpiady znajduje się tutaj.

Dodam jeszcze, że ta zabawa w rozwiązywanie zagadek algorytmicznych na komputerze nie jest tylko dla sportu. Finaliści (czyli zakwalifikowani do ostatniego etapu) otrzymują pierwszeństwo w rekrutacji do w zasadzie każdej szkoły ponadpodstawowej bez udziału w konkursie świadectw i bez brania pod uwagę wyniku egzaminu ósmoklasisty. Jakkolwiek wierzę, że prawie każdy z finalistów nie miałby większego problemu z uzyskaniem wysokich wyników w standardowej rekrutacji, taki sukces (szczególnie jeśli zdobyty wcześniej niż w ostatniej klasie szkoły) zmienia optykę na uczenie się w szkole. Nauczyciele bowiem przez ostatnie klasy szkoły podstawowej powtarzają: Uczcie się uczcie, bo egzamin ósmoklasisty, zaś w szkole ponadpodstawowej mantra zmienia się na Uczcie się uczcie, bo matura. Olimpiady dają szansę wyrwać się z tego systemu i dzięki temu bardziej skupić się na zdobywaniu ukierunkowanej już wiedzy i umiejętności, zgodnych z zainteresowaniami ucznia. Najlepsi reprezentują Polskę na olimpiadach międzynarodowych, jeżdżą na obozy naukowe, integrują się ze sobą i wzajemnie motywują (czy to poprzez rywalizację, lub lepiej, współpracę) do dalszej pracy. O olimpiadach przedmiotowych pisałem już tutaj i gorąco zachęcam Czytelników, którzy wcześniej o nich nie słyszeli do nadrobienia zaległości.

Zadania na tegorocznym finale

Zadanie Spirala

Jednym z zadań na drugim dniu zawodów było zadanie o sprawdzaniu czy spirala, zadana przez ciąg liczb (długości kolejnych odcinków łamanej) ma jakieś samoprzecięcie. Spirala najpierw ciągnie się do góry (tyle ile wynosi pierwsza liczba opisu spirali), a potem skręca w prawo o 90 stopni i ciągnie się jej następny odcinek (o takiej długości jak druga liczba opisu), potem znowu skręca w prawo o 90 stopni i tak dalej.

Poniższa spirala zadana jest ciągiem $(5, 7, 4, 6, 2, 1, 1)$ i nie zawiera samoprzecięcia (program powinien wypisać NIE jako odpowiedź):

Poniższa spirala zadana jest ciągiem $(6, 6, 8, 8, 5, 5, 1, 1, 5)$ i zawiera trzy samoprzecięcia (wystarczy, że program po znalezieniu dowolnego z nich wypisze TAK):

Na obrazku łatwo oczywiście zobaczyć jaka jest odpowiedź, jednak zadaniem zawodników było nauczyć komputer rozpoznawania samoprzecinających się spirali. A komputer raczej nie zrobi sobie rysunku i nie zobaczy tego tak jak człowiek. Inna sprawa, że spirala mogła składać się z kilkuset tysięcy odcinków o długościach rzędu miliarda jednostek, a więc rysowanie jej (nawet w pamięci komputera) nie jest zbyt praktyczne.

Spodziewałem się, że zawodnikom narzuci się następujące rozwiązanie: każda spirala składa się z odcinków pionowych i poziomych, występujących naprzemiennie. A zatem wydaje się, że można rozbić wejściowy ciąg na dwa ciągi (z elementów na pozycjach parzystych i na pozycjach nieparzystych) i sprawdzić, czy są to ciągi rosnące czy malejące. Ta strategia zdaje się działać dla zaprezentowanych powyżej przykładów. Ciąg $(5, 7, 4, 6, 2, 1, 1)$ zamieniamy na dwa ciągi: $(5, 4, 2, 1)$ oraz $(7, 6, 1)$, są to oba ciągi malejące, a więc spirala się ciągle zmniejsza i nie ma żadnych samoprzecięć. Podobnie ciąg $(6, 6, 8, 8, 5, 5, 1, 1, 5)$ zamieniamy na $(6, 8, 5, 1, 5)$ oraz $(6, 8, 5, 1)$ i widzimy od razu że “coś jest nie tak”. Oczywiście, wprawieni w boju zawodnicy od razu wyczuli, że to nie jest aż takie proste. Dla mniej wprawionych, w treści zadania był pokazany inny przykład:

Chociaż powyższe nie wygląda jak typowa spirala, to spełnia formalną definicję podaną w treści zadania i program zawodnika również powinien sobie z czymś takim poradzić. Spirala ta opisana jest ciągiem $(5, 6, 7, 8, 9, 11, 6, 2, 2, 1, 1)$, który po rozbiciu na ciągi z pozycji parzystych/nieparzystych daje: $(5, 7, 9, 6, 2, 1)$ oraz $(6, 8, 11, 2, 1)$. Oba te ciągi najpierw są rosnące, a potem (od pewnej pozycji) malejące, jak w poprzednim przykładzie. Tym razem jednak prawidłowa odpowiedź to NIE zamiast TAK.

Zadanie można poprawnie rozwiązać na co najmniej dwa sposoby:

• albo potraktować spiralę jako ciąg kolejnych odcinków pionowych i poziomych, dla których można wyliczyć współrzędne punktów będących ich końcami, a następnie zauważyć, że nie trzeba sprawdzać każdej pary odcinków czy się przecinają czy nie (a jedynie pary bliskich sobie odcinków w ciągu),
• albo poprawić pierwotny pomysł i zauważyć, że gdy spirala przejdzie w “tryb zmniejszający”, to żeby nie miała samoprzecięć musi już mieścić się w coraz mniejszych prostokątach ograniczających (inaczej od razu jest odpowiedź TAK).

W każdym z tych dwóch pomysłów trzeba być ostrożnym i zauważyć kilka przypadków szczególnych, ale implementacja jest raczej dość krótka, a sam pomysł nie wymaga żadnej wiedzy algorytmicznej nauczonej przed zawodami.

Zadanie Szpiedzy

Inne zadanie (które mieli do rozwiązania zawodnicy tego samego dnia) polegało na tym, że pewna agencja chce zebrać informacje od szpiegów porozrzucanych w terenie. W tym celu szpiedzy mogą wracać do bazy (co wiąże się z pewnym kosztem, zależnym od tego ilu agentów wróci do bazy) lub spotykać się (zawsze w grupach dwuosobowych, żeby przekazać sobie wzajemnie wszystkie dotychczas zdobyte informacje, co również wiąże się z kosztem – tym razem zależnym od pary agentów, które się spotykają).

Program więc musi wczytać:

• ile kosztuje wysłanie do bazy jednego, dwóch, trzech, …, $n$ agentów,
• które pary agentów mogą się ze sobą spotkać i ile kosztują poszczególne spotkania.

Celem jest wyznaczyć najtańszy koszt sprowadzenia wszystkich informacji do bazy. Zależnie od danych opłacalne może być:

• zaaranżowanie dużej liczby spotkań, żeby do bazy wysłać tylko jednego agenta, który wie wszystko,
• wysłanie do bazy wszystkich agentów, nie płacąc wtedy za spotkania w terenie,
• rozwiązanie pośrednie, w którym niektóre pary agentów spotykają się ze sobą, dzięki czemu do bazy można wysłać tylko niektórych z nich.

Program zawodnika musi zbalansować co się bardziej opłaca. Połowę punktów można było zdobyć za samo wyznaczenie optymalnego kosztu, a żeby zdobyć drugą połowę punktów trzeba było jeszcze podać pełne rozwiązanie – wyznaczyć które spotkania (i kiedy) się odbywają oraz którzy agenci (i kiedy) mają iść do bazy.

Myślę, że prawie wszyscy zawodnicy na finale od razu wiedzieli, że najlepiej modelować sytuację w zadaniu za pomocą teorii grafów. Agenci stanowią wierzchołki grafu, a możliwe spotkania między nimi wyrażone są za pomocą krawędzi. Każda krawędź ma swój koszt (spotkania) oraz możliwe jest również wybieranie wierzchołków (agentów, którzy pójdą do bazy). Celem jest wybrać obiekty o łącznie najtańszym koszcie, które umożliwiają zebranie wszystkich informacji.

Oczywiście, w treści zadania nie było powyższego rysunku. To zadaniem zawodnika jest znać odpowiednią teorię i narzędzia, które mogą się przydać w rozwiązaniu zadania. Tutaj kolejnym krokiem do rozwiązania zadania jest zauważenie, że po wybraniu podzbioru krawędzi (spotkań, które się odbędą) graf dzieli się na spójne składowe (na poniższym obrazku oznaczone kreskowanymi elipsami). Z każdej takiej spójnej trzeba i wystarczy oddelegować do bazy jednego agenta.

Rozwiązanie sprowadza się do zauważenia, że możliwe jest posortowanie zbioru krawędzi i analizowanie ich od najtańszych do najdroższych. Startujemy od rozwiązania, w którym nie wybraliśmy żadnej krawędzi (a więc wysyłamy wszystkich agentów do bazy). W każdym kroku dodajemy krawędź do rozwiązania, o ile jej końce nie są już inaczej połączone (innymi słowy: o ile nie są w tej samej spójnej składowej). Tymi składowymi można dynamicznie zarządzać i sprawdzać z użyciem struktury Union-Find: opowiadałem o tym kiedyś na webinarium w ramach projektu MAP (film z webinarium tutaj). Każda dołożona krawędź zwiększa koszt zorganizowanych spotkań, ale zmniejsza liczbę spójnych składowych o jeden (a więc liczbę wysłanych agentów do bazy). Najlepsze z uzyskanych rozwiązań na przestrzeni całego algorytmu jest rozwiązaniem optymalnym.

Nie jest do końca oczywiste dlaczego to działa. Trzeba jeszcze pokazać w jakiej kolejności organizować spotkania wewnątrz spójnych składowych (można sobie najpierw wybrać agenta, który na końcu pójdzie do bazy, a potem propagować informacje od agentów oddalonych najbardziej od niego w stronę ich bliższych sąsiadów - można to zrobić np. algorytmem BFS). No i wypadałoby udowodnić dlaczego możemy sobie pozwolić na takie zachłanne dokładanie krawędzi od najtańszych do najdroższych: tutaj poprawność można wywnioskować w podobny sposób jak poprawność algorytmu Kruskala na minimalne drzewo rozpinające. To byłoby ciekawe, żeby o tym opowiedzieć, ale nie chcę już nadmiernie zanudzać. Może kiedy indziej.

Rozwiązanie zadania wymaga więc kilku w miarę prostych obserwacji strukturalnych oraz pewnej twardej wiedzy, której typowi uczniowie szkół podstawowych nie mają. Implementacja nie jest wcale oczywista: trzeba osobno napisać algorytm zarządzający lasem spójnych składowych oraz osobno napisać algorytm odzyskujący pełne rozwiązanie, a nie tylko jego koszt. Podczas zawodów zawodnicy nie mają dostępu do książek, ani internetu. Nie mogą poprosić Wikipedii o przypomnienie szczegółów algorytmu lub ChatGPT o zaimplementowanie go za nich.

Komentarz

Przede wszystkim należy pochwalić zawodników, że potrafili w warunkach konkursowych powalczyć skutecznie z zaproponowanymi zadaniami. System punktacji jest dość brutalny. Sam pomysł, bez działającego programu jest nic nie warty (ocenianie jest automatyczne, na podstawie tego ile testów zalicza gotowy program). Podobnie jest, gdy zaimplementuje się rozwiązanie, które jest algorytmicznie błędne: program dla prawie każdego testu udziela wtedy złej odpowiedzi i otrzymuje najczęściej zero punktów. Żeby dostać punkty, trzeba więc całość doprowadzić do końca.

Zaskoczyło mnie bardzo, że dla zawodników łatwiejsze okazało się zadanie Szpiedzy niż zadanie Spirala. Między innymi dlatego właśnie postanowiłem o tych właśnie zadaniach napisać. Wygląda na to, że zawodnicy, którzy przygotowują się do olimpiady naprawdę się czegoś uczą: kilka lat wcześniej na finale pojawiło się zadanie na podobne techniki jak w zadaniu Szpiedzy (zadanie Ciężarówki 2) i wtedy wyniki zawodników na tym zadaniu były niskie. Nie widzę innego wyjaśnienia tej sytuacji jak takie, że zadania, które pojawiły się już na olimpiadach, są później wykorzystywane do treningu przyszłych pokoleń i dzięki temu wiedza w nich zawarta staje się powszechniejsza. Jeżeli naprawdę tak jest, to wartość olimpiad w moich oczach rośnie jeszcze bardziej. Chciałbym natomiast zrozumieć, dlaczego zadanie o spirali nie było dla finalistów atrakcyjnym kąskiem na zdobycie dużej liczby punktów. Wydawało mi się przed zawodami, że to będzie właśnie zadanie “pocieszenia”, które choć może nie jest trywialne, to nie wymaga dużej wiedzy, ani długiej implementacji, a więc zostanie pokonane przez dużą liczbę zawodników.

A może Wy, Czytelnicy, znajdujecie jakieś inne uzasadnienie, które mi umyka? Sekcja komentarzy pozostaje otwarta. Zachęcam do wyrażania swoich opinii.