Mezinárodní olympiáda studentského programování

International Student Programming Olympiad (v angličtině zkráceně ICPC , do roku 2017 - ACM ICPC ), nazývaná také World Student Team Programming Championship ICPC - největší programovací olympiáda studentských týmů .

Historie

Mistrovství světa v programování studentských týmů ICPC má své kořeny v soutěži pořádané na Texaské univerzitě v roce 1970. Současnou podobu získalo mistrovství v roce 1977, kdy se v rámci výroční konference ACM Computer Science konalo první finále . koná se každoročně od [1 ] [2] .

Do roku 2017 se šampionát konal pod záštitou Asociace pro výpočetní techniku ​​(ACM). Od roku 1989 soutěž pořádá Baylor University [1] . V různých dobách se sponzory soutěže staly společnosti jako Apple , AT&T a Microsoft [3] , v letech 1997 až 2017 byla generálním sponzorem IBM [1] [4] , od roku 2018 je globálním sponzorem programovacích nástrojů JetBrains [ 4] .

Od roku 1977 do roku 1989 se olympiády účastnily především týmy univerzit z USA a Kanady . Olympiáda se k dnešnímu dni stala celosvětovou soutěží: v roce 2019 se jí zúčastnilo 52 7097 účastníků z 3 233 vzdělávacích institucí zastupujících 110 zemí. V boji o hlavní trofej na závěrečném turnaji se sešlo 135 týmů. Počet týmů nadále roste o 10-20 % ročně, takže do budoucna soutěž slibuje ještě více reprezentovat.

Rusko , Ázerbájdžán , Arménie , Bělorusko , Gruzie , Kazachstán , Kyrgyzstán , Uzbekistán tvoří severoeurasijský region , který každoročně deleguje své nejlepší týmy na závěrečný turnaj. Kvóta kraje v počtu týmů od roku 2009 do roku 2013 se každoročně zvyšovala: v roce 2009 bylo do finále posláno 11 týmů, v roce 2010 - 12 týmů, v roce 2011 - 13 týmů, v roce 2012 - 16 týmů, v roce 2013 - 19 týmů, v roce 2014 - 17 týmů [5] . Pobaltské státy opustily semifinálový region severovýchodní Evropy: Estonsko v roce 2018 [6] , Litva a Lotyšsko v roce 2020 [7]

Pravidla

Olympiáda je týmová soutěž. Každý tým se skládá ze tří studentů. Účast je umožněna studentům vysokých škol i absolventům prvního ročníku studia . Studenti, kteří se dvakrát zúčastnili závěrečné fáze olympiády nebo se pětkrát zúčastnili krajského výběru, se nemohou zúčastnit. Existuje věkové omezení: účastníci starší 24 let nejsou povoleni [8] .

Kolo olympiády probíhá následovně: každý tým dostane na pět hodin počítač a osm až dvanáct úloh, jejichž podmínky jsou psány anglicky [9] . Týmy píší řešení v programovacích jazycích C , C++ , Java , Python nebo Kotlin psaním a kompilací programů pomocí Ubuntu 18.04. LTS(2018) a pošlete je na testovací server . Během některých regionálních zájezdů může být sada jazyků změněna. Takže například při pořádání čtvrtfinále v severovýchodní oblasti je účastníkům k dispozici Pascal [9] . Programy jsou testovány na velkém počtu různých vstupních testů, které účastníci neznali. Pokud program odpověděl nesprávně nebo nesplnil časové nebo paměťové limity, příkaz, který jej odeslal, o tom obdrží zprávu a může odeslat opravenou verzi. Problém je považován za vyřešený, pokud program ve všech testech odpověděl správně. Na rozdíl od jiných olympiád se nepočítá s dílčími řešeními.

Vyhrává tým, který správně vyřeší nejvíce problémů. Pokud několik týmů vyřeší stejný počet problémů, je jejich umístění v žebříčku určeno časem penalt. Zpočátku je penaltový čas každého týmu nulový. Za každý správně zadaný problém si týmy k penalizačnímu času připočítají čas, který uplynul od začátku soutěže do okamžiku předání problému. Pokud navíc platnému pokusu předcházelo několik neúspěšných pokusů o překonání stejného problému, pak se k trestnému času za každý z nich připočítává dvacet minut. Za neúspěšné pokusy o průchod problému, který se týmu nakonec nepodařilo vyřešit, se neúčtuje penalizační čas [10] .

Tato olympiáda se od ostatních olympiád v informatice liší zvýšeným počtem úkolů, na které je vyčleněno relativně málo času. Vzhledem k tomu, že každý tým má k dispozici pouze jeden počítač, vystupují do popředí dovednosti efektivní a dobře koordinované týmové práce.

