В американском городе Рапид-Сити 24 мая прошел финал международной студенческой олимпиады по программированию ACM ICPC — крупнейшей в своем роде. Все последние годы первые места на олимпиаде занимают российские студенты. 2017-й не стал исключением — победила команда Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики (ИТМО) под руководством тренера Андрея Станкевича. Студенты решили 10 задач из 12-ти. «Медуза» поговорила с членом команды Иваном Белоноговым.
— Как давно вы программируете?
— Первые уроки программирования у меня были в 3 классе. Но серьезно сфокусировался на нем после успешного выступления на всероссийской олимпиаде по информатике в 9 классе. До этого я больше времени уделял математике.
— То есть в ИТМО вы пришли уже сформировавшимся «олимпиадником»? А там что? Отдельный кружок, где тренируются решать спортивные задачи?
— Да, успехи были еще в школе. На всероссийской олимпиаде в 11-м классе я был 21-м из более чем двухсот участников.
[В ИТМО] мы обычно тренируемся, решая задачи прошедших олимпиад. А после обсуждаем те задачи, которые не все смогли решить, делимся идеями. Еще есть дополнительные лекции по алгоритмам, рассчитанные в основном на первокурсников.
На первом курсе после нескольких личных тренировок были сформированы команды — по силе. Я попал в пятую команду. Со временем мой уровень повышался, команды переформировывались, и к четвертому курсу я смог попасть в первую команду ИТМО, а после этого успешно выйти на финал чемпионата мира.
— Как много приходилось тренироваться? Чтобы добиваться успехов, надо уделять этому все-все время, или достаточно нескольких часов в неделю?
— Как и во всех видах спорта, чем больше ты прикладываешь усилий, тем лучше результат. Последние полгода мы действительно много тренировались: четыре, пять тренировок в неделю. Каждая по пять часов.
— А это не мешало учебе? Есть ли какие-то послабления от института тем, кто будет представлять его на таких соревнованиях?
— Было действительно очень сложно все совмещать, особенно учитывая, насколько сложно учиться на нашей кафедре компьютерных технологий. Выходные — это дни, когда ты весь день делаешь домашку или пишешь тренировки. Послаблений никаких не было.
— Расскажите об ACM ICPC. Вы были там в первый раз?
— Чтобы участники чаще менялись, есть правило: больше двух раз участвовать в финале нельзя. У меня и Ильи [Збаня] это первая попытка, а Вова [Смыкалов] ездил в прошлом году. У него было седьмое место и серебро.
— Какими были задания? Те две задачи, которые вы не решили — что с ними не так? Команда сразу на них забила или уже в процессе поняли, что это слишком трудозатратно?
— В этом году задачи были очень идейными. Сложно было придумать решение, а писать кода нужно относительно мало. И это как раз очень здорово.
Нерешенная задача «Н» выглядела хорошо, у нее было с виду простое условие, мы много думали над ней. Но в итоге не угадали: у нее оказалось очень сложное решение, ее никто не решил.
После того, как мы сдали 10-ю задачу, у нас оставалось 50 минут. Общими усилиями через полчаса мы придумали, как примерно можно решать задачу J, и начали писать код. За 15 минут написали 200 строк, но что-то не заработало. А идейно решение было правильное.
Краткий пересказ условия задачи H: Во время поездки в Рапид-Сити вы решили выделить день на фотографирование необычного ландшафта Южной Дакоты. Вы определили количество интересных точек и время, когда освещение наиболее идеально для них. Но на каждый снимок вы тратите некоторое время, поэтому вам нужна программа, которая определит, успеете ли вы за один день снять все, что нужно. На вход подается количество фотографий, время, которое вы тратите на каждую из них, и промежуток, в который нужно успеть сделать снимок. Программа должна выдавать «Да» или «Нет».
— А в команде роли распределены? Или все коллективно сначала думаете над алгоритмами, а затем пишете код?
— Все в команде достаточно универсальны. В среднем, каждый из нас придумывает и пишет равное количество задач. Но при этом у каждого есть любимые темы. И нам очень помогает, что темы почти не пересекаются.
— Какая любимая тема у вас?
— Обычно все геометрические задачи пишу я. На олимпиаде это была задача А.
Краткий пересказ условия задачи A: власти тропического острова Пиконезия решили построить аэропорт, чтобы привлечь туристов. Чем длиннее взлетно-посадочная полоса, тем крупнее самолеты смогут прилетать. Ваша задача — получив информацию о форме острова (это всегда многоугольник), рассчитать длину самой продолжительной взлетно-посадочной полосы, которая может проходить через него.
— Планируете дальше участвовать в соревнованиях?
— Да, мы с Ильей будем искать замену Вове и участвовать в следующем сезоне.
— Есть ли корреляция между победами на таких соревнованиях и дальнейшими успехами? С трудоустройством например.
— Конечно есть. Задачи на собеседованиях в Google и Facebook похожи на те, что встречаются на соревнованиях. И, разумеется, по сложности сильно проще.
— А вы лично уже определились, где хотите работать?
— Пока еще нет. Прошлым летом был на стажировке в «Яндексе». Этим летом поеду в Калифорнию — в Google. Но пока мне больше симпатизируют небольшие компании, чем такие гиганты.
Автор: Султан Сулейманов