Команда Университета ИТМО одержала победу на соревнованиях Google Hash Code 2018

В конце апреля в Дублине прошел финал соревнований по решению инженерных задач Google Hash Code 2018, ежегодно собирающих несколько десятков тысяч студентов и профессионалов в области программирования из Европы, стран Среднего Востока и Африки. Команда студентов Университета ИТМО, в которую вошли чемпионы мира по программированию 2017 года, магистранты кафедры компьютерных технологий Илья Збань и Иван Белоногов, бронзовый призер чемпионата этого года, студент второго курса бакалавриата кафедры КТ Михаил Путилин и серебряный и бронзовый призер чемпионата мира 2016 и 2014 годов, студент кафедры информационных систем Адам Бардашевич, одержала победу, обойдя 39 команд из 15 стран. В финале участникам предстояло решить оптимизационную задачу, целью которой было наиболее эффективным образом спроектировать город.

Первый Hash Code состоялся во Франции в 2014 году и собрал всего 200 участников. Год от года соревнования набирали популярность, и в 2017 году в чемпионате участвовало уже более 26 тысяч программистов из Европы, Среднего Востока и Африки. В этом году на первом этапе соревнований зарегистрировались 37 тысяч участников.

В отборочном туре участвовали в том числе две команды Университета ИТМО. Одна наполовину состояла из преподавателей кафедры компьютерных технологий – Андрея Станкевича, Павла Маврина, Павла Кунявского и Егора Куликова. В составе второй были студенты кафедры компьютерных технологий Иван Белоногов, Илья Збань, Михаил Путилин и студент кафедры информационных систем Адам Бардашевич. По итогам отборочного тура обе команды вошли в пятерку лучших и получили шанс побороться за первое место в финале соревнований.

Согласно правилам соревнований, в каждой команде может быть от двух до четырех человек. На соревновании командам предлагается решить одну оптимизационную задачу по типу тех, с которыми регулярно сталкиваются специалисты компании Google в реальной работе. Например, в первый год конкурса участники должны были составить наиболее оптимальный маршрут для автомобиля с камерой, который используется для создания Google Street View. Нужно было найти такой маршрут, чтобы автомобиль смог покрыть максимально большую площадь города за ограниченное время. А в прошлом году на отборочном этапе конкурса нужно было разработать алгоритм для наиболее оптимального размещения видео на YouTube, в том числе стримового, а в финале — распределить wi-fi-роутеры и кабели так, чтобы сигнал покрывал заданную площадь, при этом решение стоило бы как можно дешевле.

В отличие от задач Чемпионата мира по спортивному программированию ACM ICPC, у задач Google Hash Code нет однозначного ответа. Результаты необходимо загрузить в специальную систему, в которой ведется автоматический подсчет баллов, поэтому для команд главное – предоставить как можно более точное и верное решение. За качеством проведения соревнований следит жюри, состоящее из инженеров Google. Команды могут использовать любой язык программирования. Решение поставленной проблемы необходимо разработать за четыре часа.

По итогам отборочного этапа в финал Google Hash Code-2018, который проходил в Дублине 29 апреля, вышли 40 команд из 17 стран.

В этот раз участникам предлагалось решить задачу, позволяющую эффективно спроектировать город. Население мира растет и становится все более сосредоточенным в городах. По данным Всемирного банка, глобальная урбанизация в 2008 году превысила 50 % и достигла 54 % в 2016 году. Однако рост городских районов создает и нестандартные архитектурные проблемы. Организаторы соревнований предложили командам подумать, как градостроители могут эффективно использовать городское пространство и как следует сбалансировать потребности в жилых домах с доступом к коммунальным услугам, а также школам, больницам и паркам.

Победитем стала команда студентов Университета ИТМО, в которую вошли чемпионы мира по спортивному программированию 2017 года, студенты первого курса магистратуры кафедры компьютерных технологий Университета ИТМО Илья Збань и Иван Белоногов, бронзовый призер чемпионата этого года, студент второго курса кафедры КТ Михаил Путилин и серебряный и бронзовый призер чемпионата мира 2016 и 2014 годов, студент четвертого курса кафедры информационных систем Адам Бардашевич.

«Для решения этой задачи мы реализовали несколько жадных эвристик, и применили к ним метод локальных оптимизаций, – прокомментировал Илья Збань. – Оказалось эффективным не решать задачу, планируя большой город целиком, а решить ее для маленького квартала и замостить такими кварталами весь город — не очень жизненно, но эффективно в поставленной формулировке. Самым сложным для нас было понять, как вообще подойти к задаче: методы, которые сработали в итоге, не были очевидны с самого начала. Одержать победу нам помогла хорошо спланированная работа в команде: разделение подзадач между участниками и постоянный обмен идеями».

Команда, состоявшая наполовину из преподавателей Университета ИТМО (состав: Андрей Станкевич, Павел Маврин, Павел Кунявский и Егор Куликов), заняла пятое место. Стоит отметить, что весь топ-5 Google Hash Code в этом году остался за командами из России. Тройка лучших команд получает призы и сертификаты от компании Google.