Международный студенческий конкурс программирования ICPC

Введение

Международный конкурс программирования для студентов университетов

Международный студенческий конкурс программирования, известный как ICPC, — это ежегодное многоуровневое соревнование по программированию между университетами мира. Под руководством исполнительного директора ICPC и профессора Бейлора Уильяма Б. Пучера, ICPC организует автономные региональные конкурсы, охватывающие шесть континентов, которые ежегодно завершаются мировым финалом. В 2018 году в ICPC приняли участие 52 709 студентов из 3 233 университетов в 110 странах. ICPC действует под эгидой Фонда ICPC и работает на основании соглашений с университетами-организаторами и некоммерческими организациями, во всем соответствии с политикой и процедурами ICPC. С 1977 по 2017 год ICPC проводился под эгидой ACM и назывался ACM ICPC.

История

ICPC берет свое начало в соревновании, проведенном в Техасском университете A&M в 1970 году, организованном Альфа-главой Upsilon Pi Epsilon Computer Science Honor Society (UPE). Этот первоначальный конкурс программирования был назван Первым ежегодным Техасским коллегиальным чемпионатом программирования, и каждый университет был представлен командой из не более пяти участников. Используемый компьютер был моделью 360/65, одной из первых машин с системой DAT (Dynamic Address Translator, также известной как "paging") для доступа к памяти. В число команд-участниц вошли Техасский университет A&M, Техасский технологический университет, Университет Хьюстона и еще пять-шесть техасских университетов и колледжей. Участникам было предложено решить три задачи, и победители определялись по суммарному времени от "начала" до "успешного завершения". Языком программирования был Фортран. Программы писались на кодировочных листах, перфорировались на картах Холлерита и отправлялись на выполнение. Команда Университета Хьюстона выиграла соревнование, успешно решив все три задачи в отведенное время. Команды, занявшие второе и третье места, не смогли успешно решить все три задачи. В 1977 году конкурс приобрел свой нынешний многоуровневый формат, а первый финал был проведен совместно с конференцией ACM Computer Science Conference. С 1977 по 1989 год в конкурсе участвовали преимущественно команды из четырех человек из университетов США и Канады. Штаб-квартира ICPC располагалась в Университете Бейлора с 1989 по 2022 год. Благодаря учреждению региональных соревнований в мировом университетском сообществе, ICPC превратился в международное соревнование. Для расширения доступа к мировому финалу численность команд была сокращена до трех студентов, обучающихся на первых пяти курсах. С 1997 по 2017 год спонсором ICPC была корпорация International Business Machines Corporation (IBM). За этот период участие в конкурсе выросло более чем на 2000%. В 1997 году в нем приняли участие 840 команд из 560 университетов, а в 2017 году – 46 381 студент из 2948 университетов в 103 странах на шести континентах в региональных соревнованиях. ICPC организован как локализованный внеучебный интеллектуальный вид спорта и функционирует как глобально координированная некоммерческая ассоциация, действующая на основании соглашений с принимающими университетами и некоммерческими организациями. ICPC открыт для квалифицированных команд из любого университета мира. UPE оказывает непрерывную поддержку с 1970 года и награждает финалистов мирового финала с первого финала в 1976 году. ICPC признателен за вклад членов ACM и помощь ACM в период с 1976 по 2018 год. Университет Бейлора с 1985 года служил местом расположения штаб-квартиры ICPC с 1989 по 2022 год. ICPC действует под эгидой ICPC Foundation, которая предоставляет глобальную штаб-квартиру ICPC для обслуживания глобально координированного сообщества, мероприятия которого проводятся в соответствии с соглашениями с принимающими университетами и некоммерческими организациями, чтобы гарантировать, что участие в ICPC открыто для квалифицированных команд из любого университета мира. Подробности смотрите в Политике и процедурах ICPC. Участие в Северной Америке значительно меньше, чем в остальном мире, что частично объясняется низкой воспринимаемой выгодой от участия.

