Tři programátoři, jeden počítač, dvanáct úkolů aneb světové finále ICPC 2012

Už po třicáté šesté se konalo finále celosvětové soutěže ICPC (International Collegiate Programming Contest), kterou pořádá organizace ACM (Association for Computing Machinery). Během finále mezi sebou soutěží studenti vysokých škol z celého světa. Každý rok se finále koná v jiné zemi pod záštitou jiné univerzity. Tentokrát se vše odehrálo v nedaleké Varšavě a já jsem měl příležitost se celé události zúčastnit.

Dorazil jsem ve středu 16. května na společnou oficiální večeři a hned jsem měl možnost vidět úplně všechny lidi, kteří se kolem finále pohybovali: soutěžící, porotce, servisní týmy, televizní štáb, novináře, vyučující z mnoha škol a mnoho dalších lidí. Večeře se konala v hlavní budově Varšavské univerzity a bylo na ní přes tisíc lidí.

Hned na první pohled bylo zřejmých několik věcí: jde opravdu o velkou akci, jsou tu lidé z celého světa a organizace je perfektně zvládnutá. Autobusy z hotelů přijížděly a odjížděly, stovky lidí se přesouvaly kam měly, vše běželo na minutu přesně.

Dostat se sem není snadné

Přímo na večeři jsem mluvil s několika novináři z Ruska, Kanady, Indie a Rumunska a také lidmi z organizačního týmu. Dozvídám se první podrobnosti o letošním ročníku. Do regionálních kol se přihlásilo přes 25 000 studentů z 2219 univerzit v 85 zemích po celé Zemi. Jsou tu ti nejchytřejší mladí lidé na světě, vysvětlil mi Doug Heintzman, strategický ředitel společnosti IBM, která celou soutěž sponzoruje. Celkem je tu letos 112 tříčlenných tý­mů.

Dostat se sem skutečně není snadné, statisticky projde do finále jeden ze 75 přihlášených týmů. Ty musí projít regionálním kolem, kde se sejdou týmy z několika zemí. V našem případě ze zemí ze střední Evropy. Regionální kolo probíhá úplně stejně jako to finálové a vyjde z něj jen několik málo postupových míst. U nás jsou to obvykle první dva, letos to byly výjimečně tři týmy.

Během samotného klání mají studenti pět hodin čistého času. Po tu dobu mohou mluvit jen mezi sebou, nesmějí používat žádnou vlastní elektroniku a mají k dispozici jen jeden počítač, bloky, tužky a kalkulačky. Dostanou obálky s úkoly a musí jich vyřešit co nejvíce. Je to týmová práce, musí se odhalit podstata problému a pak společně vymyslet strategii řešení a dobře využít své zdroje, vysvětluje Doug Heintzman. Není třeba hledat nejlepší řešení, ale přijatelné řešení. Je to jako v reálném životě: hledáme dostatečně dobré řešení k nedokonale definovaným problémům.

Při téhle soutěži nejde jen o mechanické řešení problému, ale je třeba využít mnoho schopností, které pak student využije v praxi, vysvětluje profesor Jan Madey z Varšavské univerzity, která letošní ročník zaštiťuje. Mnoho z účastníků je pak v životě velmi úspěšných. Dělal jsem si vlastní statistiky: polovina je ve výzkumu nebo na univerzitách a čtvrtina je velmi úspěšná v komerční sféře.

Samotné studium na univerzitě ale k úspěchu nestačí, jak mi pánové vysvětlují. Někteří studenti jsou velmi mladí, často i v prvním ročníku. Je pozdě začít se takto komplikovaným úlohám věnovat až na univerzitě, ta jen rozvíjí vaše dříve nabyté schopnosti.

Jdeme do finále

Samotné finále začalo následující den v dopoledních hodinách. Autobus nás opět přivezl na půdu univerzity, tentokrát ale na fakultu managementu. Davem se postupně dostáváme na místo konání. V tělocvičně je narovnáno 112 stolků se třemi židlemi, počítačem a dalším skromným vybavením. Podél stěn jsou k vidění velké trsy balónků různých barev. Dozvídám se, že za každou úspěšně vyřešenou úlohu dostává tým balónek v příslušné barvě. Navíc existují speciální balónky pro týmy, které jednotlivé úlohy vyřeší jako první.

