Спорт для разработчиков: как устроено олимпиадное программирование
Спортивное программирование часто ассоциируется у людей с профессиональными командами, которые занимаются им со средней школы (или даже с начальной, как самый титулованный спортивный программист мира Геннадий Короткевич) и тратят на подготовку большую часть своего времени. Однако в соревнованиях участвует множество разработчиков с разным уровнем подготовки и с разной мотивацией: многие хотят научиться быстро писать рабочий код, углубить знания в области алгоритмов или добавить олимпиадный опыт в своё резюме. Академия Яндекса поговорила с участниками олимпиад и с Сергеем Чернышёвым — руководителем управления по работе с талантами Яндекса, финалистом ICPC 2002 года, о том, как начать заниматься спортивным программированием и зачем это делать.
Как устроены соревнования по программированию
Задача участников соревнований — решить как можно больше предложенных задач за ограниченное время. Соревнования бывают как индивидуальными, так и командными. Они состоят из нескольких этапов (например, отборочный тур, полуфинал и финал) и проводятся отдельно для школьников, студентов и выпускников вузов.
Одна из самых известных таких олимпиад — Международная студенческая олимпиада по программированию (ICPC). Она впервые состоялась в 1977 году в рамках конференции АСМ и с тех пор проводится каждый год. Последние восемь лет подряд выигрывают студенты российских университетов — МГУ, СПбГУ и ИТМО.
В ICPC могут участвовать студенты вузов или аспиранты первого года обучения не старше 24 лет. Это групповое соревнование, в котором участвуют команды из трёх человек.
Тур олимпиады проходит следующим образом: каждой команде выдаётся ноутбук и от восьми до двенадцати задач (их условия написаны на английском языке), которые нужно выполнить за пять часов. Участники пишут решения на языках программирования C, C++, Java, Python или Kotlin, компилируют и посылают их на тестирующий сервер.
При этом частичные решения не учитываются, а побеждает команда, правильно решившая наибольшее число задач.
Зачем участвовать в командных соревнованиях
«Олимпиадное программирование как большой спорт, и для того, чтобы занимать первые места на чемпионатах, нужно уделять подготовке почти всё своё время», — рассказывает Сергей Чернышёв, который сейчас занимается организацией олимпиад. У профессиональных команд есть свои тренеры (бывшие победители и призёры олимпиад и преподаватели университетов), которые отбирают перспективных студентов и готовят их к соревнованиям.
Многие участвуют в олимпиадах не ради победы. Например, студенты начинают заниматься спортивным программированием, потому что им нравится решать задачи или потому что на соревнования ездят их однокурсники. Однако из соревнований можно вынести пользу, даже если подходить к ним по-любительски. Чернышёв говорит о том, что участие в олимпиадах развивает как индивидуальные навыки и знания, так и умение работать в команде.
«По сути, ICPC — это дополнительное дистанционное обучение, которое позволяет „прокачать“ себя. Благодаря олимпиадам студенты лучше узнают, что такое динамическое программирование, строковые и другие алгоритмы — эти темы не всегда глубоко преподаются в университетах», — объясняет Сергей.
Влад Бидзиля, участник ICPC и других олимпиад по программированию, считает, что у людей, которые хотят стать сильными разработчиками, есть несколько возможных направлений развития. Первое — набираться практического опыта, изучать новые фреймворки и технологии. А второе — развивать интеллект, занимаясь фундаментальными задачами (например, участвуя в олимпиадах). Опыт участия в соревнованиях помогает быстрее осваивать новые области. Этот опыт пригодился и в учёбе на ФКН НИУ ВШЭ и в ШАДе, и в работе в Яндексе: Влад говорит, что он везде замечал похожие паттерны.
Кроме того, олимпиады учат писать код без багов. «В контестах встречаются запутанные логические конструкции, которые редко возникают на практике», — поясняет Бидзиля. — В работе код обычно разделен: есть отдельные компоненты с понятными связями между собой. Поэтому если человек научился работать со сложной логикой, то в промышленной разработке он уже вряд ли допустит ошибки».
Как подготовиться и что делать во время соревнования
«Для того, чтобы начать участвовать в соревнованиях, ничего не нужно — только желание и умение программировать на каком-нибудь языке», — убеждает Сергей Чернышёв. А начать подготовку можно с решения задач на таких сайтах, как Codeforces, Topcoder и CodeChef.
Участник ICPC этого года Саша Минаков говорит: «Чтобы оказаться хотя бы в середине рейтинга участников, нужно знать популярные алгоритмические методы, типичные нелинейные структуры данных и графы». А профессиональные команды отличает знание специфичных алгоритмов, которые появляются в задачах олимпиад раз в несколько лет.
Ресурсы для подготовки:
— Томас Кормен и др. Алгоритмы: построение и анализ
— Архив заданий ICPC для Северной Евразии
— Сборник задач для подготовки к школьным олимпиадам
Для участия в соревнованиях важно собрать грамотную команду и организовать её работу. Нередко в группах появляются «лидеры», которые сильнее всего мотивированы и сдают наибольшее количество задач за тур. «Однако только за счёт этого сложно достичь высоких результатов, потому что за несколько часов работы этот человек выдыхается и начинает совершать ошибки», — отмечает Чернышёв.
Хорошие команды — те, в которых все три участника постоянно сдают задачи и сменяют друг друга: пока один решает задачу, другой сидит за компьютером. Раньше бытовал стереотип, что в команде должны быть математик, программист и специалист по алгоритмам, но сейчас он неактуален, так как изменился формат соревнования и задачи стали более прикладными.
Во время тура нельзя терять концентрацию: на ICPC нужно решить до двенадцати задач за пять часов, и времени переделывать их нет. При этом на соревнованиях необязательно писать «чистый» код: он используется один раз, а жюри оценивает только итоговый результат. В случае с промышленным программированием, наоборот, важно сделать так, чтобы код было легко читать и поддерживать другим разработчикам.
Как изменялось спортивное программирование и что его ждёт
«За последние годы спортивное программирование стало более прикладным», — убеждён Сергей Чернышёв. Это связано с повышением культуры программирования: раньше в российских школах изучали Pascal, и задачи решали тоже на нём. Со временем у людей в олимпиадном сообществе появился опыт использования библиотек Java и C++ и различных структур данных. На их базе придумывали более сложные структуры для спортивного программирования, и за счёт этого прикладная и олимпиадная разработки сблизились. К тому же компьютеры стали работать быстрее, и ограничения по времени выполнения задач (на ICPC это обычно одна, две или три секунды) отошли на второй план. Ключевую роль в задачах стали играть аспекты реализации.
Чернышёв рассказывает, что олимпиадное движение развилось в России примерно на десятилетие раньше, чем хакатоны, которые набрали популярность после 2010 года. Организатор олимпиад говорит о том, что нынешним студентам будет полезно принять участие как в тех, так и в других соревнованиях. Хакатоны пригодятся тем, кто хочет развить продуктовое мышление или реализовать свою идею: они мало влияют на сам навык разработки. А спортивное программирование подойдёт как раз для того, чтобы углубить знания.
В будущем Сергею хотелось бы повысить престиж участия в олимпиадах по программированию. По его словам, сейчас для этого не хватает чёткой мотивации участвовать, нет, например, денежных призов или привилегий при приёме на работу. Чернышёв сравнивает студенческие олимпиады с Всероссийской олимпиадой школьников, где призёры и победители заключительного этапа гарантированно получают значимый приз — поступление в любой вуз России на соответствующее направление.
Мне кажется, что количество переходит в качество, поэтому если спортивное программирование будет популярным, то в нём автоматически будут очень сильные игроки.