CourseWare Wiki
Switch Term
Summer 2023 / 2024
Winter 2023 / 2024
Summer 2021 / 2022
Winter 2021 / 2022
Summer 2020 / 2021
Winter 2020 / 2021
Summer 2019 / 2020
Winter 2019 / 2020
Summer 2018 / 2019
Winter 2018 / 2019
Summer 2017 / 2018
Search
Log In
b232
courses
a4b36acm1
trenink
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Go
Go
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 ====
+
+
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: 2021/09/17 16:51 by
berezovs