Умом нужно выделяться. Чемпионат мира, который выигрывает Россия

April 27, 2018
24 апреля 2018 г.

Как устроен большой спорт программистов? Куда они идут работать после побед?
На прошлой неделе в Пекине закончился 42-й ежегодный студенческий чемпионат мира по спортивному программированию под эгидой и по правилам ACM (Association for Computing Machinery – это старейшая, созданная в 1947 году, ассоциация ученых, исследователей и практиков в сфере ИТ). Чемпионами мира стали ребята из МГУ, они единственные за отведенное время успешно решили девять задач из 11 предложенных жюри. По восемь задач решили студенты МФТИ, а также университетов Пекина и Токио; по семь – еще девять команд, в том числе две российских (СПбИТМО и УрФУ), две китайских, две американских (включая и легендарный MIT). Всего в соревнованиях в Пекине принимали участие команды из 140 университетов со всех континентов. Из последних 19 чемпионатов (с 2000 года) российские команды выиграли 13, а СПбИТМО – семикратные чемпионы мира – официально является самым титулованным в мире. Прошлогодний чемпионат (он проходил в США, в Рэпид-Сити) выиграли тоже они, но в этом году остались лишь девятыми.

Что это за соревнования такие, в чем их смысл и престижность и почему успехами российских спортивных программистов стоит гордиться?

Правила игры
С 1977 года в правилах чемпионатов удивительным образом изменилось не так уж и много. Три студента (только один из них может быть старшекурсником, двое других – не старше бакалавриата; кроме того, участвовать в финале чемпионата мира каждый конкретный человек может не более двух раз), пять часов, один компьютер, несколько (раньше 6–8, в последние годы – 10–12) алгоритмических задач со строго поставленными условиями. Решением является программа на любом из нескольких допустимых языков программирования, проверка решений носит автоматизированный характер: жюри запускает программу, написанную участниками, на определенном наборе заранее заготовленных тестов, одинаковых для всех участников, и засчитывает решение только в том случае, если программа выдаст правильный ответ на всех тестах (а вот как именно она это сделает – никого не волнует; у задачи вполне может быть несколько совершенно разных правильных решений). Хотя бы одна ошибка – решение не засчитывается; команда может исправить его и послать на проверку снова, но каждая неудачная попытка обойдется в 20 штрафных минут, почти как в биатлоне. Таблица результатов доступна всем участникам и зрителям в режиме реального времени (что придает состязанию азарта и зрелищности), кто больше решил задач – тот и победил, а при равенстве выше в таблице оказывается команда, нахватавшая меньше штрафа.

Чтобы побеждать ⁠в соревнованиях по правилам ACM, мало просто хорошо решать ⁠сложные задачи (хотя это, конечно, необходимо); это серьезный спорт, требующий ⁠железных нервов, правильного распределения сил по дистанции ⁠соревнования, выработки ⁠оптимальной стратегии. Три человека, один ⁠компьютер: кто продумывает решение «на бумажке», а кто ⁠садится вбивать сразу «из головы»? Все конкуренты, судя по таблице, успешно сдают задачу F, а у нас нет для нее решения: штурмуем ее, бросив всё, или откладываем на последний час, в надежде, что свежий взгляд поможет подобрать к ней ключи? Жюри не зачло задачу, в правильности решения которой мы уверены: попробовать немного поменять параметры алгоритма, чтобы «протолкнуть» наше решение за несколько попыток, пусть и ценой большого штрафа – или отсадить одного из участников команды внимательно перепроверять решение, а то и переписывать его целиком? Часы тикают, конкуренты уходят вперед, в большом зале постоянно раздаются радостные возгласы (еще у кого-то «зашло» решение), на бумажке много заготовок, и в принципе понятно, как решать, но отладить программы так, чтобы они проходили собственные тесты, никак не получается… Вася хватается за голову; его озарило, он понял, что не рассмотрел один важный крайний случай, и поэтому его решение «валится» на четырнадцатом тесте, ему надо срочно за компьютер, чтобы исправить ошибку – но клавиатура занята, Петя дописывает кропотливый и сложный расчет траектории полета мяча для своей задачи, если отвлечь его – наделает ошибок. Тренеры на гостевой трибуне пьют валидол – на кону самый престижный титул в студенческом интеллектуальном спорте, в подготовку вбуханы 3–4 года тяжелой работы с почти ежедневными пятичасовыми тренировками, но опять все решится в последние пять минут (три из четырех команд, занявших первые места в финале-2018, успешно сдали свои последние задачи на 296–298 минутах турнира; вид турнирной таблицы за пять минут до конца состязания кардинально отличался от итогового).

Большой спорт
Короче говоря, соревнования ACM ICPC – это высококонкурентный вид интеллектуального спорта, в котором участвуют сотни тысяч студентов (математиков и программистов) со всего мира. Неудивительно, что к этим соревнованиям приковано столько внимания, в списке спонсоров – названия ведущих мировых ИТ-компаний, а денежные призы сравнимы с призами на приличных шахматных турнирах. И важны не только денежные призы: если не любой финалист, то уж точно любой призер финала чемпионата мира по программированию вправе рассчитывать на приглашение в топовую компанию – по крайней мере на стажировку. Мало какой другой карьерный лифт имеет так мало остановок между университетом (даже не обязательно столичным) в Китае или в России и Кремниевой долиной.

