[OI] Przygotowanie do Olimpiady

Kangur, Alfik, Mistrzostwa w Grach Logicznych, Sejmik, Konkurs PW... Słowem - konkursy ogólnopolskie, ale nie OM.
Mati2000xcx
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 26 maja 2017, o 21:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 4 razy

[OI] Przygotowanie do Olimpiady

Post autor: Mati2000xcx »

Witam, uczęszczam do 1 klasy liceum profil mat-fiz-inf i chciałbym przygotowywać się do Olimpiady Informatycznej. Posiadam podstawy jeśli chodzi o język, przerobiłem całą książkę Stephena Praty J"ęzyk C++ Szkoła Programowania" oraz STL, wszelkie struktury danych pokroju vector, list, map itd. Zdaję sobie sprawę, że OI to konkurs ściśle związany z matematyką i gra ona tam główną rolę dlatego zwracam się na forum z prośbą o pomoc, czytałem już kilka postów jednak każdy problem jest indywidualny dlatego zdecydowałem się stworzyć własny temat. Podstawowe rzeczy jakie potrzebuje wiedzieć i jakie wprawiają mnie w zakłopotanie to algorytmy i książki potrzebne do olimpiady. Zaopatrzyłem się w "Wprowadzenie do algorytmów" Cormena i przerabiam ją powoli, jednak na forum spotkałem się z 2/3 opiniami, że przerobienie całej książki nie ma sensu zważając na jej rozmiary stąd moje pytanie do osób, które może spotkały się z tym samym problemem, które zagadnienia z tej książki przydadzą mi się w OI, druga sprawa to złożoności operacji, z tego co zasłyszałem na OI liczy się też wydajność rozwiązań i dobór odpowiednich algorytmów do konkretnych zadań, także na forum wyczytałem, że należy się zapoznać ze złożonościami i tu pojawia się problem, że kompletnie nie mam pojęcia gdzie tego szukać, próbowałem ale możliwe, że szukam w złych miejscach. Myślę, że to tyle i na sam koniec chciałbym dodać, że przygotowuje się do olimpiady sam, ponieważ w moje szkole nauczyciele uczący informatyki nie są informatykami z prawdziwego zdarzenia stąd moje zakłopotanie i pytania, które pewnie mogą wydawać się trochę bez sensu.
Gouranga
Użytkownik
Użytkownik
Posty: 1565
Rejestracja: 16 maja 2013, o 17:56
Płeć: Mężczyzna
Lokalizacja: Trójmiasto
Podziękował: 11 razy
Pomógł: 243 razy

Re: [OI] Przygotowanie do Olimpiady

Post autor: Gouranga »

Sama znajomość języka C++ ci nic nie da, jeśli nie będziesz miał podstaw z algorytmiki. To, co potrzebujesz opanować, to:
-algorytmy w teorii
-schematy blokowe
-złożoność obliczeniowa
Na pewno nie zaszkodzi też wiedza matematyczna rozszerzona, podstawowa wiedza o macierzach i takie tam.
Awatar użytkownika
Cytryn
Użytkownik
Użytkownik
Posty: 405
Rejestracja: 17 wrz 2016, o 17:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy
Pomógł: 46 razy

Re: [OI] Przygotowanie do Olimpiady

Post autor: Cytryn »

Schematy blokowe? Do czego na Olimpiadzie?
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Re: [OI] Przygotowanie do Olimpiady

Post autor: Mruczek »

Złożoność obliczeniowa?? Proste szacowanie złożoności wystarczy. Poza samą algorytmiką, podstawowa wiedza z matematyki dyskretnej może być potrzebna (grafy, kombinatoryka, teoria liczb).
Przygotowanie do OI nie polega na czytaniu książek, tylko na TRENINGU zadań przede wszystkim (MAIN, serwisy takie jak Codeforces, gdzie są systematycznie treningi, są tagi przy nazwach zadań które są wskazówką jakie typy zadań trzeba opanować, są tutoriale z rozwiązaniami, jest dostęp do kodów innych zawodników itp.). Powtarzam: TRENINGU! Tu się liczy, żeby szybko klepać bez błędów i jeszcze szybciej kminić.

Najbardziej doświadczeni zawodnicy, z pierwszych miejsc, znają większość zadań, która była na OIu, a na OIu przygotowanie się nie kończy - są konkursy międzynarodowe (BOI, CEOI, IOI, prawie każde mają swoje strony), a olimpiady informatyczne są na całym świecie. Trzeba zrobić kilkaset zadań na poziomie OI żeby być dobrze przygotowanym. Różnych zadań jest dużo i dużo jest też technik typowo olimpijskich, których w żadnych książkach nie znajdziesz.
Przygotuj sobie jakąś biblioteczkę podstawowych algorytmów (przy wykorzystaniu STLa).

Szukając informacji w internecie powinieneś zdawać sobie sprawę, że dużo więcej informacji znajdziesz po angielsku niż po polsku wpisując hasła w Google'u. To jest bardzo istotne. Hasło przewodnie: competitive programming.

