Идея Google HashCode проста. Организаторы предлагают разработчикам решить реальную инженерную проблему, с которой команда Google сталкивалась в своей практике. Участники могут сами выбрать язык программирования и весь инструментарий для решения поставленной задачи. Главное – предоставить готовое решение проблемы. Чем точнее готовый код решает задачу, чем больше баллов набирает команда.
Чемпионат Google HashCode проходит в два этапа: квалификационный раунд в формате онлайн и финал. На каждом из этапов разработчики получают задачу, решение которой предстоит найти за ограниченное временя. Отличается такая форма состязаний от более знакомого ACM ICPC тем, что в последнем участникам необходимо решить дюжину задач, у которых заранее известно точное решение, а у задач Google HashCode нет однозначного ответа. Первый этап состязаний – глобальный отборочный тур перед заключительным этапом в штаб-квартире Google в Париже – был проведен еще 23 февраля. Все участники могли быть вовлечены в процесс дистанционно из любой точки мира. Программистам нужно было подумать над эффективным размещением видео на YouTube. Тогда организаторы предложили участникам описание серверов кэширования, сетевых конечных точек, сами видеозаписи вместе с предсказанными запросами пользователей на отдельные видео. Участникам нужно было разместить конкретное видео на определенном сервере кэширования таким образом, чтобы минимизировать среднее число времени ожидания для всех запросов.
В заключительном раунде сотрудники Google также предоставили участникам один из своих реальных проектов. Разработчикам крупнейшей компании пришлось столкнуться с проблемой распространения Wi-Fi сигнала на одном из этажей здания штаб-квартиры Google в Париже. Программистам нужно было наиболее эффективно (по цене и качеству покрытия) расположить Wi-Fi роутеры внутри здания и настроить систему кабелей.
На заключительный этап от Университета ИТМО поехали две группы программистов – представители кафедры компьютерных технологий Университета ИТМО. В команде Past Glory участвовали Геннадий Короткевич, Артем Васильев и Борис Минаев. По результатам заключительного раунда разработчики вошли в тройку лучших команд. Представленные судьям решения поставленной задачи позволили программистам занять второе место на чемпионате. В другой команде Университета ИТМО – ИТМО 1 – выступили Иван Белоногов, Илья Збань и Владимир Смыкалов. Работа на заключительном этапе чемпионата принесла ребятам четвертое место. Победителем в чемпионате стала команда российских разработчиков AIM Tech. Стоит заметить, что система оценки решений остается автоматической и непредвзятой. Например, в заключительном этапе оценивалось качество Wi-Fi покрытия и его полнота, поэтому результаты чемпионата говорят о том, что лидер смог решить задачу технически точнее и эффективнее.
По словам Ивана Белоногова, одного из участников команды ИТМО 1, в заключительном раунде обе части задания (и распределение роутеров по территории этажа, и настройка системы кабелей) показались интересными для команды, поэтому разработчикам удалось придумать несколько хороших идей по обоим направлениям.
«Времени было достаточно, и мы сделали почти все, что планировали. Мы не распределяли задачи внутри команды, у каждого была своя версия решения. У такого подхода есть свои плюсы. Во-первых, каждый мог быстро тестировать новые идеи и эвристики, не отвлекая остальных. Во-вторых, это существенно повышает надежность. Также мы смогли попробовать больше разных подходов к задаче», – рассказывает Иван Белоногов.
Участники команды Past Glory все же выявили для себя наиболее интересную часть работы. По словам Геннадия Короткевича, самой интересной и сложной задачей показалось оптимальное соединение роутеров в общую сеть. Разработчик сравнил этот процесс с «задачей Штейнера».
«Все тесты у нас решались одними и теми же программами, но вот сам алгоритм состоял из двух независимых частей: расположение роутеров и их соединение. Это было разумно, поскольку качество сети, соединяющей роутеры, намного больше зависело от качества алгоритма построения сети, чем от конкретного расположения роутеров», – поделился Геннадий Короткевич.
По словам участников команды ИТМО 1, соревнования такого типа действительно отличаются от олимпиад, к которым они привыкли готовиться.
«Достигать хороших результатов на таких соревнованиях особенно приятно, потому что конкретно к такому типу контестов мы не готовимся совсем. А это значит, что навыки и знания, полученные на тренировках к ACM ICPC, влияют и на смежные области. Поездки на такие олимпиады мы больше рассматриваем как смену деятельности и отдых», – поделился Иван Белоногов.
Сейчас идет активная подготовка разработчиков к финалу чемпионата по спортивному программированию ACM ICPC, который будет проходить в мае. Программисты тренируются ежедневно. По словам Ивана Белоногова, для успешного выступления в олимпиадах необходимы три основных навыка: знание алгоритмов, умение быстро писать много сложного кода с минимальным количеством ошибок и умение придумывать решение задач.
«С алгоритмами все относительно просто: это базовые инструменты, которыми мы пользуемся. Практически все, что может встретиться, мы знаем и умеем писать. А вот другие два навыка можно оттачивать до бесконечности. На тренировках мы обычно решаем задачи старых олимпиад и сборов», – заключил разработчик.
