Будни молодого кодера. Как попасть на чемпионат мира по спортивному программированию?

О предстоящем чемпионате в Дакоте, стремительно меняющихся стандартах спортивного программирования и роли «Океана Ельзи» во всём этом журналисту «Звезды» рассказал программист-спортсмен Богдан Прищенко.

Слушаю то, что старше меня

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

Музыка помогает. На личных соревнованиях слушаю её в наушниках. Обычно то, что старше меня — Metallica, Sistem of a down, Pearl Jam. Мне близок Вакарчук (Святослав Вакарчук — лидер украинской группы «Океан Ельзи» — Прим.ред.), ведь он кандидат физических наук, а его отец был ректором Львовского университета.

Иногда тренируюсь по десять часов в день — личные тренировки, командные, разборы, онлайн-соревнования... Тогда приходится пропускать пары. Рассказывают, что некоторых талантливых участников соревнований отчисляли из их университета за неуспеваемость. Ну, например, за Мишу Майорова я не переживаю — у него репутация умнейшего человека в университете. Он может заниматься на паре своим делом и время от времени исправлять ошибки преподавателя. Я же отношусь к университету, скорее, как к месту, где формируется мировоззрение и налаживаются связи.

Некоторые задачи у меня «в пальцах»

— В ПГНИУ действительно сильная школа спортивного программирования. Нас тренирует Юрий Айдаров. Внутри нашей команды тактики иногда меняются. Миша Майоров лучше всех решает сложные задачи. Илья Кучумов пишет задачи на реализацию. Например, найти точку пересечения двух прямых в трёхмерном пространстве или объём пересечения цилиндра с конусом. В таких задачах нужно много писать и долго исправлять ошибки.

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

Один участник в моей команде пишет на Java, два пишут на С++ — это быстрей. У нас есть шутка: проще всего оптимизировать решение, написанное на Java — это переписать его на С++.

«Изобретение» калькулятора и прогнозирование урожая

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

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

Существуют классы задач, в которых нет правильного ответа. Например, нужно что-то оптимизировать, и никто не знает, насколько хорошо это можно сделать. Ещё участники соревнуются в построениях прогнозов. Такие задачи могут быть поставлены и реальными компаниями. Я как-то решал марафонскую задачу от одной американской компании, которая занимается выращиванием сои. Они интересовались построением прогноза урожая и показали часть данных за N количество лет. Нужно было построить модель, которая восстановила бы спрятанную часть данных. Подобная практика может быть выгодна компании: она даёт приз 5-10 тысяч долларов, а за это получает свежие идеи и хорошие модели. Участники же могут зарекомендовать себя для будущего трудоустройства.

Дисквалификация за «идейное» совпадение

— Не допустить на соревнования могут по разным причинам. Лет 10 назад был случай, когда один университет вышел на финал, но команда не поехала, потому что не выделили финансирование. Этот университет дисквалифицировали на 5 лет.

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

Всё, как в лёгкой атлетике

— В спортивном программировании — как в лёгкой атлетике: планка достижений постоянно повышается.

Мой тренер из Екатеринбурга Михаил Рубинчик работает над теорией строк, и в его следующей публикации будет использован алгоритм, который занимает более 1000 строк кода. Они с ассистентом работали целый месяц над тем, чтобы исправить в нём все ошибки. Лет через десять этот алгоритм войдёт в спортивное программирование, все будут его знать и говорить, что это стандартный алгоритм, и его можно написать за час. Реализация сократится с тысячи строк до двухсот.

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

Что дальше?

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