Omówienia zadań z OIa i kody rozwiązań są w niebieskich książeczkach:
Przydatne linki:

Tutoriale na TopCoder: https://www.topcoder.com/community/data-science/data-science-tutorials/

Na ważniaku dużo rzeczy jest (kursy Wstęp do programowania, Algorytmy i struktury danych, Matematyka dyskretna 1).

Drogowskaz pasjonata, na dole masz OI:
[url]http://warsztatywww.wikidot.com/drogowskaz-pasjonata:olimpiady[/url]

Szczegółowo wypisane podstawowe zagadnienia:
[url]http://mokip.wdfiles.com/local--files/linki/plan_arka.pdf[/url]

Mogą się przydać rzeczy z ILOCAMPu:
[url]https://ilocamp.pl/[/url]
tutaj można znaleźć książeczki z obozów.

Cormen jest książką raczej dla studentów, może być przydatny jeżeli chcesz dowodu poprawności jakiegoś podstawowego algorytmu. Istotne jest, abyś dobrze te algorytmy rozumiał, umiał je stosować i jeżeli to konieczne zmodyfikować jakieś podstawowe rzeczy. Implementacje znajdziesz w internecie.
Rozdziały, które na pewno powinieneś przeczytać z Cormena dot.:
- sortowania (ważne żeby umieć korzystać z sorta, zdefiniować własny porządek itd.)
- programowanie dynamiczne (rekurencje)
- algorytmy zachłanne
- cały rozdział związany z grafami, bo grafy są bardzo ważne (bfs, dfs, podział na spójne składowe, sortowanie topologiczne, podział na silnie spójne składowe, minimalne drzewo rozpinające, najkrótsze ścieżki - Dijkstra, Floyd-Warshall, może też trochę przepływy;)
- struktura zbiorów rozłącznych (Find&Union)
- trochę algorytmy teorioliczbowe (np. sito Eratostenesa, rozszerzone nwd, chińskie twierdzenie o resztach)
- stringi (KMP)
- może coś z geometrii obliczeniowej, choć to raczej na finał
- listy (na wskaźnikach)
- drzewa BST

Poza tym istotne są np.:
- drzewa przedziałowe, licznikowe - coś o tym jest tutaj: [url]http://was.zaa.mimuw.edu.pl/?q=node/8[/url]
- cykle Eulera - algorytm Fleury'ego
- haszowanie: [url]http://ki.staszic.waw.pl/materialy/Haszowanie.ppt[/url]
- 2 SAT.

Czytaj Deltę - jest tam dział informatyczny z omówieniami niektórych zadań.

Poza tym przydatne mogą być książki np.
Algorytmika praktyczna Stańczyka (ale tutaj kody mogą być zbyt skomplikowane dla początkującego)
Competitive programming,
Wstęp do teorii grafów, Wilson
Matematyka Dyskretna.

Aha, i nauczycielami się nie przejmuj. (...) Istotna jest samodzielna praca. Za to w Krakowie jest V LO i może oni prowadzą tam jakieś otwarte kółko ;) Więcej dowiesz się, jeżeli pogadasz z jakimś doświadczonym zawodnikiem.
Ostatnio zmieniony 27 maja 2017, o 15:17 przez Mruczek, łącznie zmieniany 15 razy.
Mati2000xcx
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 26 maja 2017, o 21:08
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 4 razy

Re: [OI] Przygotowanie do Olimpiady

Post autor: Mati2000xcx »

Źródła były dla mnie kluczowe, napewno z tego z korzystam. Jednak jeśli ktoś miałby jeszcze jakieś rady to chętnie posłucham
Awatar użytkownika
Cytryn
Użytkownik
Użytkownik
Posty: 405
Rejestracja: 17 wrz 2016, o 17:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy
Pomógł: 46 razy

Re: [OI] Przygotowanie do Olimpiady

Post autor: Cytryn »

Całkiem fajna jest też książeczka .
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Re: [OI] Przygotowanie do Olimpiady

Post autor: Mruczek »

Zamiast MAINa teraz jest Szkopuł:

Kod: Zaznacz cały

https://szkopul.edu.pl/
.

Kursy/wykłady/skrypty C/C++:
- z materiałów studiów UMCS (skrypty z wielu przedmiotów na dole):

Kod: Zaznacz cały

https://www.umcs.pl/pl/informatyka,2557.htm

http://informatyka.umcs.lublin.pl/files ... ak_cpp.pdf

- z materałów PJWSTK:
http://edu.pjwstk.edu.pl/wyklady/
http://edu.pjwstk.edu.pl/wyklady/pro/scb/index.html

Inne znane:
http://www.cplusplus.com/doc/tutorial/
https://xion.org.pl/productions/texts/c ... atutorial/


Kurs Talent-Technolgia-Tolerancja:
https://www.youtube.com/results?search_ ... tolerancja
i inne filmiki stąd: https://www.youtube.com/user/stowarzysz ... ent/videos


http://informatyka.wroc.pl/ i np. stare konkursy Spot
ODPOWIEDZ