Jak se připravit na konkurenční programování?

Takto jsem získal 3 ze 4 zlatých medailí ve výpočetní olympiádě.

Pozdější úpravy: Kvalifikoval jsem se do světových finále Google HashCode 2017, největší algoritmické soutěže pořádané společností Google.

Během prvního ročníku gymnázia jsem se začal učit C ++ od nuly. Nevěděl jsem nic o programování, algoritmech nebo datových strukturách. Sedm měsíců poté, co jsem napsal svůj první řádek kódu, Computing Olympiad klepala na dveře. A byl ten pravý čas zjistit, jestli můj styl učení stojí za 5 centů.

Po 2 dnech soutěže přišly výsledky: Získal jsem zlatou medaili.

Byl jsem šokován, protože jsem překonal konkurenty s pěti lety zkušeností. Věděl jsem, že jsem tvrdě pracoval, ale tento úspěch předčil moje očekávání. Programová soutěž mě perfektně sladila a já jsem šel all-in v této oblasti.

Vím, co mi přineslo úspěch, a chci se s vámi o to podělit.

Jaký jazyk byste si měli vybrat?

  1. C ++ - vysoce doporučeno! Je to velmi rychlé. Implementace různých algoritmů zabere kvůli STL málo času. C ++ je přijímán ve všech soutěžích. Používám ji od svého prvního řádku kódu.
  2. C - Jděte a učte se C ++ kvůli STL. Pokud víte o C, jste připraveni kódovat také v C ++.
  3. JAVA - Je to pomalé. Má však třídu Big Integer, i když existuje jen velmi málo problémů, které vyžadují její použití. Pokud je časový limit těsný, bude překročen časový limit. Java není akceptována ve všech soutěžích.

Kde můžete cvičit?

Doporučuji Sphere Online Judge (SPOJ). Je efektivní z hlediska kvality a množství. Redakce a řešení jsou k dispozici online, pokud narazíte na řešení problémů. Podpůrné weby SPOJ Toolkit a klasifikátor problémů pro SPOJ.pl.

Nejprve musíte zvládnout základy.

Poté, co si zvyknete na syntaxi jazyka, je čas vyřešit některé problémy. Začněte s jednoduchými, které vyžadují implementační dovednosti. V této fázi je vaším cílem definovat styl kódování. Možná byste chtěli psát se spoustou mezer, možná ne. Možná umístíte rovnátka do stejného řádku s tvrzením „pokud“, možná ne.

Musíte najít svůj styl kódování, protože je to váš.

Při vývoji stylu kódování mějte na paměti tyto dva principy.

  • Snadná implementace. Měli byste se cítit pohodlně při implementaci řešení, které jste přišli. Proč? Protože během soutěže je poslední věcí, kterou se chcete stát, ztracení ve vašem kódu. Vždy je lepší myslet na implementaci ještě 5 minut, než na to strávit dalších 10 minut.
  • Snadno čitelné. To znamená „Snadné ladění“. Přiznejme si to, oba víme, že se chyby objevují stále. Znáte ten pocit, když vám zbývá 10 minut a nenajdete tu zasranou chybu? Ano, ano. Chcete-li vyřešit, že musíte napsat čitelný kód. Takže když začnete ladit, bude se kód cítit přirozeně a jednoduše sledovat.

Tady je můj kódovací styl.

Jak posílit implementační dovednosti?

Praxe, praxe a další praxe. Doporučuji vám pracovat na prvních 250 nejřešenějších problémech na SPOJ. Vyřešte je v přesném pořadí. A přemýšlejte o řešení alespoň jednu hodinu.

Neříkej: „Tento problém je pro mě příliš těžký, zkusím ten další.“ To je poražená mentalita.

Vezměte kousek papíru a tužku a zkuste myslet. Tímto způsobem pravděpodobně najdete řešení, ale určitě budete rozvíjet algoritmické myšlení. Pokud nenaleznete řešení do jedné hodiny, můžete se podívat na fórum nebo v editoriálech a podívat se na řešení.

