Konkursy algorytmiczne i ich rola w moim życiu

Postanowiłem zebrać do kupy materiały, które gdzieś kiedyś wytworzyłem, mają jakąś wartość edukacyjną a jak do tej pory leżały gdzieś nie uporządkowane w czeluściach internetu, czy na moim dysku...

Tym sposobem, chciałbym dzisiaj poruszyć temat konkursów algorytmicznych, którym przez pewien okres poświęcałem naprawdę bardzo dużo czasu w swoim życiu.

Ile trzeba umieć, by zacząć startować w konkursach algorytmicznych?

Programowanie jest podobno trudne, a skoro są robione jakieś konkursy dla programistów, to łatwo można wysnuć tezę, że pewnie biorą udział w takich konkursach tylko najlepsi z najlepszych.

Jeżeli należysz do osób, które tak myślą, to jesteś po części w dużym błędzie!

Owszem, konkursu algorytmicznego nie wygra na pewno żaden amator. Reguły takich zawodów są bardzo ściśle określone i w bardzo brutalny sposób są weryfikowane twarde umiejętności zawodników.

Nie każde zawody są tworzone z myślą o mistrzach świata ;)

Nic jednak nie stoi na przeszkodzie, by w pierwszych fazach takich konkursów udział wzięły osoby, które dopiero co rozpoczęły swoje przygody z programowaniem. Wygrać pewnie nie wygrają, ale skoro weryfikacja umiejętności takich zawodników odbywa się automatycznie to znaczy, że koszt oceny takiej osoby, jest praktycznie pomijalny.


Jest naprawdę dużo stron, na których można znaleźć zadania, które polegają na zaprogramowania dosłownie prostej procedury dodawania, czy obliczenia średniej dwóch liczb - serio :)

Automatyczny sędzia i typ zadań

Największą trudnością w takich zawodach dla początkującej osoby jest tak naprawdę wdrożenie się i zrozumienie reguł takich zawodów i nauczenie się specyficznego sposobu pisania programów pod "automatycznego sędziego".

Na co dzień w życiu gdy piszemy jakiś program, piszemy go w taki sposób, by wygodnie się z niego nam korzystało. Dlatego jesteśmy przyzwyczajeni, że dobry program użytkowy ma obsługę zarówno myszki jak i umożliwia obsługę za pomocą klawiatury.... no i oczywiście korzysta z ekranu wyświetlając odpowiednie komunikaty, czy wyniki swojej pracy.

Programowanie programów z GUI nie ma nic wspólnego z konkursami algorytmicznymi.

Konkursy algorytmiczne to raczej tworzenie prostych programów konsolowych

Konkursy algorytmiczne mają na celu sprawdzenie umiejętności stworzenia programu, który w wyznaczonym czasie wykona określone zadanie. W 98% przypadków zadaniem jest obliczenie jakieś liczby, czy zbioru liczb będącej wynikiem/rozwiązaniem jakiegoś problemu.

Skoro programy w takich konkursach ostatecznie mają zwrócić tylko liczby będące wynikiem, to oznacza, że wszystko inne... grafika, wygląd programu, język narodowy interfejsu programu, a nawet język programowania w jakim program został napisany... to wszystko nie ma znaczenia, bowiem wszystko co ma program zrobić, to wypisać liczbę.

A co jest fajne w liczbach? To, że komputery świetnie je rozumieją, co z kolei oznacza, że można napisać programy, które automatycznie sprawdzają poprawność wyników zwracanych przez programy zawodników :)

Skoro programy zawodników mają być sprawdzane przez inne programy to oznacza, że reguły prezentacji wyników muszą być bardzo jasno sprecyzowane... bowiem automatyczny sędzia - program, o ograniczonych zdolnościach, nie koniecznie musi wiedzieć, że 3.0 to tyle samo co 3. Dlatego tak ważne jest zawsze zapoznanie się z informacją, w jakim formacie ma być wypisany wynik (bardzo często nawet liczba spacji i enterów pomiędzy liczbami może mieć znaczenie, więc trzeba być dokładnym ;) )

Rodzaje zadań

Zadania są naprawdę bardzo różne. Do rozwiązania niektórych wystarcza wiedza z zakresu 1 klasy szkoły podstawowej, w przypadku tych najtrudniejszych... nie będę was straszył :P

Przykład prostego zadania:

Napisz program, który otrzymując datę w formacie dd-mm-rrrr wypisze liczbę dni, jaka minęła od zadanej daty.

