Пётр Митричев — Легенда спортивного программирования

Говорят, когда он появился на свет, к нему заглянул сам Дональд Кнут. Говорят, когда его пригласили работать в Google, он за 15 минут переписал весь поисковый алгоритм 16 раз. Говорят, он с улыбкой следит за прогрессом квантовых вычислений, так как при виде его числа от страха факторизуются сами. Но мы точно знаем одно: Пётр — настоящий бог спортивного программирования.

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

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

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

На каком языке ты писал решения для задач?

На Java. В школе я писал на Pascal, потому что больше тогда ничего не знал. А потом, когда нужно было выбрать, на что перейти, Java оказался ближе к Pascal.

В условиях соревнования нужно написать программу за 20–30 минут, и она должна сразу работать правильно. Поэтому очень важно, чтобы язык не позволял сажать баги. C++, который использует большинство, отличается тем, что на нем довольно легко написать неправильную программу. Можно случайно забыть что-то, присвоить неправильный тип переменной, но все это будет как-то компилироваться и как-то работать. Скорее всего, не так, как ты ожидаешь.

В Java, если допустить ошибку или опечатку, программа, скорее всего, просто не скомпилируется. Здесь все строже, как и в случае с Pascal. Мне это показалось более подходящим. Обратная сторона медали — программы на Java часто работают раза в полтора медленнее, чем программы на C++. Иногда именно этих полутора раз не хватает, чтобы программа укладывалась в условие задачи.

Язык программирования каждый может выбирать сам, да?

Есть ограничения. Конечно, бывают разные соревнования... возьмем Google Code Jam, к примеру. Когда мы решали, как лучше его сделать, мы придумали, что можно работать на любом языке. Ты скачиваешь на компьютер входной файл с данными задачи, запускаешь на компьютере свою программу, а потом посылаешь на сервер результат. Какой у тебя на компьютере стоит компилятор/интерпретатор, тем и можно пользоваться. Минус данной системы в том, что компьютеры у людей разные. У кого-то компьютер в десять раз мощнее, чем у другого. Поэтому приходится создавать задачи, где неправильное решение от правильного по скорости отличается хотя бы в сто раз. Чтобы если у человека компьютер в десять раз медленнее, правильное решение у него работало, или на компьютере в десять раз быстрее неправильное решение все равно не работало. Поэтому нужны задачи с большим зазором между правильным и неправильным решением по скорости работы.

На Topcoder, Codeforces и ACM используется стандартная система, где ты посылаешь исходный код и они запускают его у себя на сервере. Здесь ты ограничен тем, что у них на сервере есть. Большинство участников, 70–80% используют C++, еще 20% используют Java, остальных языков очень мало. Это, мне кажется, такой цикл — новые люди, которые приходят на соревнования, начинают общаться с другими, более старыми участниками, те учат новичков тому, что умеют сами. В итоге новые люди тоже начинают пользоваться теми же языками. Так что эти два языка не то чтобы как-то особенно подходили для соревнований, просто так сложилось исторически.

То есть в жизни все это применимо? Ведь наверняка сложно найти работу, на которой эти знания пригодились бы. Да, можно пойти в Google или Яндекс, но прийти в какой-нибудь банк уже сложнее?

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

У тебя, наверное, была какая-то особая история, как ты попал в Google?

Да нет никакой истории, все было так же, как у других. Сейчас я занимаюсь поиском (общей его частью, которая не зависит от страны и языка), но, к сожалению, не могу ничего об этом рассказывать, так как это очень конфиденциальная часть.

Спортивное программирование: «за» и «против»

Давай я попробую задать тебе глупый вопрос :). Почему нужно заниматься спортивным программированием, как ты считаешь?

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

А если попытаться придумать причину, почему не стоит тратить время на спортивное программирование?

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

Но что говорит практика, возможно ли, например, построить карьеру вокруг спортивного программирования?

В России есть несколько человек, которые профессионально занимаются подготовкой новых спортивных программистов, — тренеры. Андрей Станкевич, Миша Мирзаянов и другие. Все они преподают в университетах, но существенную часть своего рабочего времени тратят именно на подготовку студентов и школьников к соревнованиям по программированию. Для них это действительно работа и, можно сказать, карьера.

Ты сам не задумывался о подобном? Нигде не участвуешь в жюри или как составитель задач?

Я пробовал учить школьников в 57-й школе, где сам учился. Пробовал готовить команды к олимпиадам. Сейчас в Москве эта тема очень активна — есть команды у МГУ, Физтеха, Высшей школы экономики. Но с преподаванием у меня как-то не сложилось.

