Nasza strona używa cookies. Korzystając ze strony, wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki. Rozumiem

Jak przygotować się na olimpiadę programistyczną

Andrei Margeloiu Masters Student / University of Cambridge
Sprawdź, jak student pokonał w olimpiadzie programistycznej koderów z pięcioletnim doświadczeniem i wyciągnij z tego naukę dla siebie.
Jak przygotować się na olimpiadę programistyczną

Zacząłem się uczyć C++ podczas pierwszego roku w liceum. Nie wiedziałem nic o programowaniu, algorytmach i strukturach danych. Siedem miesięcy po tym, jak napisałem swoją pierwszą linijkę kodu, do drzwi pukała już Olimpiada Komputerowa.  

To była perfekcyjna okazja, aby przekonać się, czy mój styl nauki był coś warty. Po dwóch dniach zmagań przyszły wyniki: wygrałem złoty medal. 

Byłem w szoku, bo pokonałem programistów z pięcioletnim doświadczeniem. Wiem, że ciężko na to pracowałem, ale to osiągnięcie przeszło moje najśmielsze oczekiwania. Ten konkurs świetnie do mnie pasował, więc poszedłem na całość. 


Wiem, dlaczego wygrałem

Który język najlepiej wybrać?

  1. C++ - mocno polecam! Bardzo szybki język. Implementacja różnych algorytmów nie zajmuje wiele czasu, ze względu na STL. C++ akceptuje się we wszystkich konkursach. Piszę w nim od pierwszej linijki kodu. 
  2. C - naucz się C++ ze względu na STL. Jeśli znasz C, dasz sobie radę w C++. 
  3. JAVA - wolny język. Zaletą jest klasa BigInteger, pomimo małej liczby problemów, których rozwiązanie jej wymaga. Jeśli limit czasowy jest krótki, to zawsze można go przedłużyć. Java nie jest akceptowana w niektórych konkursach.


Gdzie możesz ćwiczyć?

Polecam Sphere Online Judge (SPOJ). Nauka tam jest efektywna z punktu widzenia ilości i jakości. Jeśli utkniesz na jakimś problemie, do dyspozycji masz artykuły i solucje. Odwiedź również SPOJ Toolkit oraz Problem classifier for SPOJ.pl


Po pierwsze, opanuj podstawy

Po przywyknięciu do składni języka nadchodzi czas na rozwiązanie kilku problemów. Zacznij od tych prostych, które wymagają umiejętności implementacyjnych. Twoim celem jest tutaj zdefiniowanie swojego stylu kodowania. Może lubisz stawiać spacje albo nawiasy w tej samej linijce, co if.

Musisz zdefiniować swój styl, ponieważ jest “Twój”. 

Rozwijając swój kod, miej na uwadze dwie poniższe zasady:

  • Łatwość implementacji. Implementacja rozwiązania, które się wymyśliło, powinna być łatwa. Dlaczego? Bo nie chcesz się zgubić we własnym kodzie podczas konkursu. Zawsze lepiej pomyśleć 5 minut dłużej nad implementacją niż spędzić 10 minut więcej robiąc ją. 
  • Łatwość czytania. Co po prostu oznacza “łatwość w debugowaniu”. Wszyscy wiemy, że błędy się ciągle pojawiają. Znasz to uczucie, kiedy zostaje Ci 10 minut, a za nic nie jesteś w stanie znaleźć tego jednego błędu? Aby unikać takich rzeczy, trzeba pisać czytelny kod. Kiedy zatem zaczynasz debugować, za kodem powinno się podążać naturalnie i płynnie. 


Jak zwiększyć swoje umiejętności implementacyjne?

Ćwicz, ćwicz i jeszcze raz ćwicz. Polecam zająć się pierwszymi 250 najpopularniejszymi problemami na SPOJ. Rozwiąż je w takiej samej kolejności jak na stronie. Myśl nad każdym rozwiązaniem przynajmniej godzinę. 

Nie porzucaj danego problemu, bo jest za ciężki - to podejście pasujące do przegranych. 

Weź kawałek papieru, ołówek i na spokojnie się zastanów. Tak prawdopodobnie znajdziesz rozwiązanie, ale na pewno rozwiniesz w sobie myślenie algorytmiczne. Jeśli nie wpadniesz na odpowiedź w godzinę, sprawdź forum dyskusyjne lub artykuły i zobacz rozwiązanie. 