Co ważne, zadanie polega nie tylko na tym, by napisać program który potrafi odpowiedzieć ile dni minęło np. od 1 maja 1984 roku. W takim przypadku wystarczyło by napisać program który zwraca pojedynczą liczbę. Trudność w takich zadaniach polega na tym, że nie wiemy o jaką datę program sprawdzający nasz program poprosi. Może być to każda data, która mieści się w zakresie danych, które zostały w treści przedstawione. W powyższym przykładzie nie zostało to napisane, ale oprócz treści opisowej, obok zadania powinny znajdować się informacje z jakiego zakresu danych nasz program może być odpytywany, np. "program powinien zwracać prawidłową odpowiedź dla wszystkich dat XX wieku". Mając taką informacje dostajemy tak naprawdę jednocześnie podpowiedź, że można olać większą część dat, w tym także np. obsługę dat przed rokiem 0.

Zadania treningowe

Piszę niby cały czas o konkursach, ale prawda jest taka, że wcale nie trzeba się zmagać z innymi w trybie konkursowym, bowiem można brać udział w czymś co przypomina raczej "zawody stałe". W dużym skrócie, jest po prostu duża pula zadań, od bardzo łatwych, do bardzo trudnych.... i można je robić sobie po kolei, w dowolnej kolejności. Bez limitów czasowych na napisanie programu, bez stresu... dla czystej wiedzy i satysfakcji :)

Tego rodzaju zadania można rozwiązywać m.in. w serwisie http://pl.spoj.com/ :)

Też mam tam konto i pomimo tego, że od prawie 2 lat nic tam nie robiłem (o... tutaj jest moje konto), to gwarantuje wam, że gdybym tylko teraz nie zajmował się czymś innym, to nadal z chęcią poświęcałbym długie godziny na rozwiązywanie kolejnych zadań :)

Generalnie rzecz biorąc, najlepsze jest to, że takie zadania swoją specyfiką są naprawdę identyczne w stosunku do tych, które faktycznie można spotkać na różnego rodzaju innych konkursach, takich jak na potyczkach algorytmicznych :)

Małe szkolenie video

Prawdę mówiąc, cały ten wpis powstał tylko po to, by na koniec móc umieścić film, który kiedyś nakręciłem. Trwa on trochę, nie śpieszyłem się jak go nagrywałem, ale za to starałem się przekazać wiedzę, która innym może umożliwić łatwy start ;)

no i na koniec jeszcze jedno...

Dlaczego warto interesować się konkursami algorytmicznymi?

Uważam, że są programiści i klepacze kodu. Klepacz kodu to w moim mniemaniu taki programista, który niby normalnie programuje, ale to co robi równie dobrze może być wykonane przez zastąpienie go skończoną liczbą studentów.

Według mnie, prawdziwy programista to taki, który raz na jakiś czas staje przed problemem nietrywialnym, wymagającym zdolności matematycznych i algorytmicznych i to nie jest dla niego przeszkodą nie do przejścia :) Język programowania dla niego to tylko technologia, wie, że to w matematyce tkwi sekret optymalizacji.

Algorytmice poświęcałem się szalenie intensywnie przez 3 lata swojego życia (2 klasa liceum, w 3 klasie algorytmy na chwilę odpuściłem by skupić się na maturze, natomiast ze zdwojoną mocą powróciłem do nich na 1 i 2 roku studiów).

Poświęcałem im tak dużo czasu, że moja ówczesna dziewczyna non stop miała do mnie pretensje, że siedzę tylko na "tymi głupimi zadaniami", które "i tak mi nic nie dadzą". Ja wiedziałem swoje :)

Z tamtą dziewczyną się rozstałem, a parę miesięcy później na rozmowie kwalifikacyjnej w Operze, dostałem 3 pytania. Wszystkie dotyczyły zadań algorytmicznych :)

Gdy usłyszałem dwa pierwsze pytania, to niemalże nie umiałem wytrzymać ze śmiechu :) Zadania te były bowiem bardzo podobne do zadań, które już wcześniej rozwiązywałem. Były inne, ale gdy miałem podać odpowiedź, to będąc aż tak pewnym swojej wiedzy, zapytałem się aż, które utrudnienie związane z optymalizacją rozwiązania mam dodatkowo zastosować.

W praktyce muszę przyznać, że tego typu pytania na rozmowie nie były na wyrost. W przyszłości nie raz potem się okazało, że bez podstawowej wiedzy algorytmicznej, w niektórych projektach ani rusz... ;)