Что до контестов, прежде всего я помогаю делать задачи для Google Code Jam, для нашего соревнования. Плюс помогаю с полуфиналом ACM, который проходит в Санкт-Петербурге. Это отбор среди российских команд и команд бывшего СССР на финал.

Можно ли заработать на соревнованиях? Ведь за победу дают денежные призы.

Слишком маленькая вероятность. Один приз на десять тысяч участников?.. Я не назвал бы это заработком. Рассчитывать на это как на основной источник дохода... мне кажется, без шансов.

Но, как я уже сказал, есть много разных соревнований. Тот же Topcoder проводит соревнования по разработке программ. Допустим, нужно разработать компонент для программы, который делает то-то. По итогам оценивают, у кого что получилось, и лучшее используют — это решение покупает клиент и платит деньги тому, кто это решение сделал. Люди, которые занимаются этим full time, как я понимаю, зарабатывают довольно прилично.

Контесты сегодня

Расскажи подробнее, какие сейчас бывают соревнования, как все это происходит?

На сегодня существует два вида контестов. Есть еженедельные, регулярные соревнования. Их проводят два основных сайта — TopCoder и Codeforces. Каждый контест занимает полтора-два часа. Там участникам дается несколько задач, которые нужно решить и послать программу на сервер. Организаторы проверяют, работает ли программа.

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

TopCoder — самый старый и известный сайт с еженедельными контестами. У них следующие правила. На решение трех задач отводится один час пятнадцать минут.

Задания обычно делятся на очень простые, средние и сложные. Устроители стараются подобрать их так, чтобы, скажем, пять человек решили все задачи, сто человек — две, а все остальные решили хотя бы одну. Притом для каждой задачи важно, когда ты ее отправишь, — чем позже, тем меньше ты получишь баллов. Так разделяются те люди, что решили одинаковое число задач. Потом баллы суммируются. Обычная задача стоит 250 баллов. Средняя 500. Сложная 1000. В среднем у людей с первых мест получается по тысяче с чем-то баллов за соревнование.

Дальше делают перерыв пять минут и еще пятнадцать минут отводится на поиск ошибок у других. Можно открыть решение любого человека, по любой задаче в твоей «комнате». «Комната» — это когда люди, участвующие в соревновании, случайно разбиваются на группы по двадцать человек. Разбиваются на «комнаты». Ты можешь открыть любое решение любого человека из твоей «комнаты». Если решение кажется тебе неверным, то можно вбить входные данные, на которых оно будет неправильно. И если оно действительно дает неправильный ответ, ты получаешь за это еще 50 баллов. Это, конечно, меньше стоимости задачи. Но это опять же делается для разделения людей. Основные баллы все-таки начисляют за решение задач, а не за поиск ошибок.

После всего этого задачи проверяются на тестах, которые готовило жюри. Если задача не работает, человек получает 0 баллов.

Есть еще второй сайт, российский, — Codeforces. У них правила немного другие, но формат приблизительно тот же — два часа и несколько задач. Если угодно, такой формат можно назвать развлекательным, в отличие от студенческих олимпиад, которые длятся по пять часов.

Но еще есть крупные, ежегодные контесты?

Да, кроме двух описанных соревнований, что проходят еженедельно, есть еще множество ежегодных соревнований. Обычно они устроены так: некая крупная компания (Google, Яндекс, TopСoder, IBM) проводит соревнование, с несколькими этапами отбора. Первые этапы проходят по интернету. А финальный этап уже проводится в каком-то конкретном месте, куда свозят всех финалистов. Таких соревнований всего штук пять-десять, но они длинные, так что все время происходит какое-то из них.

Все эти соревнования индивидуальные?

Большинство соревнований сейчас индивидуальные. Командные — это главным образом студенческие соревнования, основное из них — ACM ICPC. И другие студенческие соревнования тоже обычно делают командными, потому что, грубо говоря, там команда уже есть. Так легче заинтересовать людей. Вот ветеранские соревнования обычно уже личные.

Почти у всех соревнований есть некие рейтинги, самый известный у TopСoder. Что это такое?