Jakie są skutki takiego podejścia do sprawy? Szybka implementacja i nauka klasycznych problemów i algorytmów. 


Po drugie, opanuj algorytmy i struktury danych 

Kieruj się hierarchią. Czy zaczniesz biegać, nie umiejąc chodzić? Czy wybudujesz wieżowiec bez solidnego fundamentu? Nie!

Pewnych rzeczy nie przeskoczysz, a jeśli będziesz próbować, to pozostaną Ci braki w wiedzy, które się powiększą w miarę upływu czasu. 

Zacznij z podstawowymi algorytmami i strukturami danych

Ciężko jest zacząć, a dzieje się zapewne dlatego, że nie wiadomo, od czego zacząć. Dlatego też stworzyłem ten kurs wideo. Zrobiłem go w taki sposób, w jaki sam chciałbym się uczyć. Odzew był niesamowity! Dołączyło do niego ponad 3000 uczniów z ponad 100 różnych państw w trakcie pierwszego miesiąca. 

Jeśli zajmujesz się tylko prostymi rzeczami, nigdy nie staniesz się lepszy. Najbardziej efektywną metodą rozwoju jest wychodzenie poza strefę komfortu. Dla mnie takie podejście zadziałało świetnie. Nauczyłem się wielu nowych technik, o których nigdy wcześniej nie słyszałem, przez to właśnie, że wybrałem ciężki problem. 

Na każde 3 problemy, które rozwiązujesz, jeden powinien nauczyć Cię czegoś nowego. Jeśli tak nie jest, ostrożniej je dobieraj. Wybieraj ciężkie problemy!

Zakończenie tych 250 problemów z SPOJ pozwoli na zorientowanie się w głównych tematach w programowaniu konkursowym. Zrozumienie podstawowych algorytmów pozwoli na ogarnięcie tych wysokopoziomowych. Możesz wtedy szybko wykorzystać swoją wiedzę. 

Zagłębiaj się w każdy z głównych tematów


Oto ogromne źródło z top 10 algorytmów i struktur danych w każdym temacie. Po przerobieniu tych 250 problemów z SPOJ rozpoznasz tam wiele pozycji. Będzie też niestety sporo, o których możesz nie mieć pojęcia. Zacznij więc naukę w sugerowanej kolejności. 

Jeśli nie utrwalisz nabytej wiedzy, to o niej zapomnisz. 

Nauczywszy się jakiegoś nowego algorytmu, polecam użyć go w 2-3 problemach. Wyszukaj tag algorytmu na SPOJ, a odnajdziesz problemy, które go wymagają. Zajmij się nimi, zanim zaczniesz robić cokolwiek innego. 

Zrozum programowanie dynamiczne, bo dzięki niemu wygrasz. 

Z własnego doświadczenia, na każdym konkursie jest co najmniej jedno pytanie dotyczące programowania dynamicznego. Koncept ten przyprawia wielu o ból głowy, bo go nie rozumieją. 

I dobrze, bo jak dobrze zrozumiesz programowanie dynamiczne, to będziesz zwycięzcą. Szczerze, to jest to mój ulubiony temat, a jego sekret brzmi: myśl globalnie, a nie lokalnie. Musisz rozbić problem na mniejsze komponenty, rozwiązując każdy z nich tylko raz i budując całościowe rozwiązanie przez połączenie tych małych komponentów. 

Przeciwieństwem programowania dynamicznego jest algorytm zachłanny - wybiera on rozwiązanie lokalnie optymalne na każdym kroku. Rozwiązania optymalne lokalnie mogą skutkować rozwiązaniem, które jest niekorzystne globalnie.

Ucząc się nowych rzeczy, sprawdź tutoriale TopCodera. Są one bardzo szczegółowe i dodatkowo są bardzo przystępne. Udało mi się dzięki nim dobrze zrozumieć drzewa indeksowane binarnie

Ciężko pracuj

Słyszałeś kiedyś o sportowcu, który wygrał Olimpiadę bez lat praktyki? Bo ja nie. 