The ICPC traces its roots to a competition held at Texas A&M University in 1970 hosted by the Alpha Chapter of the Upsilon Pi Epsilon Computer Science Honor Society (UPE). This initial programming competition was titled First Annual Texas Collegiate Programming Championship and each university was represented by a team of up to five members. The computer used was a 360 model 65 which was one of the first machines with a DAT (Dynamic Address Translator aka "paging") system for accessing memory. Teams that participated included Texas A&M, Texas Tech, University of Houston, and five or six other Texas University / Colleges. There were three problems that had to be completed and the cumulative time from "start" to "successful completion" determined first , second , and third place winners. The programming language used was Fortran. The programs were written on coding sheets, keypunched on Hollerith cards, and submitted for execution. The University of Houston team won the competition completing all three problems successfully with time. The second and third place teams did not successfully complete all three problems. The contest evolved into its present form as a multi tier competition in 1977, with the first finals held in conjunction with the ACM Computer Science Conference. From 1977 to 1989, the contest included mainly teams of four from universities throughout the United States and Canada. ICPC Headquarters was hosted by Baylor University from 1989 until 2022, with regional contests established within the world's university community, the ICPC has grown into a worldwide competition. To increase access to the World Finals, teams were reduced to three students within their first five academic years. From 1997 to 2017, International Business Machines Corporation (IBM) was the sponsor of ICPC. During that time contest participation has grown by more than 2000%. In 1997, 840 teams from 560 universities participated. In 2017, 46,381 students from 2,948 universities in 103 countries on six continents participated in regional competitions. Organized as a highly localized extra curricular university mind sport and operating as a globally coordinated unincorporated association operating under agreements with host universities and non profits, the ICPC is open to qualified teams from every university in the world. UPE has provided continuous support since 1970 and honored World Finalists since the first Finals in 1976. The ICPC is indebted to ACM member contributions and ACM assistance from 1976 to 2018. Baylor University served since 1985, hosting ICPC Headquarters from 1989 until 2022. The ICPC operates under the auspices of the ICPC Foundation which provides the ICPC Global Headquarters to service a globally coordinated community whose events operate under agreements with host universities and non profits to insure that participation in ICPC is open to qualified teams from every university in the world. See ICPC Policies and Procedures. Participation in North America is much smaller than in the rest of the world, which is partially attributed to the perceived low payoff of participating.

Правила конкурса

Конкурсы ICPC — командные соревнования. Согласно текущим правилам, каждая команда состоит из трех студентов. Участники должны быть студентами университетов, имеющими менее пяти лет высшего образования на момент начала соревнований. Студенты, ранее участвовавшие в двух мировых финалах или пяти региональных соревнованиях, не допускаются к повторному участию. Во время каждого соревнования командам из трех человек дается 5 часов на решение от восьми до пятнадцати задач по программированию (восемь задач обычно предлагается в региональных соревнованиях, а двенадцать — в финалах). Решения необходимо представлять в виде программ на C, C++, Java, Ada, Python или Kotlin (хотя не гарантируется, что каждую задачу можно решить на каком-либо конкретном языке, на сайте ICPC указано, что "судьи решат все задачи на Java и C++" как в региональных, так и в мировых финалах). Затем программы запускаются на тестовых данных. Если программа не выдает правильный ответ, команда уведомляется и может отправить другое решение. Победителем становится команда, правильно решившая наибольшее количество задач. В случае равенства результатов для определения мест при распределении медалей или призов, приоритет определяется суммой времени, затраченного на отправку правильных решений, плюс 20 минут за каждую отклоненную попытку решения, которое в итоге было принято. Время, затраченное на нерешенные задачи, не учитывается. По сравнению с другими соревнованиями по программированию (например, Международной олимпиадой по информатике), ICPC характеризуется большим количеством задач (восемь или более задач всего за 5 часов). Еще одна особенность заключается в том, что каждая команда может использовать только один компьютер, несмотря на то, что в команде три участника. Это создает дополнительное давление времени. Для победы необходима слаженная командная работа и умение справляться с давлением.

Финалы мира 2004 года

Мировой финал ACM ICPC 2004 года принимал Пражский дом советов (Obecni Dum) при поддержке Чешского технического университета в Праге. В отборочных раундах соревновались 3150 команд, представляющих 1411 университетов из 75 стран, из которых 73 команды прошли в мировой финал. Победу одержал Санкт-Петербургский институт точной механики и оптики из России, решив 7 из 10 задач. Золотые медали завоевали Санкт-Петербургский институт точной механики и оптики, Королевский технологический институт КТХ (Швеция), Белорусский государственный университет и Пермский государственный университет (Россия).

Мировые финалы 2005 года

Мировой финал 2005 года состоялся 6 апреля 2005 года в отеле Pudong Shangri La в Шанхае при поддержке Шанхайского университета Цзяо Тон. В отборочных раундах соревновались 4109 команд из 1582 университетов 71 страны, из которых 78 команд прошли в мировой финал. Шанхайский университет Цзяо Тон одержал свою вторую победу, решив 8 из 10 задач. Золотые медали завоевали Шанхайский университет Цзяо Тон, Московский государственный университет (Россия), Санкт-Петербургский институт точной механики и оптики (Россия) и Университет Ватерлоо (Канада).

