О код, ты — мир: что такое спортивное программирование и при чём тут спорт

В одном из выпусков подкаста «Люди и код» мы поговорили с Ильёй Кучумовым, который на протяжении семи лет участвовал в различных соревнованиях по спортивному программированию и побеждал в них. Илья рассказал, что это за спорт такой, и поделился собственными наблюдениями о подготовке, тактике и психологии соревнований.

Илья Кучумов

Руководитель отдела разработки поиска по товарам в «Яндексе». Во время обучения в университете стажировался в одном из европейских офисов Google.

В 2018 году занял второе место в финале Google Hash Code, а в 2017-м — 14-е место в финале ICPC. Является автором двух задач для финального раунда Yandex Cup 2022 в дисциплине «Алгоритм».

Что такое спортивное программирование и какие существуют соревнования

Суть спортивного программирования заключается в том, что участникам нужно за ограниченное время решить несколько сложных алгоритмических задач. В описании каждой задачи определён формат входных и выходных данных, а также приведены примеры и соответствующие им результаты. Участникам предоставляют компьютеры: один на команду или по одному на каждого участника — в зависимости от условий.

При этом недостаточно написать код, который будет выдавать верный результат. Программа должна быть достаточно быстрой, то есть находить решения с разными входными данными за отведённое в условии время (например, за 1 секунду) и не потреблять объём памяти выше заданного значения (например, 256 МБ).

Как правило, очевидные решения, которые приводят к правильному результату, оказываются слишком медленными или «тяжёлыми», поэтому приходится разрабатывать более эффективные алгоритмы.

Можно выделить три вида соревнований.

Командные. Обычно проводятся среди студентов. Группы по три человека в течение пяти часов решают алгоритмические задачи, которые предполагают наличие точного решения. На команду выдаётся по одному компьютеру. Количество задач — от 8 до 12. Кто решил больше, тот и выигрывает.

Самый популярный чемпионат этого формата — ICPC (International Collegiate Competitive Contest). Соревнование состоит из четырёх, иногда из пяти этапов. Финал проводится в разных странах, среди которых США, Португалия, Индонезия, Бангладеш и другие. Ежегодно в ICPC участвует около 1300 студентов.

Индивидуальные. Это довольно суровые баталии, как правило, без ограничений по возрасту, поэтому на них можно встретить ветеранов с 15–20-летним стажем. Победить или хотя бы пройти в финал невероятно сложно.

Самые известные и престижные индивидуальные состязания — Topcoder Open, AtCoder и Google Code Jam (прекращено в 2023 году). Есть и локальные российские события вроде Yandex Cup.

Оптимизационные. В последнее время популярность набирает формат задач, не предполагающих наличия строгого решения. В таких соревнованиях побеждает тот, кто нашёл оптимальный алгоритм. При этом почти всегда решение можно «докрутить», чтобы сделать его ещё более эффективным.

Оптимизационные задачи решают на Topcoder Open Marathon и Google Hash Code.

Также появляются новые форматы, связанные с машинным обучением, но они не относятся к классическому спортивному программированию.

Читайте также:

Спортивное программирование: зло и хорошая школа

Тактика и роли в команде

Слово «спорт» в нашем деле появилось не случайно, ибо здесь, как и в баскетболе, хоккее и других командных играх, важны подготовка и тактика. Нужно эффективно использовать время и сильные стороны членов команды, а также достичь высокой степени сыгранности. В связи с этим возникают разные требования к командному составу: нельзя просто взять и набрать трёх сильных программистов — у каждого должна быть специализация.

Например, один участник, отлично знающий язык программирования, может отвечать за программную реализацию алгоритма. Другой — быть спецом в узкой теме вроде линейной алгебры или вычислительной геометрии, а третий — выполнять роль этакого универсального солдата, способного выстроить «мостик» между тиммейтами.

В условиях ограниченного времени важно определить, какие задачи брать в работу в первую очередь, какие — во вторую, а какие вовсе лучше выбросить. Поэтому в любой хорошей команде должен быть лидер, за которым остаётся последнее слово в таких вопросах. Хотя, конечно, почти всегда это решается сообща.

Если говорить о тактике в спортивном программировании, то по большому счёту она связана с тем, как обсуждать задачи, кому и в каком порядке их решать, когда бросать и когда возвращаться.

Часто на соревнованиях выдаётся один компьютер на команду, поэтому если кто-то отлаживает программу, то другую в этот момент писать нельзя. Так что тестирование — один из важнейших элементов тактики.

Выбор конкретной модели поведения зависит от вида соревнований и ваших возможностей. На сложных и ответственных играх, таких как финал чемпионата мира, где даётся только одна попытка, чаще всего придерживаются консервативной тактики. Не нужно пытаться решить задачу в одиночку, рисковать и принимать опрометчивые решения.

Даёт ли язык программирования преимущество

Это зависит от соревнований.

