Differences

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

--- courses:a4b36acm1:trenink [2018/10/03 03:51]
+++ courses:a4b36acm1:trenink [2021/09/17 16:51] (current)
@@ Line 1: / Line 1: @@
+----
+====== Návodník na přípravu na programovací soutěže ======
+==== Jak na řešení ====
+Když se stránka nechce načíst, nebo server divně komunikuje, vyzkoušej jiný prohlížeč.
+Čti pozorně zadání. Když ti program později server odmítne, ujisti se vždy nejprve, že zadání rozumíš zcela přesně.
+Z uvedené maximální velikosti dat odhadni, jakou časovou a paměťovou složitost řešení zadavatel předpokládá, a podle toho vymýšlej a posuzuj svůj aloritmus řešení. Server schválně hlídá, aby neprošla příliš "liberální" řešení.
+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.
+Při ladění používej [[https://www.udebug.com/|uDebug]], ověříš si snadno svoje řešení.
+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".
+Proč je nutno číst zadání:
+Emily’s father has three daughters. The first two are named April and May. What is the third daughter’s name?
+Did you answer June? That’s the intuitive answer that many people give – but the correct answer is, of course, Emily.
+==== 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.
+Skoukni webové zdroje, např. [[https://www.geeksforgeeks.org/competitive-programming-a-complete-guide/|Competitive Programming – A Complete Guide]],
+Č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í.
+==== 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 zkušenosti a znalosti ====
+. Aktivně programuj, řeš nové úlohy.
+. 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]] \\
+. 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]].
+. Stručný přehled, v čem se tak mazák vyzná :-), [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/algoritmy|máme zde]].