Финалы мира 2006 года

Мировые финалы ACM ICPC 2006 года состоялись в Сан-Антонио, штат Техас, при поддержке Университета Бейлора. В отборочных раундах соревновались 5606 команд, представляющих 1733 университета из 84 стран, и 83 команды прошли в мировой финал. Победу одержал Саратовский государственный университет из России, решив 6 из 10 задач. Золотые медали завоевали команды Саратовского государственного университета, Ягеллонского университета (Польша), Алтайского государственного технического университета (Россия) и Университета Твенте (Нидерланды).

Мировые финалы 2007 года

Мировые финалы ACM ICPC 2007 года проходили в отеле Tokyo Bay Hilton, в Токио, Япония, с 12 по 16 марта 2007 года. Организаторами Мировых финалов выступили Японское отделение ACM и Токийская исследовательская лаборатория IBM. Около 6099 команд соревновались на региональном уровне на шести континентах. В Мировые финалы прошли 88 команд. Варшавский университет одержал свою вторую победу в чемпионате мира, решив 8 из 10 задач. Золотые медали завоевали Варшавский университет, Университет Цинхуа (Китай), Санкт-Петербургский институт точной механики и оптики (Россия) и Массачусетский технологический институт (США). Серебряные медали получили Шанхайский университет Цзяо Тун (Китай) и еще 3 университета.

Финалы мира 2008 года

Мировые финалы ACM ICPC 2008 года прошли в отеле Fairmont Banff Springs в городе Банф, провинция Альберта, Канада, с 6 по 10 апреля 2008 года. Организатором Мировых финалов выступил Университет Альберты. В Мировых финалах участвовало 100 команд, отобранных из 6700 команд, соревновавшихся на предыдущих этапах. Санкт-Петербургский институт точной механики и оптики завоевал свой второй титул чемпиона мира. Золотые медали также получили Массачусетский технологический институт, Ижевский государственный технический университет и Львовский национальный университет.

Мировые финалы 2009 года

Мировые финалы ACM ICPC 2009 года прошли в Стокгольме, Швеция, с 18 по 22 апреля, на территории Королевского технологического института КТХ, принимавшей стороны, а также в отелях Grand Hotel, Radisson Strand и Diplomat. В борьбе за звание чемпиона мира участвовали 100 команд из более чем 200 региональных центров. Санкт-Петербургский институт точной механики и оптики отстоял свой титул, завоевав свой третий чемпионат мира. Университет Цинхуа, Санкт-Петербургский государственный университет и Саратовский государственный университет также стали обладателями золотых медалей. Всемирный финал 2009 года впервые в истории транслировался в прямом эфире, с элементами, такими как экспертные комментарии, прямые трансляции работы команд и их экранов, а также интервью с судьями, тренерами и официальными лицами. Трансляция велась в интернете и на шведском телеканале Axess TV.

Финалы мира 2010 года

Мировые финалы ACM ICPC 2010 года прошли в Харбине, Китай. Организатором выступил Харбинский инженерный университет. Шанхайский университет Цзяо Тонг выиграл чемпионат мира. Золотые медали также получили Московский государственный университет, Национальный университет Тайваня и Киевский национальный университет имени Тараса Шевченко.

Победители

+22000 Побед Страна Учреждение Последние 7 ITMO University 2017 4 Saint Petersburg State University 2016 3 Shanghai Jiao Tong University 2010 3 Stanford University 1991 2 Massachusetts Institute of Technology 2022 2 Moscow State University 2019 2 University of Warsaw 2007 2 University of Waterloo 1999 2 California Institute of Technology 1988 2 Washington University in St. Louis 1980

