Короткий путь в Google


Спортивным программированием студенты НГУ начали заниматься c 1997 года, а в первый раз вышли в финал Международного чемпионата ACM International Collegiate Programming Contest (ACM-ICPC) в 1999 году. С того времени команда одиннадцать раз выходила в финал ACM-ICPC, в 2007 году завоевала «серебро». Доцент НГУ, старший научный сотрудник Института систем информатики СО РАН, руководитель и тренер по спортивному программированию Татьяна Чурина рассказала, по каким параметрам университет находится на одном уровне с Массачусетским технологическим институтом и Стэнфордом, какой путь трудоустройства в Google один из самых коротких и зачем надо заставлять подопечных отдыхать.

Медведев не помог

Международный чемпионат по программированию ACM-ICPC — один из самых престижных в мире. По словам Татьяны Чуриной, одно время вопрос усиления подготовки студентов США по данному направлению обсуждался на правительственном уровне. Особенность Новосибирского государственного университета — участие студентов в международном чемпионате считается «делом обычным»:

— Студенты не получают никаких поблажек от преподавателей. Учеба в любом случае на первом месте.

Как рассказывает Татьяна Чурина, один из самых показательных случаев был в 2007 году: команда, завоевавшая серебро в Токио, отправилась на встречу к тогда еще первому зампреду правительства РФ Дмитрию Медведеву, а в это время одногруппники одного из членов команды, Степана Гатилова, сдавали коллоквиум по английскому языку. Степан попросил Медведева подписать открытку с просьбой освободить его от коллоквиума. Премьер тогда посмеялся: «Таких отмазок я еще не давал». После встречи журналисты нашли преподавателя английского и взяли у нее интервью, в котором она сказала, что Степан – отличный студент, но коллоквиум сдать он обязан.

«Я этим болею»

Татьяна Чурина начала готовить участников олимпиад по программированию в 1998 году, когда была сотрудником Высшего колледжа информатики:

— Я в жизни не занималась олимпиадами. Вела курс «Методы программирования» в Высшем колледже информатики НГУ. В 1998 году ко мне подошел директор ВКИ Николай Сычев и сказал, поскольку у тебя такой курс, то тебе и заниматься олимпиадной подготовкой.

В 1999 году я начала заниматься с Евгением Четвертаковым подготовкой к участию в заключительном туре Всероссийской олимпиады школьников по информатике. Его на месяц освободили от занятий — это был единственный подобный случай за всю историю участия наших учеников в чемпионатах и олимпиадах. Он каждый день приходил ко мне на работу в ИСИ СО РАН, мы с ним разбирали классические алгоритмы и решения задач, он писал решение, а я фиксировала время, затраченное на реализацию решения, далее давала подобную задачу и снова засекала время — так мы повышали уровень техники программирования. В результате на Всероссийской олимпиаде школьников в Санкт-Петербург он занял 13 место из 150 участников.

Университетская команда отреагировала на победу Евгения, и я предложила продолжить подготовку студентов совместно. Со Всероссийской олимпиады мы привезли автоматическую систему тестирования, которую Дмитрий Иртегов, ныне заведующий учебной лабораторией Parallels-NSU, адаптировал для наших тренировок. Мы начали проводить регулярные занятия с использованием этой системы, читать лекции по классическим алгоритмам, проводить разбор задач. Команда НГУ в полуфинале чемпионата ACM-ICPC в 1999 году заняла третье место. Университет представляли Александр Шапеев, Алексей Бабурин, Евгений Четвертаков. В 2001 году к тренерскому составу присоединилась Татьяна Нестеренко.

В дальнейшем организатором тренировок стал факультет информационных технологий. И я не уверена, велись бы тренировки все эти годы, состоялись бы наши поездки на финал ACM-ICPC, если бы не помощь деканата этого факультета.

— Ну что тут скажешь? Я этим болею, — определяет свою увлеченность Татьяна Чурина.

Успехи НГУ на международных чемпионатах по программированию не могут быть чьей-то личной заслугой, подчеркивает она, это дело коллектива. Сейчас в тренерском составе работают «бывшие олимпиадники», в свое время участвовавшие в ACM-ICPC, которые взяли на себя основную нагрузку, — Степан Гатилов, Александр Стененко и Вадим Зайцев. Помимо того, что они ведут общие тренировки, каждый из них дополнительно работает со своей командой.

Масштабная. Поттосинская. Наша

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

— В 2000 году, когда команда НГУ впервые участвовала в финале ACM-ICPC в Орландо и заняла 15 место из 64, мы с директором ИСИ СО РАН Игорем Поттосиным пришли на прием к ректору НГУ Николаю Диканскому с предложением создать свою олимпиаду, чтобы подтянуть уровень сибирских команд. Он сразу одобрил наше предложение и в дальнейшем всегда оказывал поддержку этой олимпиаде.

В 2014 году в отборочном онлайн-туре Поттосинской олимпиады приняла участие 341 команда. В очный тур приглашается 50 лучших команд, состоящих из трех участников, половина – из регионов Сибири и Дальнего Востока. По уровню задач и масштабу олимпиада, проводимая НГУ и ИСИ СО РАН, соответствует полуфиналу ACM-ICPC, отмечает Татьяна Чурина.

Гангстеры в ресторане

– Лично я люблю задачи красиво сформулированные. Мне нравятся задачи на динамическое программирование, когда путь к ответу — это разбиение задачи на подзадачи и последующий синтез решений этих подзадач. Хотя бывают красивые задачи, которые решаются перебором. Студенты НГУ отличаются тем, что стараются придумать изящный алгоритм, уйти от полного перебора. Приведу пример старой задачи про гангстеров, которая решается с использованием метода динамического программирования:

N гангстеров собираются в ресторан. i-й гангстер приходит в момент времени Ti и имеет богатство Pi. Дверь ресторана имеет K + 1 степень открытости, они обозначаются целыми числами из интервала [0, K]. Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0). i-й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте Si. Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, T]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом

Режим труда и отдыха

Тренировка по спортивному программированию длится обычно пять часов. Тренеры НГУ работают с командами не только в учебное время, но и на сборах, которые проводятся несколько раз в году.

Заставить отдыхать студентов, рассказывает тренер, очень сложно, потому что они нацелены работать до упора:

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

В чем секрет

Есть несколько показателей успешной командной работы, говорит Татьяна Чурина:

— Во-первых, в команде должно быть разделение труда — решатель, кодер, тестер. Хорошо, когда все эти качества присутствуют. Идеальный вариант, когда участники могут заменять друг друга, есть команды, в которых каждый студент — это «3-в-1». Но главное — они должны понимать друг друга с полуслова.

Давно в мировом рейтинге

Команда университета с 2000 года стабильно выступает в Международном чемпионате ACM-ICPC. В рейтинге с 1992 по 2014 годы — 476 университетов, НГУ занимает 36–44 место и обгоняет Калифорнийский университет в Беркли и Национальный университет Сингапура.

По мнению Татьяны Чуриной, стабильный выход команды в финал этого чемпионата и последующее трудоустройство студентов в крупнейших IT-корпорациях— это хороший показатель качества образования, которое дает университет в сфере информационных технологий:

— IT-корпорации буквально охотятся за нашими выпускниками и в первую очередь за участниками мировых чемпионатов по программированию. Можно долго перечислять, сколько их работает в Google, Yandex, Intel. И главное — выпускники ФИТа сами выбирают работодателя.

Анастасия Аникина