Výsledky tohoto přístupu? Rychlá implementace. A učení klasických problémů a algoritmů.

Za druhé, musíte ovládat algoritmy a datové struktury.

Postupujte podle hierarchického přístupu. Začali jste běžet, aniž byste věděli, jak chodit? Ne. Můžete postavit mrakodrap bez pevného základu? Opět ne.

To znamená, že ve své studijní cestě nemůžete vypálit kroky. Nebo pokud tak učiníte, zůstanete s mezerami ve znalostech, které se postupem času prohloubí.

Začněte se základními strukturami algoritmů a dat.

Je těžké začít. Pravděpodobně proto, že nevíte, co se nejprve naučit. Proto jsem vytvořil video kurz Algoritmy a datové struktury. Udělal jsem tento kurz tak, jak jsem si přál, abych byl učen. Reakce byla neuvěřitelná, během prvního měsíce se k ní připojilo 3000+ studentů ze 100+ zemí.

Pokud pracujete s jednoduchými problémy, nikdy se nezlepšíte.

Nejúčinnějším způsobem, jak zjistit, co nevíte, je to se s ním skutečně setkat. To se mi stalo. Naučil jsem se mnoho nových technik, o kterých jsem nikdy předtím neslyšel, výběrem těžkého problému.

Ze všech 3 problémů, které řešíte, byste se měli naučit něco nového. Pokud ne, vyberte je opatrněji. Vyberte si těžší problémy!

Po dokončení těchto 250 problémů z SPOJENÍ získáte přehled hlavních témat konkurenčního programování. Hlubokým porozuměním logiky základních algoritmů se zdá, že algoritmy na vysoké úrovni budou snadno pochopitelné. Takže můžete rychle využít své znalosti.

Nyní se můžete hlouběji věnovat každému hlavnímu tématu.

Zde je ohromný zdroj s 10 nejvýznamnějšími algoritmy a strukturami dat v každém tématu. Po těchto 250 problémech z SPOJU budete vědět mnoho z tohoto seznamu. Ale stále existuje mnoho, o kterých jste nikdy neslyšeli. Začněte je tedy učit vzestupně.

Pokud své znalosti nezlepšíte, až se naučíte něco nového, zapomenete na to.

Doporučuji, abyste se naučili nový algoritmus pro procvičování 2–3 problémů s jeho používáním. Prohledejte značku algoritmu na SPOJ a najdete problémy, které to vyžadují. Pracujte dříve, než cokoli jiného.

Pochopte dynamické programování, protože vás zvítězí.

Z mé zkušenosti je v každé soutěži alespoň jeden dynamický programovací problém. Mnoho lidí trpí bolestmi hlavy, když slyší DP, protože tomu nerozumí.

A je to dobrá věc. Protože pokud skutečně rozumíte DP, vyhrajete.

Líbí se mi DP, to je moje oblíbené téma. A tady je tajemství RP: přemýšlejte globálně optimálně, nejen lokálně. Musíte problém rozdělit na jednodušší dílčí úlohy, vyřešit každý z nich jen jednou a vytvořit řešení kombinující tyto řešené dílčí úlohy. Opak DP je chamtivý algoritmus, protože ten vybírá v každém kroku lokálně optimální volbu. A lokálně optimální výběr může vést ke špatnému globálnímu řešení.

Když se učíte nové koncepty, podívejte se na návody TopCoder. Jsou velmi podrobné a snadno sledovatelné. Odtud jsem opravdu pochopil binární indexované stromy.

Tvrdě pracovat.

Slyšeli jste někdy o atletech, kteří vyhrávají olympijské hry bez praxe? Nemám.

Každý rok začala příprava na výpočetní olympiádu v září a skončila v dubnu.

Každý den v těchto 8 měsících jsem trénoval 5 hodin.

