Differences

This shows you the differences between two versions of the page.

Link to this comparison view

courses:a4b36acm1:trenink [2018/10/03 03:51] (current)
Line 1: Line 1:
 +----
 +
 +====== Návodník na přípravu na programovací soutěže ======
 +
 +==== Zdroje úloh ====
 +
 +[[http://​uva.onlinejudge.org/​| UVA]]  UVA Online Judge 
 +
 +[[http://​www.spoj.com/​| SPOJ]] ​ Sphere Online Judge
 +
 +[[https://​icpcarchive.ecs.baylor.edu/​|ACM-ICPC Live Archive]] Všechny mezinárodní soutěže ACM-ICPC ​
 +
 +[[http://​contest.felk.cvut.cz/​|CTU Open]] Každoroční ACM soutěž na FEL 
 +
 +[[https://​en.wikipedia.org/​wiki/​Competitive_programming#​Online_contest_and_training_resources |a další]] Rozcestník
 +
 +Úlohy jsou v zásadě dvojí: Úlohy na aplikaci čí přizpůsobení známého algoritmu a úlohy originální,​ na něž nejsou nebo se těžko hledají "​standardní páky"​. Neplatí, že by jedny musely být těžší než druhé nebo naopak.
 +
 +Při výběru "​standardnějších"​ úloh pomúže tématický seznam. Není zdaleka úplný, ale postačí. \\
 +..  Pro UVA je zde: [[http://​uvatoolkit.com/​problemssolve.php|UVA toolkit]], \\
 +..  pro SPOJ je zde: [[http://​problemclassifier.appspot.com/​|problem classifier]],​ \\
 +ACM-ICPC Live Archive ho nemá, protože registruje jen kompletní soutěže. Navíc, v seznamech úloh na UVA a ACM-ICPC Live Archive jsou "​teploměry"​ ukazující relativní obtížnost úlohy podle počtu úspěšných řešení. \\ 
 +UVA má dále několik sérií rozdělěných podle témat a obtížnosti:​ \\
 +..  [[https://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=442|zde]],​ [[https://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=93|zde]] a [[https://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=123|zde]].  ​
 +
 +[[https://​www.codechef.com/​|Codechef]] poskytuje kódy úspěšných řešitelů. ​  
 +
 +==== Jak na řešení ====
 +
 +1. Čti pozorně zadání. Když ti program později nebude fungovat, ujisti se vždy nejprve, že zadání rozumíš zcela přesně.  ​
 +
 +2. Z uvedené maximální velikosti dat odhadni, jakou asymptotickou/​časovou/​paměťovou složitost řešení zadavatel předpokládá,​ a podle toho vymýšlej a posuzuj svůj aloritmus řešení. ​
 +
 +3. Dávej pozor na "​okrajové",​ "​degenerované"​ případy velmi malých dat (velikosti 0, 1 apod.), někdy se chovají jinak než "​regulérní"​ a musí se zvlášť obsloužit.
 +
 +4. Při ladění používej [[https://​www.udebug.com/​|uDebug]],​ ověříš si snadno svoje řešení. ​
 +
 +5. Svoje potíže v řešení diskutuj s co největším počtem lidí. Rozhovor tě nutí uspořádat si myšlenky ​ a srozumitelně ​ je formulovat, leckdy si uvědomíš svou chybu nebo potřebné souvislosti,​ ještě než tvůj protějšek odpoví. Proto se doporučuje mluvit i na benevolentní členy rodiny a přátele, kteří nejsou "z oboru"​. ​    
 +
 +
 +==== Jak na kódování ====
 +
 +Přečti si na UVA [[https://​uva.onlinejudge.org/​index.php?​option=com_content&​task=view&​id=15&​Itemid=30|Submission specification]] a [[https://​uva.onlinejudge.org/​index.php?​option=com_content&​task=view&​id=16&​Itemid=31|Verdict information]],​ řeknou ti, co a jak odevzdat a co si systém myslí o tvém kódu. Podobná pravidla platí také na dalších serverech.
 +
 +Nauč se efektivně ladit: Používej trasovací výpisy, debugger je většinou na nic. Najdi první výskyt problému a ten vyřeš, pak další výskyt a další, nechtěj uhodnout najednou "proč mi to nefunguje"​. Laď na různých datech, vymysli si svoje malá ladící data. 
 +
 +Ptej se online: [[https://​www.google.com/​advanced_search?​hl=en|google]],​ [[http://​stackoverflow.com/​|stackoverflow]],​ většinou ví, jak na to.
 +
 +Čti dokumentaci jazyka! ​ Např. knihovní metody typu x.contains(y),​ z.remove(w) bývají záludné svou pomalostí.
 +
 +Omez a nespoléhej na objektový přístup. Prodlužuje kód mírně a čas běhu programu někdy drasticky.
 +
 +I/O - Nepiš vlastní superchytré procedury načítání/​tisku. Najdi na síti základní ukázky, přizpůsob si je, pokud chceš, a používej pořád. S 2-3 variantami většinou pohodlně vystačíš. V Javě nepoužívej Scanner ani string.split(),​ jsou příliš pomalé.
 +
 +Problémy s I/O nelaď ve svém GUI, neumí správně emulovat systémové I/O prostředí. Používej příkazový řádek pro překlad a spouštění programu, zejména pro textový I/O a potíže s "​neviditelnými"​ znaky (EOL, EOF, TAB apod.).
 +
 +SPOJ - čti komentáře řešitelů pod zadáním úlohy, mohou napovědět.
 +
 +Specificky na každém Online Judge:
 +
 +Runtime Error s časovou známkou 0.000 indikuje, že asi zlobí načítání dat. S časem větším než 0.000 je načítání asi dobře a zlobí něco dál v kódu.
 +
 +Při Runtime Error postupně zakomentuj více a více svého kódu a stále odevzdávej,​ dokud nedostaneš Wrong Answer. Tak odhalíš, která část kódu program shodí.
 +
 +==== Jak na zkušenosti a znalosti ====
 +
 +1. Aktivně programuj, řeš nové úlohy.
 +
 +2. Když jsi středoškolák,​ zapiš se do některého ze specializovaných seminářů,​ zúčastni se olympiády.\\
 +..    [[http://​ksp.mff.cuni.cz/​ | KSP na MFF UK Praha]]\\ ​
 +..    [[https://​mam.mff.cuni.cz/​|M&​M na MFF UK Praha]] \\
 +..    [[http://​brkos.math.muni.cz/​|BRKOS na MU Brno]] \\ 
 +..    [[https://​ksi.fi.muni.cz/​|KSI na na MU Brno]]\\
 +..    [[http://​mo.mff.cuni.cz/​p/​|Programovací olympiáda]] \\ 
 +
 +3. Popros o pořádnou knihu k narozeninám,​ za vysvědčení nebo pod stromeček. Seznam [[https://​cw.fel.cvut.cz/​wiki/​courses/​a4b36acm/​links#​velmi_doporucujeme_ke_cteni|máme zde]]. ​
 +   
 +4. Stručný přehled, v čem se tak mazák vyzná :-), [[https://​cw.fel.cvut.cz/​wiki/​courses/​a4b36acm/​algoritmy|máme zde]]. ​
 +
 +
  
courses/a4b36acm1/trenink.txt · Last modified: 2018/10/03 03:51 (external edit)