Приглашение на стажировку, конечно, не равно автоматически дому в Маунтин-Вью и контракту на несколько сот тысяч долларов в год. Далеко не все спортсмены-программисты становятся просто хорошими программистами; не секрет, что для решения алгоритмических задач на скорость и для работы над профессиональными высоконагруженными ИТ-системами нужны разные качества. Но, во-первых, соревнования по правилам ACM ICPC выявляют не только умение решать задачи, но и способность к командной работе и психологическую устойчивость. А, во-вторых, стабильно высокие результаты университета неизбежно означают наличие в нем серьезной школы, фундаментальной и качественной подготовки в области теоретической информатики – основы современной ИТ-индустрии.

Ведь совершенно не имеет значения, чем занимаются сто тысяч человек (а общее количество студентов, принимающих участие в сетке отборочных соревнований на том или ином уровне, давно уже перевалило за эту отметку) – будь то керлинг, плевки в длину или сборка-разборка автомата Калашникова – лучшие из них на самом деле очень хороши в своем деле. Высота спортивной пирамиды полностью определяется широтой ее основания; стать лучшим из ста тысяч на порядок сложнее, чем стать лучшим из десяти тысяч.

А пирамида действительно огромная; ранней осенью начинаются внутривузовские отборочные соревнования в тысячах университетов по всему миру; лучшие команды в октябре-ноябре собираются в четвертьфинальных отборочных раундах (до этой стадии доходят 8–10 тысяч команд-участниц). Это уже очень серьезный уровень и серьезная конкуренция; для многих региональных вузов попадание в группу лидеров в четвертьфинале – предмет большой гордости. Зима – время полуфиналов; весь мир поделен примерно на десяток полуфинальных отборочных зон, каждая из которых имеет свою квоту мест в финале, соответствующую успехам команд полуфинального подрегиона на прошлом мировом первенстве – это очень похоже на то, как формируются списки участников Чемпионата мира по футболу. «Наш» полуфинал называется NEERC – «северо-евразиатский региональный турнир», в нем участвует около 300 команд из всех стран бывшего СССР, кроме Украины и Молдовы (но включая Прибалтику); Украина состязается в европейской полуфинальной зоне, с событиями последних лет это никак не связано – как-то так исторически сложилось. Благодаря успехам наших команд в финалах, у NEERC самая большая квота в финале – 15–17 мест; их занимают, конечно, не только российские команды: в этом году на финал через NEERC отобрались университеты Вильнюса, Тарту, Риги, Казахско-Британский университет (Алма-Ата) и стабильно очень сильный Белорусский государственный университет. Ни разу за последние два десятилетия не пропускали финалов команды СПбИТМО, СПбГУ и МГУ. Из региональных вузов чаще всего в финал пробивался Уральский университет (УрГУ, потом УрФУ), постоянные участники финалов – команды Новосибирского, Пермского, Саратовского госуниверситетов, Ижевского технического университета.

Двадцать лет назад, когда я был студентом и занимался спортивным программированием, это было веселым хобби. Перед ответственными стартами – две-три тренировки в неделю, в остальное время – решение отдельных задач в качестве развлечения; этого уже могло быть достаточно, чтобы выступать на неплохом уровне. Те времена давно ушли; сейчас, чтобы показывать конкурентоспособные результаты, необходимо следовать тщательно выстроенному тренировочному процессу, включающему в себя практически ежедневные тренировки, подготовительные сборы, доведение до автоматизма многих технических аспектов решения задач. Большой спорт – с его плюсами и минусами. Хорошо это или плохо – спор, который никогда, наверное, не закончится.

Как использовать спортивных программистов
Еще одному спору столько же лет, сколько и спортивному программированию: так все же получаются ли из спортивных программистов хорошие «промышленные» программисты? Часто от руководителей ИТ-компаний приходится слышать: «звезды» чемпионатов ACM – это капризные гении, не способные к работе в качестве винтика в большой команде, в строго выстроенном технологическом процессе. Полагаю, все же, что дело, как обычно, в том, чтобы «уметь их готовить». Николай Дуров, чемпион мира 2000 и 2001 года в составе команды СПбГУ, старший брат своего младшего брата и ведущий разработчик сначала «Вконтакте», а потом Telegram, вместе с Андреем Лопатиным, своим напарником по команде – это, конечно, самые яркие и известные в России примеры того, на что способны лучшие спортивные программисты, если им дают развернуться и показать себя.

Никита Шамгунов, мой друг и напарник по команде УрГУ, построил, после многих лет работы в Microsoft и Facebook, успешную технологическую компанию MemSQL, – она производит суперскоростной движок для обработки данных, – и у него одно время работали сразу трое или четверо из мирового топ-10 спортивных программистов. Потому что задачи были соответствующие: алгоритмические и очень сложные. Наверное, если посадить спортивного программиста за проводки в 1С, результат будет разочаровывающим…

Ну и последний вопрос, который возникает у всех, кто сталкивается с миром спортивного программирования: «Ну так они же все уедут?». Нет, совсем не факт. Для программиста современный мир глобален и лишен границ. Для языков программирования нет лингвистических барьеров. Так что победитель чемпионата мира по программированию не уедет просто так – он поедет туда, где будет больше возможностей для самореализации. А уж где их будет больше – зависит не от него.

*Автор – бронзовый призер чемпионата мира по программированию 2001 года в составе команды УрГУ

Источник