Анатомия ICPC:
как устроен крупнейший и самый престижный чемпионат мира по программированию
как устроен крупнейший и самый престижный чемпионат мира по программированию
С 1 по 5 октября в Москве проходит финальный этап чемпионата мира ICPC ― крупнейшего и самого престижного международного турнира по программированию среди студентов. Соревнование объединит программистов из 42 стран, а Россию в финале представят 15 команд, в том числе студенты Университета ИТМО. Если у вас другие планы на эти дни, не спешите. Рассказываем, где и как следить за соревнованиями, почему русские кодеры ― лучшие в мире, зачем программистам воздушные шарики и почему турнир с тремя сотнями сидящих за компьютерами людей может поспорить по накалу страстей с Евро-2020.
Краткая история ICPC
Программирование — это так же круто, как Олимпиада. 5 аргументов
Как определяются лучшие программисты планеты
Что дает победа на соревнованиях
1970-е
ICPC (International Collegiate Programming Contest) — старейший и самый престижный мировой турнир по программированию. Чемпионат ведет свою историю с 1970-х годов ― именно тогда студенты, преподаватели и представители бизнеса из регионального отделения Международного почетного общества компьютерных наук (UPE Computer Science Honor Society) организовали в Техасском сельскохозяйственном и машиностроительном университете первое соревнование по программированию. За несколько лет идея быстро набрала популярность среди вузов США и Канады, и с 1977-го соревнования проводятся ежегодно.
1980-е
До конца 80-х в турнире в основном принимали участие студенты университетов США и Канады. Но в 1989 году событие вышло на мировой уровень. Число участников чемпионата превысило 1000 человек, соревновались команды из 308 вузов.
1990-е
В 90-е ICPC рос еще сильнее: за 10 лет число участников увеличилось в четыре раза. В эти же годы в чемпионате начала участвовать и Россия ― впервые наши команды поехали на соревнование в 1995 году.
А с начала 2000-х российские команды прочно укрепились на пьедестале почета. В 2000-м и 2001-м победу одерживали участники из СПбГУ, а в 2004 году абсолютными чемпионами впервые стали студенты Университета ИТМО (состав команды победителей: Дмитрий Павлов, Павел Маврин, Сергей Оршанский). Повторил успех Университет ИТМО в 2008 и 2009 годах.
Краткая история ICPC
2000-е
Начиная с 2012 года, российские команды и вовсе ни разу не отдавали победу соперникам. На протяжении шести лет кубок мира снова доставался двум петербургским вузам — Университету ИТМО (четыре победы за шесть лет) и СПбГУ (две победы за шесть лет). Контест 2018 года открыл еще одну российскую звезду турнира — МГУ им. Ломоносова, команда которого в неизменном составе одержала победу и в 2018, и в 2019 году.
2010-е
Финал чемпионата 1985 года (США, Новый Орлеан) / Icpc.global
Финал чемпионата 1985 года (США, Новый Орлеан) / Icpc.global
Победители чемпионата 1989 года (США. Луисвилл) / Icpc.global
Финал чемпионата 1990 года в Вашингтоне, США / Icpc.global
Чемпионы мира ACM ICPC 2004 года, Университет ИТМО / wikimedia.org
Самым титулованным участником чемпионата за всю историю остается Университет ИТМО: на счету команд петербургского вуза семь побед. Кроме того, именно представители ИТМО начинали движение ICPC в России и продолжают активно популяризировать соревнования в стране.
«ICPC — это семья, которая без преувеличения объединяет людей по всему миру. Из этой глобальной семьи вышло уже несколько поколений программистов. Я помню те давние времена, когда мы только начали взаимодействовать с Университетом ИТМО. Тогда перед нами стояли великие вызовы и великие возможности. И тогда же я узнал, что здесь создана программа, цель которой — собрать вместе талантливейших студентов и дать им возможности для развития. То, что вы делаете, впечатляет»
Билл Паучер,
исполнительный директор ICPC Global
исполнительный директор ICPC Global
Сейчас
В последние годы в отборочных турах ICPC участвуют уже более 60 000 студентов-программистов из более 3000 университетов 115 стран. По масштабу соревнования могут поспорить с крупнейшими спортивными турнирами.
Ежегодно ICPC собирает больше участников, чем Олимпийские игры. Например, в 2017 году в чемпионате приняли участие 46 381 человек из 103 стран, в то время как в летней Олимпиаде в Рио-де-Жанейро на всех этапах участвовали 11 544 спортсмена.
Спортивное программирование ― это так же круто, как Олимпийские игры. И даже круче. Вот 5 аргументов
1
ICPC во многом похож на Олимпийские игры и другие крупнейшие спортивные соревнования. Чемпионат является самым масштабным турниром по спортивному программированию. Задача спортивных программистов ― писать код и решать нестандартные задачи на время. При этом важно найти не только самое быстрое, но и самое эффективное решение.
Поэтому олимпиадное программирование можно сравнить с шахматами или «Формулой-1» ― здесь также важна не только скорость, но и стратегия. Неслучайно спортивные программисты считаются самыми изобретательными специалистами в своей области, ведь они учатся искать неочевидные подходы к решению задач, делать это быстро и выдавать итоговое решение в виде компактного, эффективного кода.
2
Как и в спорте, участники команд годами тренируются, чтобы представить свой университет в финале ICPC. До соревнований они изучают языки программирования, отрабатывают разные технологии и решают рутинные задачи, чтобы непосредственно на турнире показать максимум своих возможностей.
В финале ICPC на поиск оптимального решения конкретной задачи у участника есть в среднем 25–30 минут (за 300 минут соревнований нужно решить 12 задач). При этом лучшие спортивные программисты решают задачи еще быстрее — за пять-семь минут.
Например, Николай Будин, один из членов сборной ИТМО, который вместе с Арсением Кирилловым и Дмитрием Саютиным представит университет в финале чемпионата в Москве, активно занимается программированием с восьмого класса школы. К разным этапам ICPC он готовился с первого курса бакалавриата (с 2015 года). Николай также сам проводит тренировки для начинающих на факультете информационных технологий и программирования ИТМО, на них приглашаются все желающие студенты вуза. Вот чат тренировок, вы тоже можете попробовать.
Тренировки, как и у спортсменов, проходят регулярно и занимают по несколько часов. Как отмечает двукратный чемпион ICPC Нияз Нигматуллин, перед тем, как поехать на финал чемпионата, он вместе с командой тренировался минимум дважды в неделю ― каждая из тренировок длилась по пять часов. Кроме этого, не меньше семи часов в неделю каждый член команды готовился индивидуально.
Тренировки, как и у спортсменов, проходят регулярно и занимают по несколько часов. Как отмечает двукратный чемпион ICPC Нияз Нигматуллин, перед тем, как поехать на финал чемпионата, он вместе с командой тренировался минимум дважды в неделю ― каждая из тренировок длилась по пять часов. Кроме этого, не меньше семи часов в неделю каждый член команды готовился индивидуально.
Николай Будин
«При подготовке к чемпионату прежде всего важен личный рост, изучение новых подходов, решение большой базы задач. Если нам требуется улучшить навыки в некотором типе задач, мы открываем базу, решаем, читаем статьи, общаемся в интернете с другими ребятами, чтобы получить ценные советы. Без самостоятельной работы приносить пользу команде будет очень сложно. Кроме этого, в интернете много индивидуальных онлайн-соревнований. Они помогают сконцентрироваться, проверить свои силы, когда время ограничено, и увидеть, каких еще навыков не хватает.
Нияз Нигматуллин, двукратный чемпион ICPC,
ассистент факультета информационных технологий и программирования ИТМО
ассистент факультета информационных технологий и программирования ИТМО
Также важная часть подготовки к командным соревнованиям ― это тренировки в команде. Они длятся по пять часов и выглядят как симуляция соревнования, на них участники на время решают задачи с прошлых турниров. Это, конечно, не совсем то же самое, что и реальный контест, но очень близко и помогает тренироваться в боевом режиме. После тренировок команда и тренер обсуждают, что не получилось, анализируют, что члены команды делали в разные моменты времени в течение пяти часов, и определяют, что можно улучшить».
3
Как и на Олимпиаде, отбор на финал ICPC проходит по многоступенчатой схеме: все университеты мира разбиты по территориальному признаку на регионы, в которых проводятся полуфиналы. Например, Россия, Беларусь, Казахстан, страны Прибалтики, Кавказа и Средней Азии объединены в единый регион — Северную Евразию. Крупные регионы разбиты также на подрегионы, которые имеют свои четвертьфиналы.
Для каждого полуфинала ежегодно определяется квота команд, которые выходят от данного полуфинала в финал. Квота зависит от ряда факторов: от количества команд, участвовавших в отборочных соревнованиях от данного региона, результатов, показанных регионом за историю участия в ICPC, и так далее. В региональных соревнованиях один университет может быть представлен несколькими командами, но на финал от университета может отправиться только одна.
И, конечно, как на любых больших соревнованиях, не обходится без своих традиций и забавных историй.
И, конечно, как на любых больших соревнованиях, не обходится без своих традиций и забавных историй.
“
Как-то во время основного пятичасового тура полуфинального соревнования ICPC участник одной из команд начал делать пару десятков отжиманий от пола. При этом почти все эти пять часов команда шла в лидерах соревнования. Чтобы понимать, в чем суть, поясню правила: в ICPC, если несколько команд решили одинаковое количество задач, победитель определяется по времени, которое было затрачено на решение: чем быстрее команда справилась с заданием, тем выше ее позиция. Также предусмотрены штрафы: если команда отправила неправильное решение, ко времени добавляют штрафные 20 минут. Естественно, команды хотят этого избежать, ведь со штрафами шансов на победу становится меньше.
В узких кругах спортивных программистов есть даже такой развлекательно-поучительный способ тренировки: если тот, кто решал задачу, отправил неправильное решение, то в качестве "наказания" этот участник делает 20 отжиманий. И вот участники той команды договорились сделать это и в официальном соревновании. Думаю, любой, кто не знаком с ICPC, был бы очень удивлен тому, что посреди напряженного турнира, где важна каждая минута, человек внезапно встает и начинает отжиматься. От меня команде уважение, я бы на такое не смог решиться.
В узких кругах спортивных программистов есть даже такой развлекательно-поучительный способ тренировки: если тот, кто решал задачу, отправил неправильное решение, то в качестве "наказания" этот участник делает 20 отжиманий. И вот участники той команды договорились сделать это и в официальном соревновании. Думаю, любой, кто не знаком с ICPC, был бы очень удивлен тому, что посреди напряженного турнира, где важна каждая минута, человек внезапно встает и начинает отжиматься. От меня команде уважение, я бы на такое не смог решиться.
4
А еще у каждой команды есть свой тренер. А среди тренеров, как и в футболе, есть свои легенды. Все команды ИТМО, становившиеся абсолютными чемпионами мира, тренировал Андрей Станкевич. За 20 лет он подготовил не одно поколение победителей и призеров чемпионата ICPC. Несколько лет назад за эти заслуги Станкевичу вручили престижную награду ACM ICPC Senior Coach Award.
Международная Ассоциация вычислительной техники и раньше высоко оценивала вклад петербургского преподавателя в развитие отрасли: на его счету международная премия ACM ICPC Founder’s Award за участие в организации олимпиад программистов в Европе. Помимо этого, его труд отметила и корпорация IBM, которая в 2008 году наградила его специальной премией за успехи в тренерской работе.
Андрей Станкевич также посвящает немалую часть своего времени олимпиадам по программированию для школьников и студентов не только Северной столицы, но и всей России. Он составляет задачи, занимается организацией и является председателем жюри крупных конкурсов городского и федерального масштаба.
5
И наконец, как и в спорте, среди самих спортивных программистов есть свои звезды. Главные технические разработчики «ВКонтакте» и Telegram — Николай Дуров и Андрей Лопатин — дважды чемпионы мира по спортивному программированию. Еще один призер ICPC — предприниматель Тони Шей ― спустя всего три года после победы в чемпионате заработал 265 млн долларов, а затем создал онлайн-магазин одежды Zappos.com (в 2009 году Amazon заплатила за нее 1,2 млрд долларов). Также среди победителей чемпионата — сооснователь Facebook Адам Ди Анджело, бывший директор по технологиям Google Крейг Силверстайн и один из нынешних ведущих инженеров компании Петр Митричев.
А в аспирантуре Университета ИТМО учится двукратный чемпион ICPC и самый титулованный спортивный программист планеты Геннадий Короткевич (tourist). Он много раз побеждал на международных и всероссийских чемпионатах и турнирах по спортивному программированию, в том числе организованных крупными компаниями: Google, IBM, Facebook, «ВКонтакте», «Яндекс» и Mail.ru Group. А с недавних пор Геннадий Короткевич начал и сам тренировать новое поколение программистов.
Как определяются лучшие программисты планеты
Лучшие из лучших по итогам многоступенчатого отбора проходят в финал чемпионата ICPC, который каждый раз проходит в разных городах. До 1999 года финалы проводились США, однако с тех пор география значительно расширилась. Финальные этапы ICPC уже принимали Нидерланды, Португалия, Канада, Швеция, Япония, Чехия, Марокко и Китай.
В этом году решающий турнир крупнейшего мирового чемпионата по программированию впервые состоится в Москве. Соревнование организует Московский физико-технический институт.
Два раза они проходили в России ― в Петербурге и Екатеринбурге.
В чемпионате могут участвовать команды из трех студентов, прошедших не более восьми семестров очного обучения.
Задача команд ― за 5 часов решить 12 задач разной сложности. В их основе лежат реальные проблемы, например, оптимизация расписаний метрополитена, моделирование управления воздушным движением, оптимизация размещения ограждений, отслеживание движений роботов, составление гоночных трасс, моделирование сбора багажа в аэропорту, оценка запасов нефти и газа и другие.
Прочитав сценарий, участники должны точно определить основную существующую проблему и разработать алгоритмы ее решения. За неверную попытку начисляется штрафное время. Побеждает команда, которая быстрее остальных решит наибольшее количество задач.
Такой формат соревнований считается одним из наиболее удачных и сложных: от участников требуется не только правильно решить задачи и в совершенстве знать алгоритмы, но также грамотно распределять роли в команде и выработать свою стратегию.
Правила
Николай Будин, магистрант ИТМО, член сборной, которая представит университет в финале ICPC в Москве
«Конечно, задачи нужно стараться сдавать как можно быстрее. Поэтому в начале контеста мы делим их на три примерно равных части и каждый читает свою часть в поисках простых задач. Потом, где-нибудь на втором часу контеста, уже каждый читает все оставшиеся задачи, чтобы можно было думать над теми, которые больше нравятся. Ну и, безусловно, задачи бывают на разные темы. Поэтому мы также выбираем, кто лучше и быстрее сможет решить задачу на конкретную тему».
Долгие годы участникам давался лишь один компьютер на команду. Однако в этот раз финал пройдет по другим правилам.
«Теперь на некоторых олимпиадах команде разрешается использовать три компьютера — по одному на каждого участника. Как правило, в таком формате проводятся олимпиады, которые проходят онлайн, потому что в таком случае было бы практически невозможно проконтролировать выполнение правила про один компьютер. Но некоторые очные олимпиады тоже теперь проводятся по таким правилам. Например, как раз предстоящий финал. Так что и здесь коронавирус внес свои коррективы».
Официальные языки программирования ICPC: C/C++, Kotlin, Java и Python. Это значит, что участники могут выбрать любой из них для написания собственного кода.
«На самом деле задачу можно написать на любом языке, выбор практически не влияет на сложность. Но проблема в том, что некоторые языки работают быстрее, некоторые медленнее, а в задаче одинаковое ограничение по времени выполнения для всех языков. Поэтому обычно все пишут на C++, потому что он самый быстрый. Изредка, если в задаче скорость работы совсем не важна, мы что-то пишем на Python. Кроме того, на Python код получается чуть проще», ―
Николай Будин.
Николай Будин.
А еще во время соревнований командам дают воздушные шарики ― по одному за каждую успешно сданную задачу. Это еще одна давняя традиция ICPC.
Как определяются победители
Следить за победителями можно не только по количеству воздушых шаров рядом со столами команд. На протяжении всего соревнования ведется турнирная таблица, которая показывает расстановку сил в реальном времени. Но будьте уверены, абсолютного чемпиона вам, скорее всего, не удастся угадать вплоть до церемонии награждения ― за час до конца турнира таблица «замораживается» и именно в это время начинается особенно напряженная борьба. Лидер может поменяться в считанные минуты, поэтому следить за финалом ICPC ― это такой же драйв, как и смотреть серию послематчевых пенальти в финале Евро-2020.
В этом году следить за трансляцией финала, который пройдет 5 октября, можно на YouTube и на Twitch (русский, английский). А до финала можно посетить открытую программу: 1 и 2 октября в «Манеже» пройдут лекции с представителями российских и зарубежных компаний («Мегафон», Райффайзенбанк, «Тинькофф», 1С, «Яндекс», JetBrains, Shutterstock), а также встречи с выпускниками ICPC. На мероприятиях можно будет узнать о том, как прокачать soft skills, построить успешную карьеру, а также запустить собственные проекты в бизнесе и науке. Следить за новостями и событиями финала можно здесь (на английском) и здесь (на русском).
Команда-победитель определяется по числу решенных задач. При их одинаковом количестве побеждает команда, потратившая меньше времени. Окончательное решение выносит судейская комиссия.
Но в отличие от большинства спортивных соревнований, призовые места в ICPC распределяются по-другому. Команды, занявшие в финале первые четыре места, получают золотые медали. Места с пятого по восьмое награждаются серебряными медалями, а с девятого по двенадцатое ― бронзовыми. Студенты, занявшие первое место, объявляются абсолютными чемпионами и получают кубок.
Но в отличие от большинства спортивных соревнований, призовые места в ICPC распределяются по-другому. Команды, занявшие в финале первые четыре места, получают золотые медали. Места с пятого по восьмое награждаются серебряными медалями, а с девятого по двенадцатое ― бронзовыми. Студенты, занявшие первое место, объявляются абсолютными чемпионами и получают кубок.
Что дает победа на соревнованиях
За победителями и медалистами ICPC охотятся ведущие мировые IT-компании, ведь лучшие спортивные программисты планеты ― именно те, кто сможет решать нетривиальные задачи и искать новые подходы.
Тысячи участников соревнований сегодня работают в индустрии. Всего, по данным ICPC Foundation, они заняты в работе более 1500 международных компаний. Свыше 500 выпускников работают на позициях CEO, более 20 тысяч являются инженерами, а также разработчиками программного обеспечения. Активно сообщество ICPC и в академической сфере: свыше 2 000 экс-участников турниров являются профессорами в университетах.
При этом сфера деятельности выпускников не ограничивается только IT. Они работают в абсолютно разных областях, в том числе в консалтинге, финансовой сфере, банкинге и других. Всего же, как подсчитали в ICPC Foundation, комьюнити крупнейшего студенческого чемпионата по программированию насчитывает более 300 тысяч участников.
Над проектом работали:
Текст: Елена Меньшикова
Оформление: Екатерина Шевырёва
Фото и видео: ICPC.Global, ICPCNews, NERCNews, giphy.com, Университет ИТМО
Текст: Елена Меньшикова
Оформление: Екатерина Шевырёва
Фото и видео: ICPC.Global, ICPCNews, NERCNews, giphy.com, Университет ИТМО