Mnoho univerzit pořádá své soutěže ve formátu ICPC, protože tento formát lze považovat za jeden z nejúspěšnějších.

Etapy

Olympijské hry se konají na několika úrovních. Mnoho univerzit pořádá interní soutěže o určení svých zástupců na regionální úrovni. Poté se konají krajské olympiády, jejichž vítězové postupují do závěrečné fáze mistrovství světa. V krajských soutěžích může jednu univerzitu reprezentovat více týmů, ale do finále může postoupit pouze jeden tým z univerzity.

Vítězové

Mistři světa od roku 1977 byli:

Rok Umístění Vítěz Sestava Trenér
2020*  Rusko ,Moskva UNN Alexey Danilyuk, Nikolaj Kalinin, Valeria Ryabchikova Alexej Šmelev
2019  Portugalsko ,Porto Moskevská státní univerzita Michail Ipatov, Vladislav Makejev, Grigorij Reznikov Elena Andreeva
2018  Čína ,Peking Moskevská státní univerzita Michail Ipatov, Vladislav Makejev, Grigorij Reznikov Elena Andreeva
2017  USA ,Rapid City Petrohradská státní univerzita informačních technologií, mechaniky a optiky Ivan Belonogov, Ilja Zban, Vladimir Smykalov Andrej Stankevič
2016  Thajsko ,Phuket Petrohradská státní univerzita Stanislav Ershov, Alexey Gordeev, Igor Pyshkin Andrej Lopatin
2015  Maroko ,Marrákeš Petrohradská státní univerzita informačních technologií, mechaniky a optiky Gennadij Korotkevič , Boris Minajev, Arťom Vasiliev Andrej Stankevič
2014  Rusko ,Jekatěrinburg Petrohradská státní univerzita Dmitrij Egorov, Pavel Kunyavskij, Jegor Suvorov Andrej Lopatin
2013  Rusko ,Petrohrad Petrohradská státní univerzita informačních technologií, mechaniky a optiky Michail Kever, Gennadij Korotkevič , Niyaz Nigmatullin Andrej Stankevič
2012  Polsko ,Varšava Petrohradská státní univerzita informačních technologií, mechaniky a optiky Jevgenij Kapun, Michail Kever, Niyaz Nigmatullin Andrej Stankevič
2011  USA ,Orlando Univerzita Zhejiang Luyi Mo, Jialin Ouyang, Zejun Wu Wang Can Wang
2010  Čína ,Charbin Šanghajská dopravní univerzita (Jiaotong) Bin Jin, Zhuojie Wu, Zhao Zheng Yong Yu
2009  Švédsko ,Stockholm Petrohradská státní univerzita informačních technologií, mechaniky a optiky Vladislav Isenbaev, Maxim Buzdalov , Jevgenij Kapun Andrej Stankevič
2008  Kanada ,Banff Petrohradská státní univerzita informačních technologií, mechaniky a optiky Dmitrij Abdrašitov, Dmitrij Paraščenko, Fedor Carev Andrej Stankevič
2007  Japonsko ,Tokio Varšavská univerzita Filip Wolski, Marcin Pilipczuk, Marek Cygan Jan Madey
2006  USA ,San Antonio Saratovská státní univerzita Roman Alekseenkov, Igor Kulkin, Ivan Romanov Michail Mirzajanov
2005  Čína ,Šanghaj Šanghajská dopravní univerzita (Jiaotong) Dai Wenyuan, Shuang Zhao, Bohai Yang Yong Yu
2004  Česká republika ,Praha Petrohradská státní univerzita informačních technologií, mechaniky a optiky Dmitrij Pavlov, Pavel Mavrin, Sergey Orshansky Andrej Stankevič
2003  USA ,Beverly Hills Varšavská univerzita Tomasz Czajka, Krzysztof Onak, Andrzej Gasienica-Samek Jan Madey
2002  USA ,Honolulu Šanghajská dopravní univerzita (Jiaotong) Lin Chenxi (Chenxi Lin), Zhou Jian (Jian Zhou), Lu Jing (Jing Lu) Yong Yu
2001  Kanada ,Vancouver Petrohradská státní univerzita Nikolaj Durov, Andrey Lopatin, Viktor Petrov Dmitrij Lomov
2000  USA ,Orlando Petrohradská státní univerzita Nikolaj Durov, Andrey Lopatin, Oleg Eterevsky Natalia Vojakovskaya
1999  Nizozemsko ,Eindhoven University of Waterloo Ondřej Lhoták, Viet-Trung Luu, David Kennedy, Donny Cheung Gordon Cormack
1998  USA ,Atlanta Univerzita Karlova (Praha) Jiří Hájek, Pavel Machek, Martin Mareš Pavel Töpfer
1997  USA ,San Jose Harvey Mudd College Hrají Brian Carnes, Brian Johnson, Kevin Watkins, Dominic Mazzoni Robert Keller
1996  USA ,Philadelphia UC Berkeley Ben Rudiak-Gould, Amit Sahai, Scott McPeak Paul Hilfinger
1995  USA ,Nashville Univerzita ve Freiburgu Matthias Ruhl, Christian Wetzel, Phillip Zembrod
1994  USA ,Phoenix University of Waterloo Seiji Ando, ​​Ian Goldberg, Ka-Ping Yee Joe Ebergen
1993  USA ,Indianapolis Harvardská Univerzita Derrick Bass, Tony Shay , Craig Silverstein
1992  USA ,Kansas City Melbourne University Andrew Conway, Craig Dillon, Stephen Simmons
1991  USA ,San Antonio Stanfordská Univerzita Michael Patrick Frank, Sean Quinlan, David Magerman, Carl Witty
1990  USA ,Washington University of Otago John Gee, Craig McNaughton, Paul Sharp, Bruce Warrington
1989  USA ,Louisville Kalifornská univerzita v Los Angeles Seth Goldman, Alex Quilici, Matthew Marzbacher, Scott Turner
1988  USA ,Atlanta Kalifornský technologický institut Dave Gillespie, Adam Greenblatt, Ron Goodman, Scott Hemphill
1987  USA ,St. Louis Stanfordská Univerzita Bob Alverson, Tomas Rokicki, Ali Tabibian, Lei Zhu
1986  USA ,Cincinnati Kalifornský technologický institut Steve Burns, Tim Kay, Dave Gillespie, Steve Rabin, Rajiv Gupta
1985  USA ,New Orleans Stanfordská Univerzita Michael Dixon, Micheal Hewett, Vivek Sarkar, Joseph Weening
1984  USA ,Philadelphia Univerzita Johnse Hopkinse Michael Baldwin, Robert Strandh, John Walker, Richard Washington Joseph O'Rourke
1983  USA ,Melbourne University of Nebraska Mark Tuttle, Thane Plambeck, David Leavitt, Paul Petersen
1982  USA ,Indianapolis Baylorova univerzita Keith Hall, Patrick Keane, Jennifer Harmon, Terry Talley Don Gaitros
1981  USA ,St. Louis Missouri University Christopher Freund, Michael Richey, James Simmons, Catherine Pyron Fieseler
1980  USA ,Kansas City Univerzita Saint Louis Steve Karasek, Nathan Schroeder, Mike Zyda, Dave Camp
1979  USA ,Dayton Univerzita Saint Louis Steve Karasek, Nathan Schroeder, David Doty, Dave Camp
1978  USA ,Detroit Massachusetts Institute of Technology
1977  USA ,Atlanta Michiganská univerzita

