Zacznijmy od smutnej prawdy. Nie zostaniesz mistrzem w programowaniu konkursowym, czytając jedynie tego bloga. Należy jeszcze rozwiązywać zadania.
Zacznijmy od miejsc w których moglibyśmy rozwiązywać zadania. A jest ich sporo. Nie wszystkie z nich znam i z nie wszystkich korzystałem. Strony, które mogę polecić to:
- Codeforces – strona na której obecnie trenuje. Zawiera ona blisko 7500 zadań o zróżnicowanym poziomie trudności. Każde zadanie zawiera omówienie. Masz również dostęp do rozwiązań innych uczestników, a użytkownicy mają możliwość tworzenia własnych blogów. Dzięki temu strona ta świetnie nadaje się do celów edukacyjnych. Strona organizuje liczne zawody w których zawodnicy są klasyfikowani za pomocą rankingu ELO (podobnego używa się np. w szachach albo rankingu FIFA).
- Szkopuł – jeśli przygotowujesz się do olimpiady informatycznej, olimpiady informatycznej juniorów albo potyczek algorytmicznych – powinieneś zapoznać się z tą stroną. Zawiera ona zadania z poprzednich edycji wszystkich wymienionych konkursów.
- SPOJ – polska strona zawierająca około 4000 zadań. Jest to swoisty ranking w którym zawodnicy konkurują w liczbie rozwiązanych problemów. W związku z tym, zadania nie zawierają omówień i nie możemy podejrzeć rozwiązań innych zawodników (niektórzy publikują swoje rozwiązania na githubie).
- Online Judge – strona zawierająca zadania z Mistrzostw Świata w Programowaniu Zespołowym.
- Timus Online Judge – rosyjska strona z zadaniami.
- USACO training program – strona przygotowująca do amerykańskiego odpowiednika Olimpiady Informatycznej. Jest już trochę przestarzała.
- Codechef – Jedyna w tym zestawieniu strona, z której nigdy nie korzystałem. Zawiera wiele problemów, wiele z nich ma omówienie w formie video.
Niektórzy polecają robienie zadań z różnych stron, inni sugerują aby skupiać się na jednej. Osobiście nie mam preferencji.
Wykonywanie ćwiczeń na Twoim poziomie jest proste. Należy rozwiązywać duże ilości zadań. Później forma ćwiczeń robi się coraz bardziej skomplikowana. Oczywiście nie wszystkie zadania jesteś w stanie w tej chwili rozwiązać. Brakuje Ci jeszcze wiedzy z programowania, algorytmiki i matematyki. Wiedzę tę będziesz systematycznie zdobywał czytając tego bloga.
W jaki sposób wyszukiwać zadania proste, które jesteś w stanie rozwiązać? Na stronie codeforces możesz poszukać zadań o rankingu 800. Wciąż nie wszystkie jeszcze będziesz w stanie rozwiązać, ale dużo z nich powinno być w Twoim zasięgu (zwłaszcza za kilka kolejnych lekcji). Na stronie SPOJ zadania można posortować według liczby osób, które dane zadanie rozwiązała. Możesz w ten sposób spróbować zacząć od zadań prostszych, ewentualnie omijając te w których wymagana jest dodatkowa wiedza (zwróć uwagę, że najprostsze zadanie to nie koniecznie to, które rozwiązało najwięcej osób; zadania, które pojawiły się na stronie stosunkowo dawno będą miały większą liczbę rozwiązań niż zadania nowe, nawet jeśli są trudniejsze). Jeśli chodzi o zadania z ubiegłych olimpiad informatycznych, to nie są znane mi proste sposoby wyszukania zadań łatwych. Poradziłbym tutaj poproszenie o pomoc starszych kolegów zajmujących się programowaniem konkursowym albo zatrudnienie trenera.
Aby wysłać swoje pierwsze zgłoszenie, musicie najpierw założyć konto na wybranym serwisie. Na codeforces możecie to zrobić pod linkiem https://codeforces.com/register. Jedyne co musicie zrobić to podać swój nick (handle), adres e-mail oraz wybrać hasło. Jeśli macie konto Google albo Facebook to możecie się zalogować przez to konto.
Po przejściu do zakładki problemset, naszym oczom ukarze się lista zadań. Z prawej strony możemy wybrać trudność zadań oraz tag. Jeśli na przykład chcemy przećwiczyć zadania z programowania dynamicznego, możemy wybrać tag DP. Zadania możemy posortować po liczbie osób, która je rozwiązała. Robimy to wciskając trójkąt obok znaku zielonego ptaszka. Polecam w okienku settings odznaczyć “show tags for unsolved problems”. Tagi sugerują mocno jakiej techniki należy użyć w danym problemie. Oczywiście na zawodach wybór odpowiedniej techniki jest częścią zadania i warto go ćwiczyć od samego początku.
Po wybraniu zadania, pojawi nam się jego treść. Po przeczytaniu, rozwiązaniu i zaimplementowaniu rozwiązania, możemy sprawdzić czy nasz program działa poprawnie wysyłając plik z kodem źródłowym. Odpowiednie okienko powinno się znajdować z prawej strony.
Zwróć uwagę, aby wybrać dobry kompilator! Standardowo okienko jest ustawione na język C, podczas gdy my piszemy w języku C++. Wciskamy przycisk Przeglądaj… aby wybrać plik z naszego dysku i na końcu klikamy Submit. Zostaniemy przeniesieni na stronę z naszymi zgłoszeniami:
Jeśli nasze rozwiązanie jest prawidłowe, powinniśmy otrzymać komunikat Accepted (z okazji nowego roku, niektóre komunikaty Accepted zostały zamienione na Happy New Year! Jeśli nie zapomnę, to zrobię w lutym nowy zrzut tego ekranu, edit: zapomniałem). Komunikaty z jakimi możemy się jeszcze spotkać to: Wrong Answer oznaczający, że nasz program dał niepoprawną odpowiedź, Runtime Error – nasz program wykonał nie poprawną operację, Time Limit Exceeded – nasz program działał za wolno, Memory Limit Exceeded – nasz program zużywał za dużo pamięci (jak Chrome) oraz Compilation Error – program nie skompilował się poprawnie (sprawdź czy wybrałeś dobry kompilator).
Zadania do samodzielnego rozwiązania
Poniżej umieszczam linki do zadań, które rozwiązaliśmy w poprzednich notkach. Powinieneś być w stanie je wszystkie rozwiązać. Uważaj jednak. Zadania mogą różnić się od tych przedstawionych na blogu drobnymi szczegółami. Od teraz pod każdą notką postaram się umieścić 5 problemów o różnym stopniu trudności.
- Make Even (ranking 800)
- Construct a Rectangle (ranking 800)
- Bear and Big Brother (ranking 800)
- Filling Diamonds (ranking 900)
- Theatre Square (ranking 1000)
