Godne polecenia: Internetowe Turnieje Programistyczne
Drużynowa nauka programowania i algorytmiki. Finansowana ze środków budżetu Państwa.
Spis treści
Rok szkolny dawno się już rozpoczął, rok akademicki również, wpadłem w wir dydaktyki i dawno nie miałem czasu niczego napisać na bloga. Czasu było mało również dlatego, że zbliżają się Mistrzostwa Szkół Średnich w Programowaniu Zespołowym, w ramach projektu ministerialnego Mistrzostwa w Algorytmice i Programowaniu. Mistrzostwa odbędą się już za tydzień, a ja już wiem, że to będzie coś dużego. Skąd to wiem? Bo w eliminacjach do tych zawodów wystartowało około 200 drużyn z całej Polski, a walka była zacięta. A że coś tam wiem o organizacji takich imprez to postaram się w tym wpisie przybliżyć specyfikę zawodów.
Projekt MAP i inne inicjatywy wspierane przez Ministerstwo
Stali czytelnicy tego bloga wiedzą, że nie zawsze pochwalam rozwiązania w zakresie edukacji serwowane nam przez organy rządowe (ot choćby tutaj sobie trochę ponarzekałem). Czasami jednak nawet naszym politykom i urzędnikom (z różnych opcji rządzących) zdarza się wymyślić coś dobrego (lub choćby wdrożyć dobry pomysł podsunięty przez jakiegoś eksperta). Tak też stało się w roku 2019, gdy ogłoszono Program Rozwoju Talentów Informatycznych na lata 2019-2029. Nazwa wskazuje na niebywały rozmach działań, w ramach projektu znalazły się konkursy na organizację edukacji dla uczniów i studentów. Skupię się tutaj na części dla uczniów, o której wiem znacznie więcej. Działania skupiały się na nauczaniu uczniów oraz nauczycieli informatyki tematyki algorytmicznej i programowania, na różnych poziomach zaawansowania. Niektóre działania były kierowane do ścisłego topu: najlepszych zawodników z Polski, zdobywających medale w Międzynarodowej Olimpiadzie Informatycznej (tak, regularnie mamy takie osiągnięcia! link), a niektóre działania skupiały się na popularyzacji tej tematyki i tworzeniu nowych miejsc na mapie Polski, gdzie można znaleźć nauczycieli i uczniów co najmniej rozumiejących czym jest algorytmika i programowanie.
W ramach projektu zorganizowano:
- turnieje indywidualne i drużynowe, w których uczniowie rozwiązywali zadania przez internet sprawdzane przez automatyczny system,
- naukowe obozy informatyczne (około tygodniowe wyjazdy do ośrodków szkoleniowych dużych grup uczniów i nauczycieli z różnych szkół),
- kółka informatyczne w szkołach (na różnych poziomach zaawansowania),
- webinaria tematyczne (np. o analizie języka),
- dłuższe tematyczne kursy online (np. o sztucznej inteligencji),
- warsztaty dla nauczycieli,
- spotkania z mistrzami (np. z Tomkiem Czajką),
- Mistrzostwa Szkół Średnich w Programowaniu Zespołowym.
Film, który w skrócie pokazuje niektóre z tych działań znajduje się pod tym linkiem.
Działania były w dużej mierze wykonywane przez pracowników, studentów i absolwentów dwóch uczelni wyższych: Uniwersytetu Warszawskiego oraz Uniwersytetu Wrocławskiego. Ci, którzy obserwują konkursy programistyczne dla uczelni, zapewne wiedzą, że był to wybór nieprzypadkowy. Studenci tych uczelni (obok studentów z Uniwersytetu Jagiellońskiego) regularnie kwalifikują się do Akademickich Mistrzostwach Świata w Programowaniu Zespołowym (ICPC) i co jakiś czas uzyskują tam wyniki, które można uznać za spektakularne. Nie ukrywam, że zdarzyło mi się pomagać w niektórych z tych działań, dlatego oczywiście moja ocena może być nieco zaburzona. Nie potrafię sobie jednak wyobrazić, że wtedy istniały (lub istnieją teraz) lepsze podmioty do prowadzenia takiego projektu.
Ministerstwo zdecydowało się zaprzestać finansowania projektu w roku 2022. Była to dla mnie (i myślę, że nie tylko dla mnie) decyzja niezrozumiała, szczególnie, że w końcu było blisko, żeby udało się poszerzyć wiedzę o tym, że można próbować osiągać najwyższe rezultaty w informatyce na więcej niż tylko kilka największych ośrodków w Polsce, gdzie akurat znajdują się najlepsze licea. Na szczęście, po dwóch latach przerwy, projekt wrócił, ponownie w ręce tych samych organizatorów.
Zadania na turnieju kwalifikacyjnym
Nie byłbym sobą, gdybym nie przedstawił chociaż jednego zadania, żeby pokazać o czym są te całe turnieje czy Mistrzostwa.
Najłatwiejsze zadanie
Najłatwiejsze zadanie (Tempo biegu) polegało na przygotowaniu programu, który przeliczy prędkość w kilometrach na godzinę na tempo biegowe (czas potrzebny na pokonanie jednego kilometra). Przykładowo: biegacz, który biegnie z prędkością 10 km/h pokonuje każdy kilometr w ciągu 6 minut. Taką też informację najczęściej odczytuje ze swojego zegarka i tak też myśli o ewentualnym przyspieszaniu biegu (zamiast myśleć, że chce przyspieszyć do 11 km/h, raczej myśli o tym, że chce poprawić tempo do 5:27/km). Napisanie programu nie jest dużą trudnością, trzeba być ostrożnym na ewentualne niedokładności typów zmiennoprzecinkowych (które w skrajnych przypadkach mogą spowodować, że program pomyli się o jedną sekundę, co na takich zawodach jest nieakceptowalne).
Zawodnicy, po przygotowaniu programu (np. w C++ lub Pythonie), przesyłają go na serwer zawodów i na bieżąco otrzymują informację czy ich zgłoszenie jest zaakceptowane czy nie (i ewentualnie z jakiego powodu nie: czy jest to spowodowane tym, że program udzielił błędnej odpowiedzi lub przedwcześnie zakończył swoje działanie z błędem albo przekroczono limit czasu lub pamięci na wykonanie obliczenia). Złe rozwiązania można poprawić, ale po ostatecznym zaliczeniu zadania przyznawane są karne minuty za wcześniejsze pomyłki.
Najtrudniejsze zadanie
Jedno z najtrudniejszych zadań polegało na próbie dokonania (a co najmniej analizy) pewnego odkrycia matematycznego.
Treść zadania jest dostępna do pobrania tutaj.
Streszczając: matematycy rozważali kiedyś problem superpermutacji: wygenerowania możliwie krótkiego napisu, który zawierałby w sobie jako spójne fragmenty wszystkich permutacji napisu 1234...N.
Na przykład, gdy $N = 3$, nasz napis musi zawierać fragmenty 123, 132, 213, 231, 312, 321.
Przykładowym najkrótszym napisem spełniającym warunki zadania jest 123121321.
W treści zadania otwarcie napisane jest, że naukowcy zastanawiali się nad tym problemem i pojawiła się hipoteza, że najkrótszy napis ma zawsze długość $1! + 2! + 3! + \ldots + N!$. Hipotezę sprawdzono dla $N \in {1, 2, 3, 4, 5}$ i nie znaleziono kontrprzykładu. Aż do momentu, w którym Robin Houston użył dostatecznie szybkiego programu, żeby obalić hipotezę dla $N = 6$, znajdując napis o jeden znak krótszy niż wynikałoby to z hipotezy. Zadaniem zawodników było napisać program, który znajduje napis o pięć znaków krótszy (niż wynikający z hipotezy) dla $N = 9$. Program musiał na typowym komputerze wygenerować napis o długości nie przekraczającej $409\ 108$ w czasie nie przekraczającym dwóch sekund. Rozwiązanie zadania wymagało trochę sprytu, wiary i przeszukania interenetu w celu znalezienia stosownych informacji. Osoby, które zainteresowałem tematem superpermutacji zachęcam do przejrzenia poniższego filmu z autorem oryginalnego osiągnięcia.
Problemy ze sztuczną inteligencją
Przy tak dużej liczbie zawodników (ponad 200 drużyn, większość po trzech zawodników) zdarzyły się pewne zagrania niezgodne z duchem fair play. Zawodnikom zdarzało się pytać ChatGPT o rozwiązania zadań (co widać po stylu kodów jakie nadesłali na serwer zawodów i podobieństwach między nimi). Z jednej strony nie mogę powiedzieć, żeby osiągnięcia czatu nie były imponujące. Czat wygenerował kody, które prawidłowo rozwiązują nawet niektóre całkiem trudne zadania, które mogły sprawić kłopot również zawodnikom doświadczonym. Z drugiej strony, na szczęście w każdym z tych przypadków programy nie były dostatecznie wydajne, żeby zaliczyć wszystkie testy w limicie czasu i pamięci.
Na razie zatem (nawet w świetle najnowszego modelu o1) jesteśmy mądrzejsi niż sztuczna inteligencja. Im dłużej o tym myślę, tym bardziej wydaje mi się, że tak jeszcze przez dłuższy czas zostanie (co najmniej w niektórych zastosowaniach, tam gdzie naprawdę liczy się precyzja i bezbłędność). Ale pamiętam też, co myślałem sobie kilka lat temu o sztucznej inteligencji i jak śmiałem się z jej wpadek. Już teraz poziom czatu jest wystarczający do tego, żeby musieć go brać pod uwagę przy sprawdzaniu prac początkujących uczniów. Już teraz czat potrafi im wyjaśnić (w niektórych przypadkach) niektóre zadania lepiej niż człowiek. Wiem też, że twórcy tego czata to osoby nieprzypadkowe: Jakub Pachocki, czyli szef naukowców w OpenAI, to były laureat Olimpiady Informatycznej i zdobywca drugiego miejsca w konkursie ICPC. Myślę, że on może mieć znacznie większą wiedzę o sztucznej inteligencji niż ja.
Wyniki drużyn
Zawodnicy poradzili sobie z zadaniami turniejowymi wyśmienicie. Prawie wszyscy, którzy zarejestrowali się do turnieju, rozwiązali poprawnie co najmniej jedno zadanie (najczęściej było to zadanie o przeliczaniu tempa biegowego). Najlepsza drużyna, z XIV Liceum Ogólnokształcącego z Warszawy, rozwiązała wszystkie zadania na więcej niż 45 minut przed zakończeniem turnieju. No cóż, jako autor zadań jestem zmuszony przyjąć tę porażkę na klatę. Szkoda, że nie byłem w stanie zapewnić im dostatecznie trudnego wyzwania, żeby chociaż jedno zadanie zostało im do zastanowienia się po zawodach. Szczęśliwie jednak, wszystkie pozostałe drużyny mają jeszcze nad czym pomyśleć (lub dowiedzą się czegoś z opublikowanego w systemie omówienia zadań), więc może nie było aż tak źle. Cieszy mnie też, że przygotowany system konkursowy, po wielu poprawkach przed turniejem, zniósł napór około 600 osób jednocześnie odświeżających stronę zawodów w pierwszych i końcowych minutach zawodów (no dobrze, przyznaję, że końcówka była już ciężka). Może chociaż na Mistrzostwach za tydzień zadania trafią w gusta również najlepszych na dzisiejszych eliminacjach. Mam taką nadzieję.
Jak nauczyć się programowania?
Nauczenie się programowania do poziomu, który pozwala powalczyć choćby z najłatwiejszymi zadaniami z dzisiejszego turnieju nie jest aż takie łatwe. Użycie ChatGPT wydaje mi się niewystarczające. Proponuję zainteresowanym osobom dołączyć do projektu MAP i przeglądać zawarte tam materiały oraz uczestniczyć w lokalnych inicjatywach realizowanych w ramach tego projektu. A jeżeli ktoś jest daleko od wszystkiego, to jakąś alternatywą jest Olimpijskie Koło Informatyczne. A gdy się uda, warto wystartować w zawodach: dla młodszych jest Olimpiada Informatyczna Juniorów, dla starszych Olimpiada Informatyczna, a dla jeszcze starszych Potyczki Algorytmiczne. Powodzenia!
Podsumowanie
Mam nadzieję, że Mistrzostwa, które odbędą się za tydzień okażą się udane. Mam też nadzieję, że projekt tym razem wytrzyma zmiany rządów i ewentualne dziury budżetowe dłużej niż ostatnio.