О том, как появляются новые задачи для соревнований по олимпиадному программированию, а также о «типичных путях развития для бывших олимпиадников» рассказал «Ъ» тренер Центра развития ИТ-образования МФТИ Михаил Тихомиров.
— Вы раньше принимали участие в ICPC, а потом стали тренером. Это было некое логичное продолжение?
— Пока я был студентом, я действительно много участвовал в соревнованиях. Начал я еще в школе, где-то в 2005–2006 году, условно с восьмого-девятого класса. Я был победителем во Всероссийской олимпиаде для школьников, потом поступил на механико-математический факультет МГУ, где успел поучаствовать в соревнованиях ACM, не показывал тогда особых успехов. Но все равно мне это интересно было всегда. Потом я поступил в аспирантуру в МФТИ, а в соревнованиях можно участвовать и аспирантам. Но я так и не прошел в финалы ICPC: у меня закончились попытки, да и возраст подошел (студенты старше 24 лет к участию не допускаются.— “Ъ”). А дальше я стал участвовать в проведении сборов: Физтех давно проводит олимпиадные школы для школьников, в том числе по информатике. И в какой-то момент мне предложили стать тренером, так как я один из наиболее опытных участников ICPC в МФТИ.
— Многие ли тренеры Moscow Workshops — это бывшие участники? Чем занимаются сейчас те, кто был с вами в команде?
— Чтобы быть тренером, необходимо хорошо разбираться в задачах и теории. Многие тренеры — это бывшие активные участники, решившие взять на себя подготовку смены в своем вузе, а тренеры лучших университетов — это почти всегда медалисты финала чемпионата мира, хотя здесь я скорее исключение, и призеры крупных международных личных соревнований, таких как IOI (международная олимпиада школьников), Google Code Jam, Topcoder Open и других. Можно открыть биографию любого нашего лектора, например Андрея Станкевича из ИТМО, Андрея Лопатина из СПбГУ, Михаила Мирзаянова из Саратовского университета, у всех достаточно титулов.
За карьеру участника я сменил довольно много составов. Многие мои бывшие сокомандники нашли работу в хороших компаниях, некоторые за границей. Кто-то пытается открыть свой ИТ-бизнес. Есть и те, кто работает в университетах, занимается преподаванием и наукой. Все это довольно типичные пути развития для бывших олимпиадников.
— В чем основные задачи тренера?
— Тренер — это формальная должность, но если касаться того, как мы работаем с ребятами внутри университета, то мы следим за тем, какие к нам поступают перспективные абитуриенты. Это делается по результатам олимпиад, например, очень хороший результат дают призеры всероссийской олимпиады. Основная масса будущих участников приходит из школьных олимпиад по математике и информатике. Конечно, есть случаи, когда олимпиадное программирование становится интересно не на первом курсе, а уже на старших, и люди, которые в школе олимпиадным программированием не занимались, первые два курса университета тоже не занимались, потом стали видными соревнующимися.
Обычно, набрав студентов, мы вначале организуем личные тренировки, чтобы они прониклись спецификой, и затем потихоньку вводим в командные соревнования. Некоторым это может быть сложно, потому что это довольно большой скачок от школьной практики к студенческой, к регулярным занятиям и тренировкам. Уже ко второму курсу мы проводим еженедельные тренировки, командные обсуждения задач, частенько возим наши команды на выездные командные олимпиады — их проходит где-то пара десятков в год, в том числе и за границей.
— На какие, например?
— В России из таких олимпиад самые известные, не считая отборочных этапов ACM, которые проходят в Москве и в Питере,—Всесибирская олимпиада, которая проходит в Новосибирске, это известная старая олимпиада. Есть еще очень хороший чемпионат Урала, он не в системе отборочных этапов, тем не менее все сильные команды стараются туда приезжать, и туда мы тоже отправляем одну или две команды. Это топовые соревнования, бывают и чуть поменьше — региональные: в Коврове, в Гродно и Минске (Белоруссия). Съездить на такое командное соревнование, на месте посоревноваться в соответствующей обстановке очень полезно, особенно на первых этапах: это помогает преодолеть страх, нервозность.
— Как строится работа тренера?
— У нас много команд. В Барселону на тренировки приехали две самые сильные, но у нас есть еще около десятка команд-кандидатов. Это очень условное название. Кандидаты они потому, что в отборочный полуфинал ICPC проходит пять команд, а в финал всего одна. Соответственно, те команды, которые имеют шанс попасть в полуфинал ACM ICPC, они у нас в фокусе. Среди них обычно не больше двух-трех команд, которые имеют шанс пройти в финал. Но при этом в финал по правилам проходит только одна команда от вуза. И мы всячески побуждаем наших студентов тренироваться лично и пытаться разбираться в тех задачах, которые ты не умеешь решать. Допустим, на тренировке ты встретил задачу, но такого, что какая-то определенная тема для тебя плохая, быть не должно. И у нас есть много возможностей и не в команде потренироваться, а в хорошей команде все участники обязательно и лично тоже очень сильные, хорошо знают теорию, хорошо пишут программы. Они могут самостоятельно тренироваться в интернете, где регулярно, несколько раз в неделю, проходят личные соревнования. Это очень хорошая практика, когда ты несколько раз в неделю по два часа решаешь задачки, узнаешь что-то новое, набиваешь руки.
— Как проходят отборочные соревнования на ACM?
— Есть, например, московский четвертьфинал. Туда могут приходить более-менее готовые команды из московских вузов и из вузов Московской области. Все приходят на место, последнее время это площадки и в МГУ, и в МФТИ, потому что на одну площадку все желающие не помещаются, не хватает компьютеров, классов. И там все очень серьезно. Есть дежурные, чтобы никто в интернете не посмотрел решения, например, через телефон. А вот в финал проходят по квотам от вуза, то есть у каждого вуза есть своя команда, и кто поедет, зависит от каких-то прошлых заслуг. Полуфинал будет проходить в декабре в Санкт-Петербурге. И полуфинал проходит еще более строго.
— У МФТИ огромный опыт проведения тренировок, если мы говорим о Moscow Workshops, однако студенты этого вуза победителями не становились, только золотыми медалистами. Почему?
— Хороший вопрос. Если бы мы умели на него отвечать... МФТИ не выигрывал, но мы три раза брали медали, два раза из них золотые. Если пытаться понять, почему, например, ИТМО в последнее время побеждает, то думаю, там очень хороший тренерский состав, есть Андрей Станкевич (его команды семь раз побеждали в ACM ICPC.— “Ъ”), но не только он, там есть другие прекрасные тренеры, которые работают с кафедрой технологий. Ну, и кроме того, ИТМО начал выигрывать эти соревнования очень давно, поэтому среди абитуриентов, которые заинтересованы в участии в соревновании, уже есть заранее такой образ, что ИТМО — самый крутой университет. И они целенаправленно идут туда.
— Команды каких вузов сейчас считаются сильными, у кого сильная школа?
— На сборы к нам сейчас приезжают со всего мира. У нас были ребята из Японии, Китая, Австралии, из Европы очень много. В Китае, как правило, сильнейший Шанхайский университет, в Японии сильнейший,— Токийский университет, в Америке очень сильно обычно выступают гарвардцы и MIT (Массачусетский технологический университете.— “Ъ”). Но американцам довольно сложно до нас ехать, они нас сейчас к себе зовут.
И на сборах мы пытаемся ребят подтягивать: если какую-то тему мы рассказывали студентам, а потом им попадается нечто подобное, естественно, они быстренько эту задачу решают и переходят к следующей. В этом и цель сборов. Кстати, здесь тоже есть такая специфик: нет какого-то круга определенных тем, на которые обязательно даются задачи, потому что постоянно возникают новые темы. Это связано и с тем, что в математике возникают новые открытия.
— Могли бы вы привести пример?
— Например, тренер Уральского федерального университета Михаил Рубинчик защитил диссертацию по итогам придуманной ребятами задачи. Они придумали к АСМ задачу, и решение, и оказалось, что, в общем, в науке такого еще не было. Задача связана с поиском палиндромов. Может показаться, что это игрушечка такая, но такие алгоритмы важны, например, для биоинформатики, потому что геном в биоинформатике — это как раз очень, очень длинный текст, в котором нужно искать одинаковые, похожие куски. Вот ребята придумали задачу с поиском зеркальных кусочков в строке, и алгоритм у них оказался новый и научно ценный. Оказалось, что, в общем, в науке такого еще не было. Не сказать, что так происходит часто, но одно из достоинств и ACM, и подобных соревнований в том, что все это настраивает мозги на нужный лад — отношение к задаче как к научной проблеме. И нередки случаи, когда бывшие участники ACM действительно добивались в науке больших успехов.
— Вы сейчас принимаете участие в каких-нибудь соревнованиях?
— В последнее время я начал снова участвовать в соревнованиях, хотя крупных командных чемпионатов для моего возраста сейчас нет. Но бывают личные соревнования, например, Google Code Jam (считается одним из самых массовых чемпионатов по программированию, участникам предоставляется набор алгоритмических задач, которые нужно решить за ограниченное время.— “Ъ”). Это довольно похоже на ACM. Это открытое соревнование — там на первом этапе участвуют десятки тысяч человек, но в финал проходят где-то 20–25. В этом году я прошел в финал и, кажется, в десятку вошел.