Kromě toho budou výsledky průběžně zobrazovány na velkých projekčních plátnech a zároveň s živým vysíláním budou streamovány do internetu. Každý tak může sledovat průběžné vysílání z pětihodinového maratonu. Každý tým má navíc před sebou webkameru. Ta slouží k nahrávání třeba pro případ podezření z podvodu, ale zároveň je jejich obraz také streamován. Zájemce tak má možnost se dívat třeba na soutěžící ze své země.

Nastupují soutěžící, každý tým má trička ve zvláštní barvě a se jménem svého týmu na zádech. Naše trojka je v tmavě modré. Dozvídáme se základní informace: nikdo u sebe nesmí mít žádnou pomůcku, mobil ani jinou elektroniku a samozřejmě se nesmí s nikým radit. Soutěž začne přesně v 10:00 a skončí o pět hodin později. Soutěžící u sebe mají svačiny, které mohou konzumovat kdykoliv, takže i o jejich zdraví je postaráno. Po několika dalších podrobnostech dav odpočítá posledních deset sekund do desáté a začíná se.

Pravidla jsou poměrně jednoduchá: vyhrává ten tým, který z 12 problémů vyřeší nejvyšší počet. Řešit je možné v libovolném pořadí, důležité je odevzdání řešení, přičemž se sčítá čas, který uplynul od začátku soutěže k odevzdání konkrétního úkolu. Pokud budou mít dva týmy stejný počet úspěšných řešení, rozhodne čas.

Úkoly se odevzdávají automaticky po síti hodnotícímu systému. Ten kód přijme, zkompiluje, spustí a naplní vstupními daty. Sleduje se, zda je kód zkompilovatelný, zda dává požadované výstupy a zda neběží příliš dlouho. S hrubou silou tu obvykle neuspějete, pokud běh překročí nastavený limit, neuspěli jste a systém vám úlohu vrátí k přepracování. Tohle můžete opakovat libovolněkrát, ale za každý pokus dostanete dvacet trestných minut. Ty se vám ale přičtou jen v případě, že se vám úkol podaří skutečně úspěšně odevzdat.

Jak vypadají problémy

Všechny kdy zadané problémy (včetně letošních) jsou k dispozici na webu. Jde obecně o komplikované algoritmické problémy. Jsou zadány formou „příběhu“, tedy jako slovní úloha. Vždy je uveden textový popis a jsou velmi přesně popsány vstupy a výstupy pro aplikaci soutěžících. Abyste měli konkrétnější představu, několik letošních zadání stručně shrnu.

Je rok 2112 a lidstvo se rozšířilo po sluneční soustavě. Nyní je třeba vytvořit komunikační síť napříč základnami na mnoha asteroidech. Protože je to drahé, je třeba vytvořit co nejmenší počet co nejkratších linek. Je ovšem třeba počítat s tím, že se asteroidy pohybují a mít možnost síť překonfigurovat, aby byla vždy co nejlevnější. Vstup tvoří úvodní polohy asteroidů, vektory jejich pohybu a informace o rychlostí. Toto byla pravděpodobně nejtěžší úloha, protože ji dokončilo jen několik týmů.

Jill potkala náhodou obchod s netradičně tvarovanými lahvemi. Napadlo ji, že by s jejich pomocí mohla měřit objem různých kapalin, ale to by vyžadovalo udělat na každé z nich rysky, aby bylo možné objem odečíst. Vstupem jsou informace popisující velikost a tvar lahve, výstupem je pak celkový objem dané lahve a maximálně osm stejně vzdálených bodů pro umístění rysek. Tato úloha byla zase pravděpodobně nejjednodušší, poprala se s ní většina týmů.