+Год Страна Учреждение Страна-хозяйка Город-хозяин 2023 National Research University Higher School of Economics Luxor 2022 Peking University Luxor 2021 Massachusetts Institute of Technology Dhaka 2020 Nizhny Novgorod State University Moscow 2019 Moscow State University Porto 2018 Moscow State University Beijing 2017 ITMO University Rapid City, South Dakota 2016 St. Petersburg State University Phuket 2015 ITMO University Marrakech 2014 St. Petersburg State University Ekaterinburg 2013 ITMO University Saint Petersburg 2012 ITMO University Warsaw 2011 Zhejiang University Orlando, Florida 2010 Shanghai Jiao Tong University Harbin 2009 ITMO University Stockholm 2008 ITMO University Banff, Alberta 2007 University of Warsaw Urayasu, Chiba 2006 Saratov State University San Antonio, Texas 2005 Shanghai Jiao Tong University Shanghai 2004 ITMO University Prague 2003 University of Warsaw Beverly Hills, California 2002 Shanghai Jiao Tong University Honolulu, Hawaii 2001 St. Petersburg State University Vancouver, British Columbia 2000 St. Petersburg State University Orlando, Florida 1999 University of Waterloo Eindhoven 1998 Charles University Atlanta, Georgia 1997 Harvey Mudd College San Jose, California 1996 University of California, Berkeley Philadelphia, Pennsylvania 1995 Albert Ludwigs Universität Nashville, Tennessee 1994 University of Waterloo Phoenix, Arizona 1993 Harvard University Indianapolis, Indiana 1992 University of Melbourne Kansas City, Missouri 1991 Stanford University San Antonio, Texas 1990 University of Otago Washington, DC 1989 University of California, Los Angeles Louisville, Kentucky 1988 California Institute of Technology Atlanta, Georgia 1987 Stanford University St Louis, Missouri 1986 California Institute of Technology Cincinnati, Ohio 1985 Stanford University New Orleans, Louisiana 1984 Johns Hopkins University Philadelphia, Pennsylvania 1983 University of Nebraska–Lincoln Melbourne, Florida 1982 Baylor University Indianapolis, Indiana 1981 University of Missouri–Rolla St Louis, Missouri 1980 Washington University in St. Louis Kansas City, Missouri 1979 Washington University in St. Louis Dayton, Ohio 1978 Massachusetts Institute of Technology Detroit, Michigan 1977 Michigan State University Atlanta, Georgia

+YearsYearCountryInstitutionHost CountryHost City 2023 National Research University Higher School of Economics Luxor 2022 Peking University Luxor 2021 Massachusetts Institute of Technology Dhaka2020Nizhny Novgorod State University Moscow2019Moscow State University Porto2018Moscow State University Beijing2017 ITMO University Rapid City, South Dakota2016 St. Petersburg State University Phuket2015 ITMO University Marrakech 2014 St. Petersburg State University Ekaterinburg2013 ITMO University Saint Petersburg2012 ITMO University Warsaw2011 Zhejiang University Orlando, Florida2010 Shanghai Jiao Tong University Harbin2009 ITMO University Stockholm 2008 ITMO University Banff, Alberta2007 University of Warsaw Urayasu, Chiba2006 Saratov State University San Antonio, Texas 2005 Shanghai Jiao Tong University Shanghai2004 ITMO University Prague 2003 University of Warsaw Beverly Hills, California 2002 Shanghai Jiao Tong University Honolulu, Hawaii 2001 St. Petersburg State University Vancouver, British Columbia 2000 St. Petersburg State University Orlando, Florida 1999 University of Waterloo Eindhoven 1998 Charles University Atlanta, Georgia 1997 Harvey Mudd College San Jose, California 1996 University of California, Berkeley Philadelphia, Pennsylvania 1995 Albert Ludwigs Universität Nashville, Tennessee1994 University of Waterloo Phoenix, Arizona 1993 Harvard University Indianapolis, Indiana 1992 University of Melbourne Kansas City, Missouri 1991 Stanford University San Antonio, Texas 1990 University of Otago Washington, DC 1989 University of California, Los Angeles Louisville, Kentucky 1988 California Institute of Technology Atlanta, Georgia 1987 Stanford University St Louis, Missouri 1986 California Institute of Technology Cincinnati, Ohio 1985 Stanford University New Orleans, Louisiana 1984 Johns Hopkins University Philadelphia, Pennsylvania 1983 University of Nebraska Lincoln Melbourne, Florida 1982 Baylor University Indianapolis, Indiana 1981 University of Missouri–Rolla St Louis, Missouri 1980 Washington University in St. Louis Kansas City, Missouri 1979 Washington University in St. Louis Dayton, Ohio 1978 Massachusetts Institute of Technology Detroit, Michigan 1977 Michigan State University Atlanta, Georgia

+Страны Победитель Страна Последняя победа Количество лет участия 18 2021 47 16 2023 28 (с 1996) 5 2022 2 2007 2 1999 1 1998 1 1995 1 1992 1 1990

Известные участники

Некоторые бывшие финалисты ICPC добились выдающихся успехов в индустрии программного обеспечения и научных исследованиях. Среди них Адам Д'Анджело, бывший технический директор Facebook и основатель Quora; Николай Дуров, сооснователь Telegram Messenger; Матей Захария, создатель Apache Spark; Тони Хси, генеральный директор Zappos и венчурный инвестор; Амит Сахай, известный профессор, специализирующийся в области безопасности и криптографии; и Крейг Сильверштейн, первый сотрудник Google.