Соревнования Google Code Jam являются одними из самых массовых в мире и ежегодно собирают около 50 тысяч участников, из которых примерно половина проходит квалификационных раунд. До финала в этом году добрались 26 программистов, которые поборолись за главный приз в 15 тысяч долларов. Геннадию Короткевичу, как победителю Google Code Jam прошлого года, не пришлось участвовать в отборе.

Особенность чемпионата в том, что участники решают задачи, состоящие из двух «половинок». Первую можно условно назвать более легкой для участника, так как для ее решения подходит менее эффективный алгоритм, а перед программистом стоит меньше ограничений. Кроме того, как только он отправил решение, ему сразу же приходит ответ, верное ли оно. Если нет, то у программиста есть возможность исправиться. А вот вторая «половинка» каждой задачи требует уже более сложных алгоритмов, кроме того, правильность их решения участник узнает только на церемонии награждения победителей. Отличительная черта турнира еще и в том, что программисты могут использовать для решения любой язык программирования.

Google Code Jam. Источник: социальные сети
Google Code Jam. Источник: социальные сети

В этом году финалисты Google Code Jam должны были решить шесть задач. При этом одна из них не была разделена на «половинки». Как следует из официальной аналитики соревнований, большинство участников сначала решали легкие «половинки» задач, а потом уже переходили к сложным. В конце турнира организаторы разобрали решения всех задач, а результаты подсчитывались в режиме реального времени на глазах всех участников. Геннадий Короткевич в четвертый раз подряд занял первое место, набрав 120 баллов из 200 возможных, а Евгений Капун – четвертое место, получив 100 баллов. При этом Геннадий Короткевич два с половиной часа не выдавал ни одного решения, зато в следующие полтора часа предоставлял одно решение за другим.

«Первые два с половиной часа я потратил на то, чтобы прочитать и понять условия всех задач. Стало сразу понятно, что нужно делать в задачах А и В, поэтому их можно было отложить. Решил задачу С, но думал в основном над последними задачами. Примерно понял, что, чтобы написать и отправить все решенное, понадобится около полутора часов. Например, нужно было написать одно из решений на Java, а там еще и задача на вычислительную геометрию, требующая скрупулезного написания. Самой же сложной для меня была задача про путешествия на самолетах. Был дан маршрут перелетов между аэропортами, нужно было проверить, что маршрут действительно кругосветный», – прокомментировал победитель.

В соревнованиях также учитывается общее время решения задач: так, три участника, разместившиеся на втором, третьем и четвертом местах, набрали по 110 баллов. 

Геннадий Короткевич является двукратным победителем международного чемпионата мира по программированию ACM ICPC (2013 и 2015 годов), точно так же, как и Евгений Капун (2009 и 2012 годов).

«Я по максимуму стараюсь решать сложную половину задачи, потому что решение более общей задачи почти всегда решает более частную. В этом году, тем не менее, за два часа у меня не получилось решить сложные версии трех последних задач, и я переключился на их “легкие” части. В такой ситуации я ожидал, что кто-то из финалистов сможет решить “сложные”, и обойдет меня по очкам», – описал свою тактику решения задач контеста Google Code Jam Геннадий Короткевич.

В Дублине также состоялись соревнования Distributed Code Jam, которые организует компания Google третий год подряд. Задачи этого турнира похожи на задачи традиционного Code Jam, но для их решения программисты могут использовать только распределенные вычисления (это когда необходимо работать с несколькими процессами на разных компьютерах, которые можно объединить в систему). Точно так же, как и обычный Code Jam, Distributed Code Jam направлен на развитие навыков, необходимых для работы в крупных IT-компаниях. Победители чемпионата получают денежный приз в 10 000 долларов.

Турнирная таблица
Турнирная таблица

В этом году в финале выступили 21 человек. Евгений Капун занял второе место, а тьютор кафедры компьютерных технологий Павел Маврин (чемпион ACM ICPC 2004 года) занял четвертое место. Он смог полностью решить две задачи (обе «половинки»), а также «легкую» часть третьей задачи, набрав 48 баллов из 100 возможных. При этом победитель турнира набрал 59 баллов.

«Подготовиться к соревнованиям было достаточно сложно. Оно проходит в достаточно специфической инфраструктуре, поэтому просто запустить у себя на компьютере решение и посмотреть, сколько времени оно будет работать, не получится. Но в этом и интерес! Мне понравилась, хотя не показалась невероятно сложной, задача про робота на клетчатом поле. В каждой клеточке поля нарисована стрелка вверх, вниз, вправо или влево. Робот может стартовать в любой из клеток и будет двигаться по стрелкам, а, значит, в какой-то момент либо свалится с поля, либо зациклится. Нужно заменить некоторые стрелки на финиш, чтобы, где бы робот ни стартовал, он придет в финиш. Понятно, как решается эта задача на маленьком поле, но в большом варианте задачи поле имеет размер 30000 х 30000 клеток», – прокомментировал Павел Маврин.

Как следует из аналитики, первые две задачи решили полностью почти все участники, а вот «сложную» часть четвертой и пятой задач не смог решить никто. При этом уровень финалистов Distributed Code Jam повышается с каждым годом, подчеркнули организаторы.