Soutěž ACM ICPC

Našim studentům se celkem dařilo
na mezinárodní soutěži v programování


ACM International Collegiate Programming Contest - http://icpc.baylor.edu/icpc/ - je celosvětová soutěž v programování pořádaná mezinárodní organizací Association for Computing Machinery, nejstarší počítačovou organizací na světě vůbec existující již od roku 1947. Soutěž je určena studentům vysokých škol po celém světě a probíhá ve dvou hlavních kolech - nejprve se soutěžící přihlásí do regionálního kola podle geografické polohy svého státu (například v Evropě je pět regionů). V našem regionu  soutěží Česká republika, Polsko, Slovensko, Rakousko, Maďarsko a Slovinsko. Nejlepší týmy z těchto kol postupují do světového finále, které se na různých místech koná  již od roku 1977.Letošní finále bude ve dnech 22.-26.3. v Beverly Hills v  Kalifornii. Kromě těchto dvou hlavních kol pořádá ČVUT v Praze ještě před regionálním kolem české a slovenské přípravné kolo této soutěže s názvem CTU Open Contest - http://contest.felk.cvut.cz/02prg/ , do kterého se mohou hlásit týmy z libovolné české či slovenské vysoké školy.

Soutěže se účastní tříčlenné týmy (vedené koučem), které řeší 5 až 10 úloh. Vlastní soutěž trvá 5 hodin a úlohy jsou zadávány v angličtině. Hlavním kritériem hodnocení je počet odevzdaných funkčních úloh, teprve na druhém místě je čas řešení. Řešení se vyhodnocuje plně automaticky, program je otestován na konkrétních datech. Pokud je jeho výstup správný a vypočten v časovém limitu, je program přijat. Záleží tedy na funkčnosti a efektivitě algoritmu. Hodnocení je zcela objektivní. Odevzdaná úloha, která nevyhověla zadání anebo překročila povolený čas výpočtu, je vrácena a tým má možnost ji přepracovat a znovu odevzdat. Tým má k dispozici jeden počítač, programuje se v ANSI C nebo Pascalu a je povolena jakákoliv literatura. Nesmějí se používat kalkulačky, mobilní telefony, pagery, jiná komunikační zařízení a vlastní hardware. Podrobnější informace o soutěži a příklady zadání úloh z minulých let a prostředí pro kontakt zájemců můžete najít na webové stránce http://www.kiv.zcu.cz/cz/pro-studenty/souteze/acm-icpc.

V posledních šesti letech se této soutěže účastní i týmy FAV ZČU v Plzni. Získaly dvakrát sedmé místo v přípravném kole v Praze a třikrát postoupily do regionálního kola. V listopadu 2002 se toto kolo konalo již podruhé ve Varšavě - http://cepc.mimuw.edu.pl/ . Soutěž byla tentokrát mimořádně těžká, o čemž svědčí fakt, že z celkového počtu 61 týmů plných 31 týmů nevypracovalo ani jednu úlohu. Naši univerzitu reprezentovaly dva týmy, z nichž zkušenější tým ve složení Martin Benda, Tomáš Budai, Ladislav Lang s koučem Ing. Radkem Svitákem obsadil 25. místo, ale před námi skončily z České republiky pouze dva týmy z  MFF Univerzity Karlovy, jejichž výuka je k typickým problémům řešeným v soutěži jen snad blíže, a navíc na MFF existuje seminář zaměřený přímo na přípravu k soutěži. Zbylé týmy z ostatních českých vysokých škol nevypracovaly ani jednu úlohu. Z tohoto pohledu můžeme považovat vystoupení našich studentů za úspěch.

V prosinci 2002 se uskutečnila beseda s účastníky  soutěže ve Varšavě s cílem získat další zájemce. Účast v této soutěži je velmi zajímavá a pokud máte v sobě alespoň trochu soutěživosti, určitě by se vám líbila. Svědčí o tom i to, že všichni naši soutěžící se účastní i  dalších ročníků. Jestliže máte hlavy otevřené, máte šanci postoupit do regionálního kola a podívat se tak "do světa". Navíc může dobrý výsledek zvýšit vaši prestiž a pomoci při získávání zaměstnání nebo stipendia na zahraniční univerzitě.

Zdůrazněme, že soutěž není jenom o kódování programu. Jako příklad uveďme následující problém. Pro Stirlingova čísla druhého druhu definovaná pro kladná celá čísla m a n rekurentním vztahem

                S(0,0) = 1,  S(0,n) = 0,  S(m,0) = 0,
                S(n,m) =mS(n-1,m) + S(n-1,m-1)

máte určit hodnotu  S(n,m) mod 2. Přímočarý rekurzivní program bude, řekněme pro větší hodnoty m a n, odmítnut kvůli časové náročnosti.

Student Karel Černohorský odvodil vlastnost,  která vede na následující programové řešení v Pascalu

                n := n – m;
                m:=(m-1)div2;
                if Boolean (m and n) then WriteLn(0) else WriteLn(1);

a jehož doba výpočtu je na velikosti m a n nezávislá.

I když nemáme na univerzitě speciální předmět nebo seminář  orientovaný na ACM soutěž, která by snad neměla být cílem vzdělávání, výsledek našich studentů prokázal, že v našem prostředí hlubokým studiem lze docílit velmi dobrých znalostí ve srovnání s podobnými univerzitami v mezinárodním okolí. Navíc v předmětu Algorithms Design and Problem Solving, už z jeho povahy, se využívá úloh z ACM jako prostředku a může být dobrou průpravou pro soutěž.

V případě, že máte  předběžný zájem o účast v soutěži, obraťte  se na  dále uvedenou e‑mailovou adresu: acm@mail.kiv.zcu.cz.


V článku byly aktualizovány kontaktní údaje.