Bezpečnostní firma vynalezla nový trezor. Při pokusu o jeho odemčení je prostorem vyslán laserový paprsek. V síti a×b čtverců vychází laser z levé stěny levého horního čtverce. Uvnitř sítě je rozmístěno několik zrcadel se 45° sklonem. Ty odrážejí laserový paprsek v 90° úhlu. Pokud paprsek opustí prostor pravou stěnou čtverce vpravo dole, trezor se odemkne. V jiném případě je spuštěn poplach. V každém takovém mechanismu chybí jedno zrcadlo. Oprávněný uživatel ví, kam a jak orientované zrcadlo umístit, aby paprsek dopadl na správné místo. Vašim úkolem je zjistit, jestli je konkrétní konfigurace bezpečná. Tedy zda se ve výchozím stavu trezor neotevře a zda je to možné změnit přidáním jediného zrcadla. Vstupem jsou data o rozměrech sítě a umístění zrcadel, výstupem pak informace o tom, kam umístit chybějící zrcadlo, či chybový údaj o neřešitelné situaci nebo o nezabezpečené variantě.

První úkol za 15 minut

Soutěž byla v plném proudu a jako první vyřešil úkol tým Stanford University, trvalo jim to pouhých patnáct minut. Ve zkušebním kole, které proběhlo o den dříve, dokonce Stanford zvítězil. Podle Boženy Mannové z ČVUT, která během první části soutěže stála vedle mě, to ale vůbec nic neznamená. Ve finále může vyhrát někdo úplně jiný.

Celý průběh soutěže jsme mohli sledovat na přehledných bodových tabulích, které se promítaly na mnoha plátnech po celé budově i v místnosti s týmy. V tabulce bylo postupně k vidění: pořadí týmu, vlajka státu, znak univerzity, název univerzity, značky za splnění jednotlivých úkolů, počet bodů a započítaný čas. Značky za úkoly měly dvě barvy: červená znamenala neúspěšně odeslané řešení, zelená pak úspěch. Navíc číslo v obdélníčku oznamovalo, kolik pokusů bylo zatím uskutečněno a tedy jaká bude časová pokuta.

Kromě toho samozřejmě proudily už zmíněné balónky, podle kterých bylo možno také situaci sledovat. Logistika jejich distribuce je poměrně zajímavá. V zákulisí je řada tiskáren. Když některý tým splní úlohu, automaticky na tiskárně vyjede papír s informací o tom, komu a jaký balónek je třeba zanést. Navíc je přiložena i mapa stolků, aby měl nosič možnost tým rychle najít, řekl mi Doug Heintzman, a tiskárny jsem skutečně viděl na vlastní oči.

Abyste měli představu o atmosféře klání a množství účastníků, natočil jsem pro vás ukázkové video. Nejde o profesionální práci, proto ji berte spíše jako takový pohyblivý screenshot z akce.

Ohromné technické zázemí

Tím jsem trochu nakousl technické zázemí, které také stojí za zmínku. Pohybovaly se v něm stovky (skutečně) lidí, kteří měli na starosti nejrůznější záležitosti. Byl tu například velký televizní štáb, který vyráběl živé vysílání distribuované přes internet do světa. Součástí bylo několik mobilních a řada statických kamer, dva steadicamy, televizní studio s moderátory a obrovské studio, které zpracovávalo čtyřicet samostatných videovstupů. Vše se streamovalo do Švédska, kde probíhal postprocesing a odbavování. O video se staral tým studentů mediálních studií ze Švédska, Finska a Polska.

Vysílání bylo opravdu zajímavé a bylo ho možné sledovat v jednom z přednáškových sálů, kde stálo i studio s moderátory. Ti nejsou tak chytří, jak vypadají. Vzadu je tým analytiků, kteří jim radí do sluchátek, prozradil mi s úsměvem Doug Heintzman. Analytiky jsem skutečně viděl a někteří chodili i naživo mluvit před kameru, kde rozebírali aktuální situaci, popisovali ideální řešení jednotlivých úkolů a největší problémy, které by mohly při řešení nastat. Profesionalita celého vysílání byla neuvěřitelná.

