Олимпиадное программирование – Высшая лига
В декабре произошло знаковое, я бы даже сказал, эпохальное событие не только для Института Вычислительной Математики и Информационных Технологий, но и для КФУ. Дело в том, что впервые в истории команда, состоящая из студентов нашего университета, прошла в финал одного из самых престижных чемпионатов мира по программированию ACM ICPC. Имена этих героев, вернувшихся в родной город с триумфом, подобно древнеримским полководцам - Динар Гайнитдинов, Владимир Бутин и Рамис Ямилов. На полуфинале, состоявшемся 7 декабря в городе Санкт-Петербург, они сумели решить 6 задач, тем самым опередив 200 команд и получив в общем зачете диплом второй степени. Скоро участники поедут в Марокко на финал, а пока программисты ещё в Казани, мы попросили их ответить на наши вопросы, на что Владимир и Динар любезно согласились.
- Уезжая в Петербург на полуфинал, рассчитывали ли вы на такой высокий результат?
Владимир: Нет. У нас были более приземленные планы - постараться выступить не хуже, чем в предыдущие три года и войти, наконец, в топ-50. Кажется, мы слегка перестарались.
Динар: Было бы неправильно так говорить. Мы много тренировались, но чтобы пройти дальше, необходимо было опередить множество других команд, без доли удачи это не представлялось возможным.
Также, всё закончилось бы иначе, не сохрани мы концентрацию до конца соревнования.
Рамис: Нет. Даже после завершения основного тура я думал, что 6 задач не хватит для прохода.
- Какой язык вы используете на олимпиадах и почему?
Владимир: C++. Мы слишком к нему привыкли. По сравнению с Java, он более лаконичный и, в среднем, работает быстрее из-за меньшего оверхеда. С другой стороны, в Java гораздо больше готовых реализаций всяких структур данных и алгоритмов. Кроме того, работая с C++, вероятность допустить ошибку, которая не будет отловлена, несколько выше. Обычно выбор языка - дело вкуса.
Динар: С++. За некоторыми исключениями, мне он кажется довольно удобным для решения олимпиадных задач.
Рамис: С++. Привычка наверное.
- Как у вас обычно распределяются роли в команде?
Владимир: В первые минуты Динар с Рамисом просматривают все задачки и выбирают самые лёгкие. Я в это время пишу шаблон для программ, после чего сдаю выбранные задачки. После этого мы пытаемся решить оставшиеся задачки, при необходимости помогая друг другу тестами, теорией и идеями. Набирает на компьютере обычно тот, кто придумал решение, хотя бывают исключения. Обычно мы решаем 2-3 задачи одновременно, в исключительных случаях мы можем втроём сидеть за одной задачей. Вроде бы всё стандартно.
Динар: Я стараюсь больше обдумывать решения, чем их реализовывать - у Вовы и Рамиса это получится лучше, чем у меня. Также, у каждого, пожалуй, есть тип задач, которые он любит больше остальных - так их и распределяем.
Рамис: Наверное, в основном кодит Вова, мы думаем над следующими задачами. Хотя на полуфинале было чуть по-другому.
- Когда вы написали свою первую программу?
Владимир: Это было очень давно, я не помню, когда это было. Какое теперь это имеет значение?
Динар: В пятом классе, это был калькулятор на Visual Basic. После этого, однако, было много периодов, когда я не занимался активно программированием.
- Расскажите, как проходят ваши тренировки?
Владимир: Мы берём какой-нибудь сложный контест, уровня полуфинала ACM ICPC или выше, устраиваемся где-нибудь вместе и 5 часов его решаем. После контеста, в свободное время, пытаемся его дорешать. Таким образом, условия для тренировок мало чем отличаются от условий для «реальных» контестов. Тут важно не только уметь решать сложные задачи, надо решать их быстро и решать надо до последнего. Ситуация, когда олимпиадник перестает решать на 3-4 часу и начинает просто смотреть на задачи и компьютер, не такая уж и редкая.
Динар: На командных тренировках имитируется работа на реальном соревновании - обычно для этого используют наборы задач с прошедших турниров, которые мы ещё не решали. Важным элементом подготовки являются дорешивания - разбор задач, которые не получилось решить до окончания тренировки.
- Какой тип задач даётся сложнее остальных?
Владимир: Персонально – мат. ожидания в перестановках, а также всё, что связано с мат. ожиданиями и перестановками. А так - сложно сказать, возможно - отвечать на такие вопросы.
Динар: Обычно сложными являются задачи, в которых очень много различных направлений для обдумывания - легко запутаться или пойти не в ту сторону. Особенно, если подобных задач до этого решал мало.
- Какие у вас планы на финал?
Владимир: У меня - никаких, ну разве что выступить как можно лучше.
Динар: Решить всё, что нам по силам.
Рамис: Решить столько же задач, сколько и команда на 60-м месте (50%).
- Возникают ли какие-либо сложности при подготовке к поездке, или это только предстоит?
Владимир: Нам приходится сочетать подготовку с учебой в магистратуре и работой, кроме того, у нас нет опыта поездок такого уровня.
Динар: Приходится совмещать тренировки с работой, а также с личной жизнью.
Рамис: Надо находить время для этой подготовки, еще писать магистерский диссер и работать.
- Есть ли у вас кумир среди известных программистов?
Динар: Да, есть много известных программистов, к опыту и умениям которых стоит стремиться.
Рамис: Петр Митричев, Егор Куликов, ну и Гена Короткевич. Top 3 рейтинга Topcoder.
- Как вы решили последнюю задачу, благодаря которой прошли в финал?
Владимир: Я сидел некоторое время над ней, подбирая разные входные данные, и решал её для разных частных случаев. В какой-то момент я обнаружил, что в ответе входная последовательность разбивается на две независимые последовательности. Динар довёл мою идею до поиска наибольших возрастающих/убывающих последовательностей, а Рамис это всё реализовал. Потом обнаружилось, что в разборе было совершенно другое решение, с одинаковой сложностью.
Рамис: Долго над ней думали. И Динар с Вовой в итоге за 20 минут до конца додумали идею с деревом отрезков и рассказали мне, чтоб я реализовал. В итоге успели.
- Что посоветуете начинающим олимпиадникам?
Владимир: Стараться участвовать во всевозможных контестах вроде Open Cup, TopCoder, Codeforces и Code Jam. Обязательно читать разборы и реализовывать все не получившиеся ранее задачки. Периодически решать задачи из архивов вроде acm.timus.ru. Очень желательно проходить на онсайты, т.е. в очные туры, поскольку решать задачи дома и где-то в чужом городе - эти весьма разные вещи. Ну и главное - не опускать руки при неудачах.
Динар: Не отчаиваться при поражениях. Решать как можно больше задач. Их так много, что можно хоть сутками это делать. Стараться выбирать те из них, которые принесут максимальную пользу.
Рамис: Решать задачи и участвовать в личных онлайн-соревнованиях Codeforces и Topcoder.
Матвей Малацион, редакция «Include»
Игры – современное искусство
Вся Википедия для всех...бесплатно