* Kvůli pandemii COVID-19 se soutěž konala v říjnu 2021, některé týmy, které se nemohly zúčastnit, se zúčastnily samostatné soutěže online na platformě Codeforces. Vyhrál ho tým Tokijské univerzity (Wataru Inoue, Hirotaka Isa, Yuta Takaya) .

Poznámky

  1. 1 2 3 Informační list ICPC  (anglicky) (8. března 2019). Archivováno z originálu 25. března 2019.
  2. CSC '77 Sborník příspěvků z 5. výroční počítačové konference ACM  ( 1977). Staženo: 3. prosince 2010.
  3. Účast týmu ACM International Collegiate Programming Contest od roku  1989 . Získáno 3. prosince 2010. Archivováno z originálu dne 22. srpna 2011.
  4. ↑ 1 2 Michail Mirzajanov. ACM-ICPC Final 2017: Vede z oborů . Codeforces (23. května 2017). Získáno 25. března 2019. Archivováno z originálu dne 25. března 2019.
  5. Světoví finalisté ze severní Eurasie . Získáno 14. října 2019. Archivováno z originálu dne 14. října 2019.
  6. St. výsledky výběrového kola za roky 2017 a 2018 : Tallinn SU se přestal účastnit.
  7. St. výsledky výběrového kola 2020 a 2021 : VU a LU se přestaly účastnit (hvězdička před názvem týmu znamená účast mimo soutěž).
  8. Pravidla regionálních soutěží ICPC 2008  ( 27. února 2008). Získáno 3. prosince 2010. Archivováno z originálu dne 22. srpna 2011.
  9. 1 2 :: ACM ICPC, NEERC, Jižní subregion :: Pořadí a pravidla soutěže . Získáno 18. října 2011. Archivováno z originálu dne 21. září 2011.
  10. Pravidla světového finále ACM-ICPC 2009  ( 8. dubna 2008). Získáno 3. prosince 2010. Archivováno z originálu dne 22. srpna 2011.


Odkazy