Про Google Code Jam

Google Code Jam (GCJ) — это соревнования по программированию, организованные компанией Google. Вообще, многие крупные компании проводят свои соревнования по программированию для всех (или почти всех) желающих — Яндекс.Алгоритм, Mail.Ru Russian Code Cup, VkCup, Facebook HackerCup, может, я кого забыл — но GCJ, на мой взгляд, один из наиболее интересных и адекватных. Соответственно, я советую всем, кто имеет уровень 2В или выше, и кто готов читать все тексты (условия, правила и т.д.) на английском языке, или кто умеет пользоваться онлайн-переводчиком, в нем участвовать.

Формат

GCJ проходит в несколько раундов (см. официальное расписание):

квалификационный раунд — 6 апреля
раунд 1, состоящий из трех подраундов: 1A, 1B и 1C — с 13 апреля по 4 мая
раунд 2 — 18 мая
раунд 3 — 8 июня
финальный раунд — 9 августа

(Еще есть Distributed Code Jam, это немного отдельная вещь.)

Все раунды проходят онлайн, кроме финала, который проходит в одном из офисов Гугла.

В квалификационном раунде могут участвовать все желающие. Квалификационный раунд длится 27 часов, можно начать писать в любое время, обычно написание раунда занимает 1-3 часа. Все, кто набрал больше заранее определенного количества баллов, проходят в раунд 1. Обычно пройти в раунд 1 достаточно легко.

В раунде 1 есть три подраунда, проводимые в разное время. В раунда 1A могут участвовать все, кто прошел квалификацию, 1000 лучших проходят в раунд 2. В раунде 1B могут участвовать все, кто прошел квалификацию, кроме тех 1000 человек, кто уже отобрался в раунд 2; 1000 лучших из раунда 1B проходят в раунд 2. В раунде 1C все аналогично: могут участвовать все, кто прошел квалификацию, кроме тех 2000 человек, кто уже отобрался в раунд 2; 1000 лучших из раунда 1C проходят в раунд 2. Итого в раунд 2 проходят 3000 человек. Обычно в раунде 1 не очень сложные задачи, но уже и не совсем уж простые; пройти в раунд 2 вполне реально.

1000 лучших в раунде 2 получают в подарок футболки (их потом в течение полугода высылают почтой); 500 лучших из раунда 2 проходят в раунд 3. В раунде 2 уже обычно довольно сложные задачи, пройти в раунд 3 (да даже получить футболку) — это весьма неплохой (для среднего олимпиадника) результат.

25 лучших из раунда 3 проходят в финал.

Структура раунда

В каждом раунде предлагается несколько (обычно 3-5) задач. Задачи имеют довольно стандартный тип: надо считать какие-то данные и вывести какое-то решение. Но есть два крупных отличия.

Во-первых, в каждой задаче в каждом входном файле есть несколько тестов (это называется мультитест). Т.е. вам сначала вводится количество тестовых примеров, и дальше вы считываете эти примеры и выводите ответы на них. Такая система на самом деле нередко встречается и на других олимпиадах.

Во-вторых, в каждой задаче тут обычно только два таких мультитеста — "маленький" (обычно с маленькими ограничениями) и "большой". Вы пишете программу, и, когда считаете, что она у вас готова, отправляете ее в "маленький" тест. Вам сообщают результат тестирования — все ли подтесты вы прошли или нет.

Если не все, то вы можете работать над задачей дальше — искать ошибки и т.д. Когда захотите, вы сможете опять сдавать в "маленький" тест. И так далее, пока наконец вы не сдадите правильный ответ.

После того, как вы решили маленький тест, вы можете решать большой. Результат большого теста вам будет сообщен только после тура.

Конечно, решать задачи вы можете в произвольном порядке, в том числе вы можете сдать маленький тест по одной задаче и переключиться на другую задачу и т.п.

Каждый успешно сданный тест (что маленький, что большой) оценивается определенным, указанным в условии, количеством баллов (разным за разные тесты). Ваш итоговый балл равен сумме баллов за все успешно сданные тесты. В итоговой таблице участники сортируются по баллам, при равных баллах — штрафному времени, которое равно времени последней успешной посылки плюс некоторый штраф за каждую неудачную попытку решить маленький тест (наверное, учитываются только те тесты, которые вы в итоге решили, но я не уверен — почитайте полные правила на сайте).

Во время тура вам доступна полная текущая таблица результатов, составленная из предположения, что все попытки по большим тестам были успешными (т.е. каждая попытка по большому тесту показывается как успешная, даже если на самом деле она не успешная). Окончательная таблица становится доступна вскоре после конца тура.

Как участвовать?

Заходите на http://code.google.com/codejam, регистрируетесь и участвуете. Надо логиниться с каким-нибудь гугловым аккаунтом (это не обязательно должен быть гмейл). Всё в общем-то понятно, но всё по-английски.

Старые задачи

На самом же сайте GCJ можно порешать старые задачи, там же можно найти разборы и решения других участников. Рекомендую потренироваться именно на сайте GCJ, чтобы освоиться с форматом.

Кроме того, они есть в тренировках на codeforces, хотя там их и непросто найти. Вот, например, 2015 год:

Формат там более привычный — сдаете программу, она проверяется на примере, маленьком и большом тестах.