Pokud zde nenajdete něco o MO-P, co vás zajímá, napište nám na p@mo.mff.cuni.cz.
Na internetu existuje tolik zdrojů, ze kterých se můžete naučit programovat, až je těžké mezi nimi vybrat. Doporučujeme Liaheň, kterou vytvořili organizátoři slovenského Korespondenčního semináře z programování. Liaheň má interaktivní lekce programování v jazyce C++, které jsou zaměřené přímo na soutěžní programování (tj. na soutěže podobné MO-P). Navíc si na ní procvičíte slovenštinu :) Ať už se rozhodnete Liaheň vyzkoušet nebo ne, doporučujeme vám používat jazyk C++. C++ je mezi soutěžními programátory zdaleka nejčastější programovací jazyk, protože je rychlé a zároveň má užitečnou tzv. standardní knihovnu (stdlib), která umožňuje snadno dělat věci, které jsou v C a Pascalu těžší.
V praktických úlohách musíte napsat program (třeba v C++), který
dostane na standardním vstupu nějaká data a z nich spočítá výsledek,
který vypíše na standardní výstup. (Třeba má v seznamu najít dvě čísla,
která se sečtou na dané číslo – viz ukázková
úloha). Když napíšete program, který úlohu řeší, pošlete ho do
vyhodnocovacího systému (judge
), který váš program zkusí spustit
na sadě připravených testů. Ta je zveřejněna až po skončení soutěže, tj.
při řešení úlohy tuto sadu testů neznáte a nemůžete napsat program
specificky řešící jen tuto sadu testů. V každém testu dostane váš
program nějaký vstup a vyhodnocovač zkontroluje, zda výstup programu
odpovídá očekávanému výsledku.
Správnost výsledku ale sama o sobě nestačí. Judge nastavuje omezení na čas a na paměť, kterou má program k dispozici. Pokud je časový limit jedna sekunda a váš program za tuto dobu nestihne doběhnout, nebude uznán. Stejně tak pokud použije moc paměti; na toto omezení budete ale narážet méně často.
Slovo program
zde používáme ve smyslu konzolový
program
. Pokud používáte Windows nebo Mac, je možné, že jste se s
konzolí (aneb příkazovou řádkou) dosud nesetkali. Konzolové programy
nemají žádné vizuální rozhraní, žádné okénko
, kde by byly vidět.
S uživatelem interagují pomocí jednoduššího textového rozhraní přes tzv.
konzoli, což bývá černé okénko s bílým textem, do kterého hackeři ve
filmech vždy něco zuřivě píšou.
Konzoli podobnou linuxové si můžete vyzkoušet třeba tady.
Po načtení zkuste napsat tr a o a zmáčknout Enter. Tím
spustíte program tr (zkratka pro translate
), který
bude přepisovat všechna a na o. Program čeká
na vstup; když napíšete alej a zmáčknete Enter, program na
další řádku napíše olej. Můžete mu zkusit napsat další
slova. Pak zmáčkněte Ctrl+D, což znamená konec
vstupu
, a program skončí. tr četl váš vstup ze
standardního vstupu a vypisoval na standardní výstup. Programy tohoto
druhu (ale samozřejmě zajímavější) budete psát v MO-P.
Pokud nechcete, nemusíte se s konzolí učit. Různá vývojová prostředí umí program spustit samy; například Code::Blocks, se kterým vás naučí Liaheň. (Nezaručujeme, že Code::Blocks bude dostupné v ústředním kole, protože jsme s ním v minulosti měli problémy. Pokud jste dosud spouštěli kód pouze přes Code::Blocks, nebojte, před soutěží vám ukážeme, jak kompilovat a spouštět kód přes konzoli.)
Podívejte se i na konkrétní ukázku toho, jak číst standardní vstup a psát na standardní výstup.
Nejsnáze se to vysvětluje ve srovnání s praktickými úlohami. Představte si, že napíšete program, který řeší praktickou úlohu, a chcete ho někomu vysvětlit tak, aby daná osoba dokázal/a program také implementovat. Píšeme tedy text ne pro počítače, ale pro lidi. Lidé jsou chytřejší než počítače, takže můžeme vynechat nějaké technické detaily (jak přečíst vstup, jak pojmenovat nějaké proměnné a tak dále). Popis by ale pořád měl být dostatečně přesný, aby si čtenář nemusel domýšlet důležité části algoritmu.
Důležité je také zdůvodnit správnost použitého algoritmu. Stává se totiž někdy, že použitý algoritmus je jednoduchý a těžká část je ukázat, proč opravdu funguje – např. u hladových algoritmů na minimální kostru (pokud nevíte, o co jde, nelamte si s tím hlavu). Je potřeba napsat i důkaz, tj. zdůvodnění, které přesvědčí opravovatele, že je váš algoritmus správný a že i víte, proč tomu tak je. Dalo by se říct, že v praktických úlohách funguje váš program jako důkaz toho, že je algoritmus správný, i když narozdíl od teoretických úloh neověřujeme, zda opravdu víte proč.
U teoretických úloh nám záleží na tzv. asymptotické složitosti, což je způsob, jak vyjádřit rychlost algoritmu v závislosti na velikosti vstupních dat. Můžete se o ní dočíst v Průvodci labyrintem algoritmů nebo v kuchařce KSP.
Máme připravenou i ukázkovou úlohu, na které ilustrujeme teoretická řešení. Pro další příklady si můžete v Archivu přečíst vzorová řešení úloh uplynulých ročníků MO-P. Tato vzorová řešení bývají napsána podrobněji, než by bylo třeba v případě soutěžního řešení; vaše řešení mohou být o něco stručnější.
I pokud umíte programovat, soutěžní programování je poměrně odlišné od jiných věcí, které bychom nazvali programování, jako třeba vytváření webových nebo mobilních aplikací. K úspěchu nestačí jen umět C++ (či jiný jazyk), důležitější je umět vymýšlet chytré algoritmy. Tento druh programování má blíž k matematice než k vytváření androidových appek.
O algoritmech je také k dispozici velké množství literatury. My doporučíme výborného Průvodce labyrintem algoritmů od Martina Mareše a Tomáše Vally, který je zdarma k dispozici jako PDF. Najdete v něm vše od základů až po velmi pokročilé algoritmy. Rozhodně není potřeba přečíst celou knihu, abyste mohli s MO-P začít. Může ale sloužit jako dobrý zdroj, když se rozhodnete si rozšířit své vědomosti.
Další úvody do jednotlivých témat můžete najít v kuchařkách KSP.
Pokud chcete vědět, jaké algoritmy a techniky vám můžou při soutěžním
programování pomoci, podívejte se na IOI Syllabus, který
určuje, co se může hodit při řešení úloh z IOI (Mezinárodní informatická
olympiády). Opět platí, že není potřeba vědět všechno, jedná se spíš o
horní odhad
.
V praktických úlohách má řešení dvě části: musíte vymyslet správný algoritmus, který je následně potřeba implementovat. V teoretických úlohách stačí algoritmus vymyslet a zapsat na papír. Zaměřme se tedy na praktické úlohy; rady pro vymýšlení se dají aplikovat i na ty teoretické.
Nepřekvapí vás, že nejlepší způsob, jak se zlepšit, je trénováním.
Podívejte se na sekci Další soutěže a
zkuste se nějaké zúčastnit. Pokud chcete řešit ve větším klidu, zkuste
některý z tam zmíněných seminářů. Pro efektivní trénink je zaprvé dobré
se účastnit soutěží, které mají podobný druh úloh jako MO-P, a zadruhé
řešit úlohy, které jsou na hranici vašich možností (vyřešením stovky
lehkých úloh se nezlepšíte). Pokud se třeba snažíte dostat do ústředního
kola, podívejte se v Archivu na úlohy z
minulých ústředních kol. Pokud cílíte i na mezinárodní soutěže, je dobré
řešit třeba předešlé IOI, případně regionální soutěže, kterých je hodně
a mívají podobně těžké úlohy. Na spoustu těchto soutěží se dá najít
vyhodnocovač (googlete <jméno soutěže> online judge
), takže
si můžete doma udělat virtuální soutěž a pak porovnat svoje výsledky se
soutěžícími skutečné soutěže, abyste zjistili, jak na tom jste.
Setkávejte se s lidmi, které také baví soutěžní programování. Je větší zábava soutěžit s kamarády, když si po soutěži můžete společně zanadávat na to, jak hrozné úlohy organizátoři připravili tentokrát, nebo se snažit společně vymyslet řešení poslední úlohy, kterou jste zatím nerozlouskli. Dobrá příležitost setkat se s dalšími nadšenci je samozřejmě ústřední kolo MO-P. Kromě něj doporučujeme soustředění různých korespondenčních seminářů, jako je KSP, KSI, PraSe a další (viz Další soutěže).
Na úspěch v časově omezených soutěžích je kromě algoritmických dovedností potřeba i umět se vyrovnat se stresem a dokázat si rozvrhnout čas, aby vás najednou nepřekvapilo, že zbývá čtvrt hodiny do konce soutěže. To se nedá naučit jinak než účastí v různých soutěžích. Na stres může pomoct i příliš se nezaměřovat na výsledky v porovnání s ostatními; jejich výkon koneckonců neovlivníte. My doufáme, že místo stresu spojeného s poměřováním se s ostatními vás čeká spíše radost z povedeného souboje s úlohami.
Pokud vám po nějaké soutěži zbydou úlohy, které jste nevyřešili (a pokud se to nestává, najděte si větší výzvu!), pokuste se je vyřešit po soutěži. Nejste-li tak trpěliví (což je pochopitelné), najděte si vzorové řešení a nastudujte ho. Pokud je složité, o to víc získáte tím, že se ho skutečně pokusíte pochopit. Tomuto čtení by ale vždy měl předcházet vážný pokus o řešení; samotným čtením řešení se tolik nezlepšíte.
Vymýšlení se dá trénovat i na praktických úlohách, ale teoretické mohou být rozmanitější a umožňují pořadatelům zadávat i úlohy, které jsou zajímavé, ale nepříjemně se implementují, což je třeba případ geometrických úloh. Mnoho teoretických úloh včetně řešení najdete v našem Archivu a také na stránkách KSP. Oblíbená je i kniha Looking for a challenge?, což je sbírka nejzajímavějších úloh Varšavské univerzity, která má silnou tradici soutěžního programování. Z domácí literatury můžeme doporučit Algoritmy a programovací techniky od Pavla Töpfera.
Pomáhá číst si kód zkušenějších soutěžících. Zkuste se třeba
zúčastnit nějaké online soutěže, jako je Codeforces, a po soutěži se podívat,
jak úlohy řešili lidé na předních pozicích. Obecně si můžete všimnout,
že čím lepší je soutěžící, tím kratší bývá kód. Ti nejlepší totiž znají
spoustu triků, kterými si mohou ušetřit práci. To platí jak na úrovni
kódu (chci-li vyzkoušet všechny podmnožiny, můžu každé přiřadit
bitmasku, tj. číslo napsané v binární soustavě
, na spočítání
největšího společného dělitele dvou čísel můžu v C++ použít již
naimplementovanou funkci
),
tak na vyšší úrovni (std::gcd()tohle dynamické programování se snáze
implementuje pomocí rekurze s memoizací
, tenhle případ nemusím
řešit, protože to je podpřípad jiného, který jsem už vyřešil
).
Pokud jste zvyklí věci dělat nějakým způsobem, tak vás třeba nenapadne, že to jde snáz. Čtení cizího kódu vám může dát spoustu nových nápadů. Ze začátku je to náročné, protože každý píše kód jiným stylem, a obzvlášť v C++ je hodně možností, jak zapsat stejný postup, ale čtení cizího kódu se pořád vyplácí.