A ano, strávil jsem těchto 5 hodin řešením algoritmických problémů. Vzpomínám si na dny, kdy jsem cvičil dokonce 8 nebo 10 hodin. Proč? Protože jsem byl nadšený. Každý den po návratu ze školy jsem šel rovnou do své ložnice a začal řešit nový problém. Nebo se učí nový algoritmus potřebný pro tento problém.

Pokud chcete vyhrát, musíte udělat totéž. Vezměte si problém a držte se ho. Přemýšlejte o tom během své každodenní rutiny. Jako na vaší cestě do supermarketu nebo za jízdy.

Víte, že během spánku váš mozek defragmentuje informace shromážděné v ten den? Je to jako dát knihy v abecedním pořadí na polici. V podstatě váš mozek přemýšlí o různých problémech, s nimiž jste se setkali.

Zde je návod, jak toho využít. Než půjdete spát, přečtěte si těžký problém a mějte na paměti, co to vyžaduje. V tuto chvíli nemusíte hledat řešení. Pak jdete spát a váš mozkový mechanismus začne tento problém zpracovávat. Až se probudíte, budete překvapeni: našli jste řešení během spánku.

Vyzkoušejte to sami. Je to jako magie.

Začal jsem Vlog

Tento krátký odstavec nesouvisí s konkurenčním programováním. Chtěl jsem ti jen dát vědět, že pokud máš 20 let a je zajímavé, jak vidím svět, dělám vlog na Youtube. Mluvím o světě, životě a informatice.

Pracujte chytře.

To je tajemství úspěchu. Potřebujete cíle.

Jsme lidé a rádi otálíme. To znamená odložit věci, které musíte udělat hned teď. Vždy je snazší sledovat Netflix než pracovat s problémy DP. To víte a musíte to napravit.

Jak můžete porazit otálení?

Převzetím cílů. Vždy najdete zajímavé problémy, odkud se můžete dozvědět něco nového (zkontrolujte zdroje, které jsem vám dal výše). Tyto problémy však musí být vyřešeny, nejen přečteny.

Tak jsem překonal otálení. Vytvořil jsem papírový kalendář a naplnil jsem jej problémy, které jsem chtěl každý den vyřešit. A vždy jsem dva dny dopředu plnil problémy, takže jsem věděl, jak si v následujících dnech řídit svůj čas.

Tímto způsobem jsem byl vždy motivován dokončit problémy a najít nové, které naplní kalendář v následujících dnech. Když je řešíte, je to odměňující pocit. Vím, že se vám to taky líbí.

Vytvořte si vlastní papírový kalendář. Nevytvářejte ve svém telefonu další kontrolní seznam, o který vám bude zítra jedno.

Jak efektivně ladit?

Chcete se stát profesionálem? Pokud ano, musíte „ladit ve své mysli“.

Je to zdaleka nejúčinnější debugovací technika, kterou znám, protože to vůbec nevyžaduje debugger. Váš mozek zkoumá více cest kódu současně a dává vám mnohem širší perspektivu kódu ve srovnání s klasickým debuggerem.

Je to podobné schopnosti velmistrů hrát šachy a myslet 3 pohyby předem.

Tuto techniku ​​používám výhradně jako svou počáteční linii obrany, následovanou použitím skutečného debuggeru v poslední instanci.

Abyste se naučili „ladit ve své mysli“, musíte cvičit. Když odešlete problém a obdržíte „Nesprávná odpověď“, nepřecházejte přímo na tlačítko debuggeru. Místo toho začněte číst kód a přemýšlejte: „Co se stane na tomto řádku?“, „Jak to ovlivní“, pokud „příkaz ovlivní program?“, „Když opustí smyčku, jaká je hodnota iterátoru?“.

Tímto způsobem si myslíte sami. Postupem času začnete ladit v reálném čase při psaní kódu.

Považujete tento příspěvek za užitečný? Laskavě klepněte na tlačítko below níže! :)

O autorovi

Andrei Margeloiu je vášnivý programátor se zájmem o podnikání, startupy a přírodu. Můžete se s ním spojit na LinkedIn.