Návodník na přípravu na programovací soutěže

Zdroje úloh

UVA UVA Online Judge

SPOJ Sphere Online Judge

ACM-ICPC Live Archive Všechny mezinárodní soutěže ACM-ICPC

CTU Open Každoroční ACM soutěž na FEL

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: UVA toolkit,
.. pro SPOJ je zde: 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:
.. zde, zde a zde.

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 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 Submission specification a 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: google, 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.
.. KSP na MFF UK Praha
.. M&M na MFF UK Praha
.. BRKOS na MU Brno
.. KSI na na MU Brno
.. Programovací olympiáda

3. Popros o pořádnou knihu k narozeninám, za vysvědčení nebo pod stromeček. Seznam máme zde.

4. Stručný přehled, v čem se tak mazák vyzná :-), máme zde.

 
Groups:
courses/a4b36acm/trenink.txt · Last modified: 2016/12/15 19:41 by berezovs