DataArt давно дружит с командой ИТМО по спортивному программированию и помогает ей. Этим летом в гости в наш петербургский центр разработки пришли Илья Збань, Иван Белоногов и Владимир Смыкалов. Чемпионы мира 2017 года рассказали о том, как именно программисты соревнуются между собой, о тренировочных сборах, любимых задачах и сильнейших соперниках.
Олимпиада по программированию
Главное соревнование программистов — международная студенческая олимпиада под эгидой ACM (ACM-ICPC, или просто ICPC) — проходит с 1970-х, а в виде, близком к сегодняшнему, оформилась в 1989 году. Олимпиада предназначена для студентов и аспирантов, за редким исключением к соревнованиям не допускают программистов старше 24-х лет. К тому же, испытывать силы в финале можно только дважды, а в региональных отборах разрешается участвовать всего пять раз. На ранних этапах, проходящих по всему миру, соревнуются тысячи команд. Около сотни лучших доходят до финала.
Основные правила
Команды состоят из трех человек, при этом в распоряжении каждой команды — только один компьютер. Перед началом соревнования всем выдаются конверты с задачами алгоритмического или математического характера — от восьми до 13 штук — которые нужно решить за пять часов. Решение задачи — программа, считывающая текстовый запрос и выдающая текстовый ответ. Для проверки решение прогоняется примерно на сотне тестов, заранее подготовленных жюри, — верным оно признается, только если ответ получается правильным в каждом из тестов.
Правила ICPC очень доходчиво изложены в ролике, выпущенном к чемпионату Урала по программированию — одному из первичных этапов отбора на Олимпиаду. Они едины для всех регионов и с 2013 года остались без изменений.
Языки и среда
В финале 2017 года можно было использовать языки Java, C++ и Python. Впрочем, понятно, что Python в принципе не очень быстрый — жюри не гарантировало, что на нем можно будет сдать задачу. Однако оно давало гарантии, что у них есть решения, написанные на этих языках, которые проходят все тесты.
На разных соревнованиях набор языков может быть различным. Например, на онлайн-платформе Codeforces допускается около 20 языков: от C++ и Java до Haskell и Perl.
Большинство команд в финалах пишет на C++, поскольку на первый план выходит скорость. В качестве среды разработки многие команды используют VIM (в нем, например, работали Иван и Илья) или Gina (в ней работал Владимир). Те, кто все же пишет на Java, как правило пользуются средой вроде Eclipse, поскольку писать на Java без автокомплита гораздо сложнее.
В ближайшее время можно ждать изменений, поскольку финалы теперь будет спонсировать JetBrains (20 лет до конца мая 2017 года спонсором ICPC был IBM). Это значит, что на них появится и продукция спонсора: IDEA для Java и CLion для С++. Возможно, после этого команды начнут широко пользоваться отладчиками, хотя пока чаще справляются без них.
Эволюция задач
В начале 2000-х преобладали задачи на перебор с небольшими ограничениями, сейчас стало больше задач на структуры данных. При этом в мире есть несколько достаточно обособленных школ спортивного программирования: если в Польше любят идейные, часто математические, задачи, в Китае предпочитают сложные технические, где приходится писать много кода, — например, считать комбинаторику.
Цель всегда — придумать и реализовать решение, которое работает быстро. Любую задачу можно хоть как-то решить, например, написав программу, которая просто переберет все возможные варианты. Но в последние годы задачи, предполагающие написание переборов, практически не встречаются.
Существуют ограничения по времени и памяти, однако на практике проблемы с тем, что решение использует слишком много памяти, возникают нечасто. Ограничение по времени на каждый тест обычно от одной до трех секунд в зависимости от задачи — это тоже указывается в условии.
Примеры задач
Задачи бывают разными: на графы, строки, геометрию и т. д. Допустим, рассчитать кратчайший путь между городами на карте. Или построить максимально длинную взлетно-посадочную полосу на острове, представленном в виде невыпуклого многоугольника. Задачей может быть сравнение текстов — поиск наибольшей общей подстроки для пары строк.
Еще один формат — интерактивные задачи, где вам предлагают поиграть в какую-нибудь игру с системой, написанной жюри. В одном из полуфиналов нужно было написать программу, способную в 90 % случаев выигрывать у предложенного алгоритма в крестики-нолики. Задачи с прошлых финалов, включая последний, можно посмотреть здесь.
Процесс решения
В основном участники команд разбирают листы с условиями в зависимости от личных предпочтений: кто-то больше любит задачи на строки, кто-то — на геометрию. В целом индивидуальная работа здесь преобладает над командной.
Первым делом нужно придумать алгоритм решения одной из задач. Иногда автор решения обсуждает его с командой, чтобы убедиться — решение получается математически правильным. После этого автор садится писать код — двое других участников в это время продолжают думать над решениями остальных задач. Когда код написан, его можно проверить на тестовых примерах, которые обычно прилагаются к условию, и отправлять в систему для оценки. Поскольку компьютерное время ограничено (напомним, что компьютер у участников всего один), на соревнованиях всегда присутствует принтер: если решение не работает, кто-то — обычно его автор — ищет ошибки, распечатав код на бумаге.
Особенности кода
С одной стороны, люди, занимающиеся спортивным программированием, умеют писать код быстро и четко, причем в стрессовых условиях. С другой стороны, их нередко критикуют за то, что этот код содержит непонятные переменные и трудно читается. В коде, который пишется на соревнованиях, действительно нет длинных понятных названий переменных — ведь его не придется поддерживать через год. Впрочем, на высоком уровне эта проблема так остро не стоит, поскольку код все же должен быть понятен товарищам по команде.
Еще одна особенность спортивного программирования в том, что тестовой системой никак не оценивается освобождение памяти — решение работает всего несколько секунд.
Алгоритмы
Мы знаем довольно много алгоритмов, используем разные структуры данных: дерево отрезков, дерево Фенвика, декартово дерево и т. д. Иногда сбалансированное дерево поиска приходится писать самостоятельно, параллельно модифицировав его так, чтобы оно считало информацию, определенную условием задачи. Например, в языке С++ есть структура множества, которая умеет поддерживать множество чисел и, например, находить следующее. Задача же может требовать найти не следующее число, а сумму всех чисел, меньших или равных заданному. Стандартными структурами реализовать это не получится.
Приносить какие-то фрагменты коды с собой нельзя, но на чемпионате мира разрешается пользоваться так называемым team reference — распечатанным на бумаге набором алгоритмов. Хотя многое мы умеем писать с ходу, в этом году немало времени потратили на его подготовку — тестировали более сложные алгоритмы. Но в итоге записями не воспользовались вообще.
Объем кода напрямую не влияет на итоговую оценку, другое дело, что 1000 строк написать за отведенное время сложно. А придумав красивое лаконичное решение, можно уложиться всего в 10–15 минут. Именно под поиск таких изящных путей и заточены большинство условий: средний объем решения — 100-200 строк кода, хотя в некоторых случаях он может доходить до 300. В обычной жизни 300 строк не так уж много, но здесь у тебя есть всего пять часов на решение всех задач. Писать нужно быстро, а если в трех сотнях строк будет допущена ошибка — задача не пройдет, значит, все время на ее решение будет попросту потеряно. К тому же, чем длиннее код, тем труднее найти ошибку в распечатанной версии.
Другие турниры и тренировки
Денежные призы далеко не основная мотивация участников турниров. На фото: Иван Белоногов и Илья Збань — призеры VK Cup 2015 (источник — страница Ивана Белоногова). В 2017-м призером VK Cup стал третий участник чемпионской команды ИТМО Владимир Смыкалов.
Мы постоянно участвуем в индивидуальных турнирах — их проводится очень много. Например, соревнования на российском сайте Codeforces регулярно собирают по несколько тысяч человек, из которых россиян обычно около 20 %. Стандартный тур здесь состоит из пяти алгоритмических задач, которые нужно решить за два часа. Самое главное в сложившемся вокруг этого ресурса сообществе — личный рейтинг, рассчитанный по системе Эло, как в шахматах. Успешно выступая на турнирах, программисты получают очки — их определенное количество автоматически меняет цвет ника. Те, у кого ники красные, получают не только просьбы о помощи, но и предложения от работодателей. А главное, как любые спортсмены-чемпионы, пользуются всеобщим уважением — для многих участников «красный ник» сам по себе служит достаточным стимулом для борьбы.
Круче красных ников, только красные ники с первой черной буквой. 13 июля в двадцатке лучших на Codeforces было восемь россиян, по двое украинцев, поляков и китайцев и по одному представителю Швейцарии, Австралии, Кореи, США, Тайваня и Беларуси. При этом белорусский программист сейчас возглавляет рейтинг, хотя в принципе перестановки в таблице происходят постоянно.
Крупные соревнования проводят Mail.ru, Яндекс, Facebook, Google и другие компании. Например, в первом раунде текущего турнира Google Code Jam участвовало 20 тысяч человек. Тысяча лучших получили фирменные футболки, 25 — поедут на финал, который в этом году пройдет в Дублине.
Помимо Google Code Jam, Google проводил еще один турнир — Hash Code, финал которого в проходил в головном офисе компании. Участникам, в частности, выдавались планы зданий, которые нужно было максимально покрыть сетью Wi-Fi-точек, используя как можно меньше роутеров и проводов. Оптимального решения у такой задачи не существует, но решить ее лучше других, конечно, возможно.
Одним из зданий, в котором организаторы Google Hash Code предлагали расставить роутеры, была парижская Гранд-Опера.
Отдельный вид соревнований представляет AI Cup, где нужно написать программу искусственного интеллекта, способную играть против оригинальной программы, предоставленной организаторами в виде библиотеки. Игры создают специально для турниров, т. е. поиграть в них руками в принципе нельзя. Но сценарии подбирают так, чтобы писать для них стратегии было интересно.
В этом году игра была похожа на современные MOBA: решение должно было управлять командой из пяти волшебников, обеспечив между ними обмен командами с помощью кодовых слов.
Подобные соревнования постоянно проходят на французском сайте CodinGame. И приятно, что в турнирах AI мы добиваемся неплохих результатов, занимая места в первых двух двадцатках при полном отсутствии тренировок. Все-таки в спортивном программировании главный навык — сесть, подумать и написать код.
Платформа Topcoder иногда проводит марафонские соревнования, которые могут продолжаться несколько недель. Есть несколько турниров, например, Deadline24 или Challenge24, финальная часть которых длится сутки. Отбираются на них, решая обычные алгоритмические задачи, а в финале здесь нужно создавать стратегии для управления игрой. На этом турнире самым эффективным нам показалось писать код первые 12 часов, а исправлением ошибок заниматься после перерыва на сон.
Онлайн-платформы позволяют поддерживать себя в форме, иначе навык решения задач теряется очень быстро. Но интересны они, конечно, не только как тренировка. Соревнования всегда драйв и эмоции, которых без них может остро не хватать.
Тренировки
Почти все наши тренировки длятся по пять часов, как и самые главные соревнования. Обычно мы просто решаем задачи с одного из прошедших турниров. Новые алгоритмы мы практически не учим, поскольку знаем их достаточно много. В конце концов, от нас ждут не знания сложных структур данных, а способности быстро придумать решение. Поэтому и специальные книги нам не очень помогают. Гораздо эффективнее читать отдельные статьи или слушать лекции по конкретным темам в интернете.
Несколько раз в год проходят сборы, на которые собираются команды из разных стран. В частности, в Петрозаводск в этом году приезжали сильные поляки, а в МФТИ в Долгопрудном — программисты из Китая и Австралии. На сборах мы полторы недели разбираем новые, специально подготовленные задачи, в том числе, привезенные другими командами.
Совмещать спортивное программирование с учебой было сложно в первые два года — на третьем и четвертом курсах стало легче, поскольку занятий в университете стало меньше. В принципе в это время многие студенты уже начинают работать. У нас времени на полноценную работу пока нет, хотя предложения после турниров мы, конечно, получаем.
Соперники
Самые сильные команды стабильно собирают вузы из России, Польши, Китая, Кореи и Японии. Временами удачные составы подбираются у одного из западно-европейских или американских университетов, но в целом там спортивным программированием явно интересуются меньше. Восточная Европа и Азия доминируют и в индивидуальных турнирах, например, на Codeforces. По количеству участников на многих соревнованиях первой постоянно оказывается Индия, однако чаще всего результаты их представители показывают не самые высокие. Хотя в решении проблем дизайна индийцы как раз сильны — это проявляется на cпециальных турнирах на Topcoder.
Школьная сборная США сезона 2017/18. Успеха в спортивном программировании в Америке в основном достигают молодые люди с азиатскими корнями.
Самыми загадочными соперникам кажутся программисты из Северной Кореи, которые в условиях ограниченного доступа к интернету все-таки тренируются и часто выступают довольно прилично. Правда, в этом году на финал в США они не приехали, а на Codeforces у них сложилась репутация читеров. В частности, северо-корейских участников онлайн-турниров обвиняли, что с одного аккаунта код пишут явно разные люди. А это строго запрещено правилами.
В этом году в десятку лучших на международной Олимпиаде вошла всего одна команда из Западной Европы — студенты Королевского технологического института из Стокгольма.
Успехи России выглядят вполне объяснимыми, поскольку здесь — и очень сильная математическая школа, и сложившаяся тусовка олимпиадников, готовая помочь начинающим. В России, помимо ИТМО, очень сильные команды представляют СПбГУ (чемпионы прошлого года), МГУ, московский Физтех, вузы Екатеринбурга и Саратова, хотя время от времени хорошие составы удается собрать и другим университетам.
На фото еще одна команда ИТМО: Артем Васильев и Бориса Минаев и Геннадий Короткевич — чемпионы мира 2015 года. Кубки Международной олимпиады по программированию не переходящие — теперь в ИТМО хранится уже семь.