Например, на Codeforces вводятся отдельные ограничения по времени для скриптовых языков, таких как Python. И если решение на C++ должно срабатывать не более чем за две секунды, то на Python — не более чем за пять. Поэтому на таких соревнованиях язык большой роли не играет.

На соревнованиях вроде ICPC или Topcoder Open картина немного иная. Набор языков там гораздо уже. Например, на ICPC это C++, Java, Python и, вы удивитесь, Ada. Никаких «поблажек» для скриптовых языков там нет: одинаковое ограничение по времени и для C++, и для Java, и для Python. Поэтому выбор языка здесь очень важен.

Обычно выбирают между C++ и Java. При этом жюри гарантирует, что решение, которое укладывается в заданные ограничения, существует как для C++, так и для Java, которая по умолчанию более медленная. Но, положа руку на сердце, у команды с «плюсами» часто больше шансов пройти по времени: иной раз даже более-менее простые решения со сложностью О (n^2) укладываются в 1,95 секунды. И это, конечно, важное преимущество.

Тогда почему некоторые всё-таки выбирают Java? Банально потому, что в Java легче отлавливать баги: чуть что — язык тут же расскажет и покажет, что и где пошло не так, и это намного приятнее, чем словить undefined behavior и полчаса его дебажить.

Как отбросить неверное решение

Иногда мы влюбляемся в собственные идеи и долго не можем от них отказаться. В спортивном программировании это может стать большой проблемой. Подобно лудоманам, вы рискуете попасть в ловушку азарта и думать, будто, просидев за задачей ещё пять минут, уж точно найдёте решение. А часы продолжают предательски тикать, оставляя всё меньше времени на остальные задачи…

Принять решение помогает таблица результатов, в которой видно, сколько команд решили ту или иную задачу. Если вы бьётесь над как бы очевидной задачей, которую «вот-вот решите», а все команды ловят за неё прочерки, то это явный сигнал, что надо бросать.

Гораздо сложнее, когда все задачу сдают, а вы нет. В таком случае полезно отложить её на время, например на час, и переключиться на что-то другое. Или устроить перезагрузку: отбросить всё, что нарешали, и начать сначала. Также иногда помогает «брутфорс» с помощью генератора случайных тестов, о котором я писал выше.

Нерешаемые или очень сложные задачи в спортивном программировании в шутку называют «гробами». Важно как можно раньше их распознать, чтобы отложить напоследок или вовсе отбросить и не тратить время впустую. Здесь хорошо помогает опыт, интуиция и наблюдение за другими участниками: если никто задачу не сдаёт, значит, скорее всего, это «гроб».

С другой стороны, далеко не всегда стоит следовать за толпой — даже если это толпа программистов-олимпиадников. Бывает, что несколько команд не могут сдать задачу просто потому, что что-то упустили, а остальные пугаются и отбрасывают её. Потом эта же задача встречается на локальном соревновании, какая-нибудь команда её решает в первый час, и за ней находят решение другие. Мнение толпы иногда сильно влияет на результат.

Один из примеров «гробов» — геометрия, в частности с трёхмерным пространством, с математическими моделями, подход к которым непонятен.

Как готовиться к соревнованиям

Решать, решать и ещё раз решать! Чем больше задач разберёте, тем выше вероятность, что на соревнованиях попадётся что-то знакомое или даже аналогичное («баян», другими словами). Мы использовали архивы уральского чемпионата на acm.timus.ru. К концу олимпиадной карьеры у всех в личном зачёте было примерно по тысяче задач.

Но решать задачи в «тепличных условиях» — это всё равно что готовиться к чемпионату мира по футболу, играя только с товарищами по команде. Нужно постоянно мериться силами с соперниками, чтобы понимать свой реальный уровень подготовки. Для этого есть несколько инструментов.

Виртуальные соревнования. Всё, чему вы научились на первом этапе, нужно отработать в стрессовых условиях ограниченного времени. Для этого на площадках вроде Codeforces и Opentrains есть виртуальный режим, который позволяет участвовать в соревновании так, будто с вами в реальном времени соревнуются другие команды. Результаты отображаются в таблице, и исход игры заранее неизвестен.

Во время активной подготовки мы играли в таком режиме два-три раза в неделю. Далее приступали к разбору нерешённых задач: изучали решение на сайте и попутно необходимую теорию. Всё это занимало более 30 часов в неделю, как настоящая работа на фултайме.

Загородные сборы. Это отличная возможность помериться силами с реальными соперниками и порешать задачи, которых ещё ни разу не было на соревнованиях. Сборы проводятся в Москве, Петрозаводске, Ижевске и других городах и длятся одну-две недели.

Локальные соревнования. Участвуйте в местных чемпионатах, которые проходят в Екатеринбурге, Новосибирске, Москве, Санкт-Петербурге и других региональных центрах России. Регулярное участие повышает стрессоустойчивость и адаптивность к смене локаций и позволяет подходить к более глобальным соревнованиям, таким как финал ICPC, менее восприимчивым к раздражителям, которых там в изобилии.