У еженедельных соревнований есть рейтинг, как в шахматах, который обновляется после каждого соревнования. Те, кто выступил лучше, получают плюс, кто хуже — минус. Если же ты не участвовал вовсе, рейтинг не меняется. Система построена таким образом, чтобы уравнять людей, которые бывают часто и редко. Давления «нужно участвовать постоянно» там нет. Есть много людей, которые гораздо старше меня, они появляются очень редко — раз в два месяца, — и все равно у них остается хороший рейтинг, потому что они продолжают хорошо решать задачи.

В рейтинге TopCoder ты сейчас второй?

Да, на первом месте Гена Короткевич, очень умный студент из Гомеля, сейчас он учится в ИТМО. На Codeforces у меня в последнее время результат похуже, сейчас я шестой или пятый. Там тоже Гена на первом месте.

Наверное, играть в онлайне и офлайне — это совсем разные ощущения и опыт?

Конечно. Мне кажется, очень важная положительная сторона спортивного программирования заключается в том, что все соревнования заканчиваются onsite-раундом, куда съезжаются все лучшие. Я благодаря этому познакомился со многими классными людьми со всего мира. Вообще, основной «приз» в таких соревнованиях, как мне кажется, — это именно встреча с людьми. Проводишь с ними время, общаешься, узнаешь что-то новое. Очень забавно, что людей из других стран, которые зачастую плохо говорят по-английски, тем не менее очень легко понимать, потому как у них очень похожие интересы.

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

Бывает такое, что компании потом пытаются использовать в жизни наработки из сданных конкурсантами решений?

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

Соревнования со временем меняются? Становятся сложнее или, наоборот, проще?

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

О задачах и их составлении

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

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

Придумывать такие задачи — это ведь особый скилл?

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

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

Авторы часто пытаются сделать задачи ближе к реальности, используют термины из жизни?

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

Бывают и другие соревнования. У TopCoder это называется Marathon Match, и другие компании тоже проводят подобные контесты. Они устроены немного иначе. Это уже соревнования не по алгоритмам, а по решению приближенных задач. Когда нет точного решения и нужно придумать вариант как можно лучше. Такие соревнования длятся обычно две недели, месяц. Можно присылать разные решения и наблюдать, что, ага, вот сейчас мое решение лучше остальных на 20%.

«Лучше» — в смысле быстрее, использует меньше памяти и так далее?

Да. К примеру, нужно придумать схему распределения движения автобусов по карте Москвы, чтобы использовать как можно меньше автобусов. То есть в условии задачи есть некий параметр, который нужно оптимизировать, но единого «верного решения» не существует, только какие-то приближенные алгоритмы.

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

С чего начать

С точки зрения подготовки хорошего алгоритмического программиста и участника разных контестов — как подготовить себя к такому? Если представить себя на месте старшеклассника или студентов первых курсов?

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

А если я беру задачу и вообще не знаю, с какой стороны к ней подойти?

Значит, возьми попроще. Они ведь разные. Есть задачи, которые может решить каждый второй выпускник школы. Там совершенно разные уровни сложности. Втянуться должно быть довольно легко. Другого способа, как мне кажется, нет. Плюс таким образом ты сразу поймешь, нравится тебе эта деятельность или нет.

Что нужно делать, чтобы набрать алгоритмическую базу? Вряд ли нужно прямо сразу кидаться читать Кнута.

Мне кажется, начинать нужно именно с задач. Уже потом, когда ты поймешь, что не можешь решить какую-то конкретную из них, в этих соревнованиях у каждой есть разбор. Можно прочитать решение, если справиться самостоятельно не получается. Например, в разборе указано, что в решении задачи используется некий алгоритм. Можно почитать, что это за алгоритм, где еще он применяется.Так лучше, чем читать по списку «ага, у меня есть алгоритм, который мне нужно изучить за лето». Лучше отталкиваться от конкретной задачи, которую ты не смог решить, потому что не знаешь какой-то конкретный алгоритм. Это более правильно. Запоминаешь лучше, мотивация получается сильнее. Такой способ изучения алгоритмов, наверное, дольше, чем по списку, но он приводит к лучшим результатам.

Если хочется «прокачать» себя именно по алгоритмам, есть какая-то литература, учебники?

Самый стандартный учебник — Кормен, Лейзерсон, Ривест с ослом на обложке. «Алгоритмы: Построение и анализ» называется. Не знаю, я довольно давно не учился, сейчас наверняка есть новые учебники, которые могут быть лучше. Но в мое время использовали Кормена. Кнут — это, скорее, этакий reference book. Если что-то нужно найти и оно нигде не находится, скорее всего, там оно будет. Но читать Кнута подряд... это довольно грустное занятие.