Każdego roku przygotowania do Olimpiady komputerowej w USA zaczynają się we wrześniu, a kończą w kwietniu. 

W ciągu tych 8 miesięcy ćwiczyłem 5 godzin każdego dnia. 

Tak było, 5 godzin tylko z problemami algorytmicznymi. Pamiętam dni, w których ćwiczyłem od 8 do 10 godzin. Dlaczego? Bo mnie to kręciło. Każdego dnia po przyjściu ze szkoły szedłem prosto do mojego pokoju, żeby zająć się nowym problemem. Albo, żeby nauczyć się nowego algorytmu potrzebnego do jego rozwiązania. 

Jeżeli chcesz wygrać, musisz zrobić to samo. Weź jakiś problem i trzymaj się rozwiązywania go. Myśl o nim podczas swojej codziennych czynności, takich jak, droga do supermarketu, czy dojazd do szkoły/pracy. 

Czy wiesz, że podczas snu Twój mózg defragmentuje informacje nagromadzone w ciągu dnia? To jak układanie książek w kolejności alfabetycznej na półce. Twój mózg też może sobie w taki sposób układać te problemy. 

Oto jak możesz to wykorzystać. Przed pójściem spać, przeczytaj jakiś trudny problem i pamiętaj, czego potrzeba do jego rozwiązania. Nie musisz znajdować rozwiązania od razu. Potem idź spać, a Twój mózg zacznie przetwarzać ten problem. Kiedy się obudzisz, możesz być zaskoczony, że rozwiązanie przyszło podczas snu. 

Spróbuj sam - to magia. 

Pracuj mądrze

Oto sekret do sukcesu - potrzebne są Ci targety. 

Jako ludzie lubimy prokrastynować. Oznacza to odkładanie rzeczy, które trzeba zrobić teraz, na później. Zawsze fajniej jest obejrzeć sobie Netflixa niż rozwiązywać zadania z programowania. Znasz to i musisz sobie z tym poradzić. 


Jak pokonać prokrastynację? 

Przez określanie celów. Zawsze znajdą się jakieś problemy, z których możesz się czegoś nowego nauczyć (sprawdź źródła, które dałem powyżej). Te problemy muszą jednak zostać rozwiązane, a nie przeczytane. 

Oto jak mi udało się poradzić z prokrastynacją. Stworzyłem sobie kalendarz i wypełniłem go problemami, które każdego dnia chciałem rozwiązywać. Zawsze robiłem to dwa dni przed danym problemem, żebym mógł sobie to wszystko na spokojnie zaplanować. 

W taki sposób zawsze byłem zmotywowany do rozwiązania problemów i szukania następnych, którymi mógłbym wypełnić kalendarz. Rozwiązanie problemu daje dużą satysfakcję. Wiem, że też to lubisz. 

Aha, ważna rzecz: zrób to w papierowym kalendarzu, bo o checkliście w telefonie zapomnisz już następnego dnia. 


Jak efektywnie degubować?

Chcesz zostać prosem? Jeśli tak, to musisz “debugować w myślach.” To moim zdaniem najlepszy sposób, ponieważ nie wymaga debuggera. Twój mózg bada wiele ścieżek w kodzie jednocześnie i daje większą perspektywę w porównaniu do klasycznego debuggera. 

Podobnie jest w przypadku arcymistrzów szachowych, którzy potrafią planować trzy ruchy do przodu. Używam tej techniki jako moja początkowa linia obrony, a dopiero potem używam debuggera. 

Aby nauczyć się debugować w taki sposób, trzeba ćwiczyć. Kiedy dostarczysz dany problem i otrzymasz “złą odpowiedź”, nie idź do debuggera. Zamiast tego zacznij czytać kod i pomyśl, “co stało się w tej linijce?”, “w jaki sposób wrażenie “if” wpływa na program?”, “Jeśli opuścimy pętlę, jaka jest wartość iteratora?”.

Dzięki temu zaczynasz myśleć samodzielnie. Z czasem zaczniesz debugować podczas pisania kodu. 



Oryginał tekstu w języku angielskim przeczytasz tutaj.

Rozpocznij dyskusję

Lubisz dzielić się wiedzą i chcesz zostać autorem?

Podziel się wiedzą z 160 tysiącami naszych czytelników

Dowiedz się więcej