Я бы рекомендовал отталкиваться от задач: сначала попытаться что-то решить, а потом изучить соответствующую теорию. Не существует волшебной книги, по которой можно подготовиться, как готовятся к экзамену в университете.

Какие есть плюсы, минусы и подводные камни

Спортивное программирование развивает навык решать алгоритмические задачи любой сложности. Многие задачи перестают казаться хоть сколько-нибудь сложными, и это даёт вам преимущество на технических интервью, особенно в крупных IT-компаниях, где алгоритмам уделяется много внимания.

Есть и менее очевидные вещи, которые также важны.

✅ Во-первых, на соревнованиях прививается «алгоритмический подход» к решению задач:

• сформулировать задачу,
• понять её;
• определить «корнер-кейсы» и ограничения;
• расписать решение в общем виде.

Другими словами, это способ решать задачи без паники и распыления фокуса. К нему довольно быстро привыкаешь — и начинаешь использовать даже в процессе проектирования крупных систем.

✅ Во-вторых, спортивное программирование прокачивает навык работы в стрессовых ситуациях, когда нет права на ошибку.

Стандартная ситуация на олимпиаде: до окончания 15 минут, при одном из тестов программа выдаёт неверный результат, и в таком стрессе, под огромным давлением нужно успокоиться и сконцентрироваться. С опытом учишься отбрасывать эмоции и продолжать думать ровно до тех пор, пока соревнование не закончится.

✅ В-третьих, соревнования учат работать в команде со сложными, но талантливыми людьми. Особенно это касается серьёзных соревнований, когда вы попадаете в топ-100 в мире или в топ-10 по России в командном зачёте. На этом уровне остаются очень талантливые ребята, у которых высокое (что справедливо) мнение о себе. Эти люди способны решить практически любую техническую задачу, хоть и не все обладают сильными софт-скиллами.

Теперь о недостатках. Их почти нет.

❌ Низкое качество кода. Нужно признать, что с точки зрения продакшена качество олимпиадного кода оставляет желать лучшего. С другой стороны, олимпиадные программы и не нужно поддерживать.

Код — это инструмент, с помощью которого люди решают задачи. Если вы разрабатываете сервис, над которым работают десятки и сотни инженеров, то да, качество выходит на первый план. Но на олимпиаде, в условиях ограниченного времени, когда нужно решить 8–12 задач за пять часов, важно лишь получить работающее решение (иногда это актуально и в профессиональной разработке).

Я нанимал много ребят с олимпиадным прошлым и могу точно сказать: если понятно и аргументированно объяснить джуну, почему надо соблюдать код-стайл, проблем не возникнет. В то же время умение быстро написать работающий «одноразовый» код для проверки гипотезы высоко ценится.

❌ Игра (не) стоит свеч. Многие плюсы, которые я перечислил выше, появляются, когда вы добрались до топ-100 — топ-200 в мировом командном зачёте. Но вот вопрос: а зачем стремиться дальше и выше? Зачем пытаться занять пьедестал?

Кажется, что, кроме подпитки ЧСВ и нескольких тысяч долларов, это не даёт практически ничего. Зато у среднего олимпиадника, который, помимо алгоритмов, силён в смежных дисциплинах, в том же ML, куда больше карьерных возможностей.

Есть ли в спортивном программировании свои звёзды

Пожалуй, самая крупная звезда — белорусский программист Геннадий Короткевич (выступает под ником tourist). В 2020 году он занимал первое место в рейтингах Topcoder и Codeforces.

Ещё одна знаменитость — Пётр Митричев. Он также одержал победу в невообразимом количестве соревнований.

Среди стран, если считать по общему количеству побед в индивидуальных, студенческих и школьных соревнованиях, лидируют Польша, Россия, Беларусь, Китай, Япония и США. Особенно в последнее время выросла российская команда: за 15 лет мы выиграли около 10 мировых чемпионатов.

Итого

В этой статье мы обсудили классическое спортивное программирование, но прогресс не стоит на месте и понятие «классика» весьма эфемерно. Организаторы чемпионатов следят за трендами и постоянно экспериментируют с направлениями и форматами.

Выше я уже упомянул оптимизационные задачи, приближенные к тем, что каждый день решают инженеры в BigTech-компаниях вроде «Яндекса», Amazon и Netflix. Недавно Google устраивал соревнования по программированию распределённых систем, задачи на которых по условиям напоминают реальные. И конечно, куда без соревнований по машинному обучению, которые уже регулярно проводятся в разных странах.

Уверен, через 5–10 лет спортивное программирование изменится до неузнаваемости. Может быть, промпт-инжиниринг станет одной из флагманских дисциплин и мы напишем новую статью о «классическом» спортивном программировании.