Kromě místnosti s analytiky se mi podařilo na chvíli nahlédnout také do místnosti rozhodčích. Bylo jich tam deset, seděli u počítačů či u papírů a zkoumali řešení odesílaná jednotlivými týmy.

Ta samozřejmě předem zkoumal počítačový systém, který jsem měl také možnost vidět. Tvořila jej celá „baterie“ notebooků ThinkPad a v místnosti stál i rack se síťovou technikou. Technici byli při focení silně nervózní, protože po displejích probíhaly logy s citlivými informacemi o průběhu soutěže. Když jsem jim řekl, že fotky půjdou ven až za několik dní, takže před koncem nic nevyzradím, viditelně se uklidnili. Všichni to tu berou opravdu vážně.

Dramatická poslední hodinka

Aby byl průběh trochu dramatický, došlo v poslední hodině ke zmrazení výsledků na tabulích. Místo zelených a červených obdélníků se začaly objevovat značky modré barvy. Bylo tedy zřejmé, že konkrétní tým odeslal úlohu k ověření, ale nebylo známo, jak test dopadl. Tuto informaci měl jen konkrétní tým, nikdo jiný.

Stejně tak přestaly proudit balónky. Respektive některé ještě chodily, ale jen do výše čtyř na tým. Pokud jich měl tým tolik nebo více, už další nedostal. Diváci byli tedy skutečně odstřiženi od informací, aby byl závěr skutečné drama.

Musím říct, že ono drama skutečně přišlo. Po hlasitém odpočítání posledních deseti sekund soutěže nastala krátká pauza a po ní už následovalo dopočítání bodů za poslední hodinu. Počítač odspodu obarvoval modré obdélníky na červené či zelené a automaticky měnil pořadí týmů, které dostaly bod. Na prvních dvou místech skončily se stejným množstvím bodů univerzity z Varšavy a St. Petersburgu. Poláci měli ještě dva „rozjeté“ úkoly, Rusové jeden. Drama nastalo, když se druhým Polákům jeden bod obarvil na zeleno a dostali se na první místo, s jedním bodem visícím ve vzduchu. Rusům se také obarvil jejich úkol na zelenou a zase přeskočili nahoru. Tisícihlavý dav řval nadšením, bylo to neuvěřitelně emotivní.

Celé vyhlášení jsem pro vás opět natočil na video:

O vítězství měl rozhodnout poslední polský bod, ale Poláci nakonec neuspěli a objevila se červená. Zvítězil tedy tým St. Petersburgu.

Tato univerzita nezvítězila poprvé. Před několika lety si kvůli výhře dokonce změnila jméno. Vítěze tehdy při návratu přijel přivítat ruský prezident a byla to velká sláva. (Autorův povzdech: Všiml by si toho někdo v Česku? Asi ne.) Univerzita se tenkrát jmenovala „St. Petersburg State University of Mechanics and Optics“ a po tomto úspěchu si do názvu před mechaniku přidala ještě „IT“.

Drsná příprava

Soutěž ICPC většinou vyhrávají Číňané nebo Rusové. Velkou zásluhu na tom má především velmi rozsáhlá příprava jejich týmů. Doug Heintzman mi k tomu řekl: Čínský tým například za poslední rok natrénoval 3400 problémů, podobných těm, jaké tu předkládáme. Rusové mají zase vlastní tréninkové centrum, kam jezdí na několikatýdenní soustředění, na kterých se věnují jenom problematice řešení takových problémů. Není pak divu, že se jim daří pravidelně sbírat vítězství.

Za Českou republiku se letošního boje zúčastnili Michal Danilák, Filip Hlásek, Jakub Zíka a jejich „kouč“ Pavel Töpfer z Karlovy univerzity. Nakonec skončili na poměrně slušném 45. místě. Podařilo se mi je sehnat až večer po soutěži a mohl jsem se zeptat na řadu zajímavých věcí ohledně jejich přípravy, sehranosti, strategie a plánů na příští rok. Rozhovor s nimi vám přineseme v následujících dnech.

(Foto: Petr Krčmář, Root.cz)