24. mezinárodní olympiáda v informatice IOI 2012

Pavel Töpfer, MFF UK Praha

Dvacátý čtvrtý ročník Mezinárodní olympiády v informatice IOI 2012 se konal ve dnech 23. – 30. 9. 2012 v severní Itálii ve městě Sirmione. Ubytování účastníků i prostory pro jednání byly zajištěny v rekreačním středisku Garda Village, vlastní soutěž probíhala v nedalekém městě Montichiari.

Olympiády se zúčastnilo 81 delegací z celého světa. Z každé země se IOI mohou zúčastnit čtyři soutěžící a dva vedoucí, celkově letos soutěžilo 317 studentů. České družstvo bylo sestaveno na základě výsledků ústředního kola 61. ročníku Matematické olympiády – kategorie P a bylo tvořeno těmito studenty:

• Jiří Eichler, absolvent Slovanského gymnázia v Olomouci
• Ondřej Hübsch, student gymnázia Arabská v Praze 6
• Štěpán Šimsa, student gymnázia Josefa Jungmanna v Litoměřicích
• Martin Zikmund, absolvent gymnázia v Turnově

Vedoucími české delegace na IOI 2012 byli jmenováni Mgr. Zdeněk Dvořák, Ph.D. a doc. RNDr. Pavel Töpfer, CSc., oba z Matematicko-fyzikální fakulty Univerzity Karlovy v Praze.

Již tradičně se naši účastníci IOI připravovali na olympiádu společně s reprezentanty vybranými pro CEOI (Středoevropská olympiáda v informatice) na týdenním soustředěním CPSPC (Czech-Polish-Slovak Preparation Camp). Přípravné soustředění bylo letos pořádáno u nás v Bílovci a zúčastnili se ho vybraní studenti ze všech tří zemí.

Během prvního dne pobytu v Itálii proběhlo slavnostní zahájení soutěže a poté měli soutěžící příležitost seznámit se podrobně s počítači a se softwarovým prostředím, ve kterém budou pracovat při soutěži. Vlastní soutěž se konala jako obvykle ve dvou dnech, oddělených jedním odpočinkovým dnem. Tento volný den strávili studenti v blízkém zábavním parku Gardaland, který patří k největším v Evropě, dospělí měli možnost namísto toho navštívit Milán a prohlédnout si jeho historické památky. Po druhém soutěžním dnu následoval druhý odpočinkový den, během kterého byl pro soutěžící uspořádán celodenní výlet do Benátek. Jeho součástí byla návštěva nejvýznamnějších památek i plavba lodí po kanálech. V závěrečném dni pobytu si účastníci prohlédli město Sirmione a pak následovalo slavnostní vyhlášení výsledků.

Soutěž IOI probíhá podobným způsobem, jako praktická část ústředního kola naší Matematické olympiády – kategorie P. Každý soutěžící má přidělen osobní počítač, na kterém řeší zadané úlohy. V každém dni má na práci vymezen čas 5 hodin. Úlohy je třeba dovést až do tvaru odladěného programu, hotové programy se odevzdávají k vyhodnocení prostřednictvím soutěžního prostředí. Odevzdané programy se testují pomocí předem připravené sady testovacích dat. Prováděné testy jsou navíc omezeny časovými a paměťovými limity, aby se kromě otestování správnosti odlišila časová i paměťová efektivita algoritmu použitého jednotlivými účastníky soutěže. Při testování každé úlohy se používají sady testovacích dat různé velikosti, takže teoreticky správné řešení založené na neefektivním algoritmu zvládne dokončit výpočet pouze pro některé, menší testy. Takové řešení je potom ohodnoceno dílčím počtem bodů. Krátce po odevzdání vypracovaného programu do vyhodnocovacího systému se soutěžící dozví hodnocení svého řešení a má pak ještě možnost jej opravit a odevzdat znovu. Jedná se o podobný systém, jaký používáme v posledních letech u nás v Matematické olympiádě – kategorie P pro praktické úlohy domácího kola. Divákům, ale nikoliv soutěžícím, byla k dispozici i průběžná výsledková listina.

Každá z šesti soutěžních úloh byla hodnocena maximálně 100 body, takže nejvyšší počet bodů, který bylo možné získat, byl 600. Tohoto výsledku dosáhl pouze jeden soutěžící z USA, který se tak stal absolutním vítězem olympiády. Na základě přesně stanovených pravidel se na IOI podle dosažených bodů rozdělují medaile. Některou z medailí obdrží nejvýše polovina účastníků soutěže, přičemž zlaté, stříbrné a bronzové medaile se rozdělují přibližně v poměru 1 : 2 : 3 (s ohledem na to, aby soutěžící se stejným bodovým ziskem získali stejnou medaili). Na letošní IOI bylo rozděleno celkem 26 zlatých, 52 stříbrných a 77 bronzových medailí. Výsledky našich soutěžících:

• 54. Jiří Eichler, 266 bodů, stříbrná medaile
• 101. Štěpán Šimsa, 197 bodů, bronzová medaile
• 111. Ondřej Hübsch, 192 bodů, bronzová medaile
• 185. Martin Zikmund, 125 bodů

Zisk tří medailí pro Českou republiku je dobrým výsledkem. Mezinárodní olympiáda v informatice je soutěží jednotlivců a žádné pořadí zúčastněných zemí v ní není vyhlašováno, ale v neoficiálním pořadí zemí by se letos Česká republika podle počtu získaných medailí umístila někde kolem 25.-30. místa, tzn. přibližně ve třetině celkového pořadí zemí. Nejúspěšnějšími zeměmi byly již tradičně Rusko a Čína, jejich soutěžící získali čtyři zlaté medaile. Studenti ze Slovenska si odvezli jednu zlatou a dvě bronzové medaile.

Všechny podrobnosti o soutěži, texty soutěžních úloh i celkové výsledky lze nalézt na Internetu na adrese http://www.ioi2012.org/ . Další ročníky IOI se budou konat postupně v Austrálii (2013), na Taiwanu (2014), v Kazachstánu (2015) a v Rusku (2016). Pořadatelé IOI 2013 z Austrálie na místě pozvali všechny zúčastněné země, aby se zúčastnily také následujícího ročníku soutěže ve dnech 6. - 13. 7. 2013 ve městě Brisbane v univerzitním areálu University of Queensland’s St Lucia (viz http://www.ioi2013.org/ ).