Отдел новостей 6 января 2011, 01:08

Facebook Hacker Cup

Не так давно Facebook объявил о проведении соревнования со странным названием Hacker Cup. И если сначала никакой конкретной информации по самому соревнованию почти не было, то сейчас есть вполне внятный FAQ и очень подробные и точные terms & conditions. Я постараюсь рассказать, что это за Hacker Cup, начинающийся 7 января, и с чем его едят. Самое основное, что можно вынести из изучения подробностей: Facebook решил проводить свое ежегодное алгоритмическое соревнование. При этом, видимо, решив, что от добра добра не ищут, ребята из Facebook пока что делают соревнование, очень схожее с ежегодным Google Code Jam (Не удивлюсь, что соревнованием занимается кто-нибудь из бывших гуглеров, организовывавших Google Code Jam). Для начала самый главный вопрос:

Что нужно делать во время соревнования?

Каждый этап соревнования будет содержать три алгоритмические задачи. Для каждой задачи будут даны: условие, ограничения, форматы входных и выходных данных, а также файл со входными данными. В качестве решения нужно предоставить результат выполнения программы в виде файла с выходными данными, а также исходные тексты программ, использовавшихся для нахождения ответа. Процесс для отдельно взятой задачи следующий: читаем условие, придумываем и пишем решение, тестируем (нет, ну можно, конечно, тестирование пропустить, но не советую :)), затем скачиваем файл со входными данными. С этого момента у нас есть ровно 6 минут, чтобы послать ответ. Ответ можно посылать несколько раз, засчитываться будет последний посланный в эти 6 минут. Если по истечении этого времени мы так и не послали результат, то по этой задаче получаем ноль и можем к ней уже не возвращаться. Если послали, то, похоже, придется ждать конца соревнования, чтобы узнать правильный ли ответ мы прислали. Задачи можно решать и сдавать в произвольном порядке в течение всего времени соревнования.

Какие средства можно использовать?

Писать можно на любом языке программирования по вкусу, с тем условием, что организаторы должны имет физическую возможность собрать и выполнить нашу программу (или несколько программ), используя IDE/компиляторы/системы сборки, которые существуют в свободном доступе. Особым пунктом идет разрешение на использование MS Visual Studio, так как в свободном доступе есть Visual Studio Express. Все исходные коды, использовавшиеся для решения должны быть отосланы одновременно с выходным файлом. В правилах разрешено решать задачи даже руками, при условии, что вместе с ответом присылается описание решения в текстовом файле.

Оценка решений

Тут все просто. Задача решена правильно — получаем одно очко. Важный момент в том, что все задачи оцениваются одинаково, хотя по сложности они могут и различаться. Результат в соревновании — это количество правильно решенных задач. Если количество задач у участников совпадает, то смотрят штрафное время. Штрафное время — это время отсылки последней правильно решенной задачи.

Структура соревнования, призы

Квалификационный раунд начинается 7 января и будет длиться 72 часа. За это время нужно будет правильно решить хотя бы одну из предложенных задач. Еще раз замечу, что, во-первых, после скачивания входного файла у нас будет только 6 минут на отсылку ответа вместе с исходниками, поэтому забирать входной файл нужно только после того, как решение протестировано и есть уверенность в его правильности; а во-вторых, узнать правильно ли решена задача или нет, похоже, во время соревнования будет невозможно.
Первый раунд будет состоять из 3 отдельных подраундов, каждый из которых будет длиться 3 часа. Лучшая 1000 человек из каждого подраунда выходит во второй раунд соревнования. При этом участвовать можно хоть во всех трех подраундах, при условии, что вы еще не попали в Top-1000 в одном из предыдущих подраундов. Таким образом во второй раунд выходит 3000 человек.
Второй раунд будет длиться все те же 3 часа. Top-300 человек получат футболки, Top-25 поедут в Headquarters Facebook, в Palo Alto участвовать в финальном раунде.
Участникам финала оплачивается поезда, проживание, и всякая еда. И эти 25 счастливчиков будут бороться за обладание званием победителя Hacker Cup и довольно скромный призовой фонд (победитель получает $5000, второе место — $2000, 3-е — $1000, остальные по сто баксов).

Кто может участвовать?

Участник должен быть зарегистрирован на Facebook. Ему должно быть как минимум 18 лет, он не должен являться сотрудником Facebook, ну и еще несколько экзотических ограничений типа территориальной принадлежности Квебеку :)

Мысли вслух

Во-первых, наверное, сразу надо предложить собственную версию того, почему призовой фонд соревнования настолько мал (он точно такой же и в Google Code Jam). Мне кажется, что организаторы хотят все же привлечь людей, которые просто любят программировать и решать головоломки вне зависимости от того, заплатят им за это или нет. Плюс к этому большой призовой фонд привел бы к увеличению читинга в разных формах. А бороться с ним иногда в таких масштабах (а индусов будут тыщи, уж поверьте :)) довольно непросто. Во-вторых, интересно то, что многие из взрослых топовых участников подобных соревнований (IOI, ACM ICPC, TopCoder, GCJ, etc) работают сейчас в Google, поэтому они не имеют права участвовать в Google Code Jam (GCJ), а вот в Hacker Cup они все участвовать смогут, так что борьба будет нешуточная :) В-третьих, позволю себе сравнить правила Hacker Cup с правилами GCJ. Похоже, ребята из Facebook решили не заморачиваться и по максимуму упростили правила: В гугловском соревновании мало того, что задачи оцениваются разным количеством баллов, так еще и для каждой задачи есть два набора входных данных, простой и сложный, с разными ограничениями. Это позволяет решать задачу различными методами, зарабатывая разное количество очков. Более того, в GCJ для простого набора данных можно много раз посылать решение и сразу же видеть, правильное оно или нет. А так как в этот простой набор обычно включают различные частные случаи, это минимизирует количество различных глупых ошибок, допускаемых участником, и посланное решение для сложного набора с большей вероятностью оказывается правильным. В Hacker Cup все будет предельно жестко, допустил хоть одну ошибку — получил ноль за задачу, и возможности что-то исправить не будет. Также в гугловских правилах есть много довольно продуманных мелочей, которые в Facebook решили выбросить. Выиграет ли от этого соревнование? Сильно сомневаюсь. Ну, а самое неприятное для меня лично, как для потенциального участника, что во время соревнования, похоже, не будет никакой online таблицы, поэтому придется посылать задачи вслепую, не видя, что и как быстро сдают соперники. Наличие живой таблицы вносит в соревнование азарт, а тут, похоже, мы этого лишаемся. Но в любом случае, это всего лишь первый блин у Facebook, поэтому пожелаем им удачи и дальнейшего развития. Все-таки общемировые соревнования, проводимые крупными компаниями — это повод размять пальцы и мозги для довольно большого числа программистов, как будущих, так и состоявшихся. Всем удачи! Спасибо, что дочитали до конца :)