Подведены итоги Facebook Hacker Cup. Соревнование, в котором приняли участие 11768 человек со всего мира, проходит в формате решения сложных алгоритмических задач в три раунда «на вылет». Двадцать пять финалистов были приглашены в штаб-квартиру Facebook в Пало-Альто для последнего состязания.В финал попали 7 представителей Польши, 6 — из России, 4 — из США, 2 — из Японии и по одному из Китая, Германии, Нидерландов, Сингапура, Швейцарии и Украины. Все они смогли провести 2 дня в офисе Facebook: встретиться с разработчиками, пообедать в Cafe X, поиграть Catan и попытаться прокатиться на RipStik.
Участники имели возможность выбора машины (Mac или PC), после чего начался финальный раунд. От финалистов требовалось решить три алгоритмические задачи: Party Time, Safest Place и Alien Game — как можно быстрее.
Результаты представляются на суд по мере готовности решения для каждой из задач, и по окончании двухчасового раунда подсчитвается итоговое количество баллов для каждого участника.
Условия задач можно посмотреть в блоге Facebook Engineering (впрочем, если будет спрос — я могу попробовать перевести их позже).
В итоге «золото» досталось нашему соотечественнику Петру Митричеву (участнику и призеру многих аналогичных соревнований).
UPD #1 — интересные подробности от Skiminok:
Добавлю ещё, что там была потрясающая интрига касательно победителя.
Главный соперник Митричева — Lou Tian Cheng, также известный как ACRush.
Принцип этого соревнования таков, что каждая из трех задач оценивается в 1 очко, и в турнирной таблице выше тот, у кого больше сдано задач, а при равенстве выше тот, у кого суммарное время, потраченное на каждую задачу с начала раунда, ниже. При этом финальная проверка ответов происходит только после того, как раунд закончится.
Так вот, ACRush опережал Митричева на протяжении всего раунда. Митричев сдавал те же задачи, по количеству они всегда были одинаковы — но ACRush сдавал их быстрее, мы уже и не надеялись на победу Пети. И тут раунд заканчивается, происходит финальная проверка, и у ACRush падает одна из задач с неправильным ответом, и он оказывается с двумя очками, и опускается на два места, пропуская вперед Петю с тремя решенными медленнее, но правильно.
UPD #2 — перевод собственно задач (опять же спасибо Skiminok)
Задача 1. Игра инопланетян.
На Неизвестной планете инопланетяне традиционно играют в игру под названием Loiten. В ней учавствуют два игрока, которые ходят по очереди. Перед игроками в ряд выстроены N корзин с яблоками. Они пронумерованы слева направо целыми числами, начиная с 1.
Каждый ход заключается в том, что игрок выбирает одну из корзин, которая не первая и не последняя в ряду, и в которой положительной число яблок, и перекладывает все яблоки в этой корзине в соседнюю слева корзину, и в то же время одновременно переносит их все в соседнюю справа корзину. Да, на этой действительно странной планете число яблок может быть отрицательным. Так, если имеется 3 последовательные корзины, в которых соответственно x, y, z яблок, то с ними можно произвести ход, если y больше нуля. В результате после хода в корзинах будут следующие количества: x+y, -y, z+y. Проигрывает тот игрок, который не может сделать ход.
Вы знакомы с одним из жителей Неизвестной планеты, по имени Попо. Он отличный игрок в Loiten, и прошел в финал чемпионата планеты по Loiten`у. За день до игры он как-то выяснил, сколько будет яблок в каждой из корзин. К сожалению, у него не слишком хорошая память, и он забыл количество яблок в корзине под номером P. Он помнит только, что это число по модулю не превосходит F.
Сейчас, он просит вас просчитать его шансы на победу. В финал чемпионата проходят настолько хорошие игроки, что они всегда делают только оптимальные ходы для максимизации собственного шанса на выигрыш. Если ни один из игроков не может выиграть, засчитывается ничья. Вам необходимо узнать число возможных количеств яблок в корзине №P, при которых Попо выигрывает. Попо также уверен, что именно он делает первый ход в игре.
Входные данные
Первая строка входных данных содержит единственное целое число T, количество тестов. Каждый тест начинается со строки, содержащей два целых числа: N, количество корзин, и P, номер корзины с неизвестным числом яблок. В следующей строке содержится N целых чисел — количества яблок в соответствующих корзинах. P-е число в этой строке — положительное целое F, соответствующее ограничению на число яблок в P-й корзине.
Выходные данные
Выходной файл должен содержать T строк, по одной на тест. В каждой строке — ответ на соответствующий тест, количество возможных выигрышных значений числа яблок для P-й корзины.
Ограничения
T = 50
1 ≤ P ≤ N ≤ 2,000.
1 ≤ F ≤ 1,000,000,000,000.
Перед началом игры количество яблок в каждой корзине по абсолютному значению не превосходит 1,000,000,000,000.
Задача 2. Безопасное место.
По дороге на 295-ю годовщину Большой Галактической Вечеринки вас внезапно бесцеремонно вышвырнуло из гиперпространства и теперь, если верить сенсорам, вы окружены N космическими бомбами. Несомненно, вы попали в ловушку, подстроенную каким-то неизвестным подлым врагом, вернуться в гиперпространство вы не можете, и теперь вам предстоит найти самое безопасное место в окрестностях, чтобы пережить взрыв всех бомб. Вам незримый соперник создал космическую аномалию в форме куба, за пределы которой вы не можете вылететь, так что в качестве варианта расположения вам доступны только точки в пределах этого куба.
Перед тем, как все бомбы одновременно взорвутся, у вас есть достаточно времени, чтобы добраться до любой целой точки в пределах куба [0, 0, 0]-[1000, 1000, 1000], включительно. Вам нужно найти точку, у которой расстояние до ближайшей бомбы максимально, так как ваша интуиция подсказывает, что это будет самое безопасное место.
Входные данные
Первая строка входных данных содержит единственное целое число T, количество тестов. Каждый тест начинается целым числом N, количеством бомб, за которым следуют 3*N целых чисел, задающих координаты каждой бомбы.
Выходные данные
Выходной файл должен содержать T строк, по одной на тест. В каждой строке — квадрат расстояния до ближайшей бомбы от самой безопасной точки в кубе.
Ограничения
T = 50
1 ≤ N ≤ 200
Все координаты бомб лежат в пределах [0, 1000] включительно.
Задача 3. Время для вечеринки
Вы устраиваете вечеринку для своих друзей, но поскольку не все из ваших друзей знают друг друга, вы опасаетесь, что некоторым из них вечеринка может не понравиться. Чтобы избежать такой ситуации, вы решили также пригласить несколько друзей своих друзей. Но кого же именно пригласить, чтобы получилась отличная вечеринка?
К счастью, вам известны подробности обо всех отношениях между вашими друзьями и друзьями ваших друзей. В терминах теории графов, есть подграф G социального графа, чьи вершины соответствуют вашим друзьям и их друзьям (не считая вас), а ребра графа означают взаимную дружбу. Более того, вам удалось установить в точности, сколько еды съест на вечеринке каждый человек из G, если будет приглашен.
Вы хотите выбрать множество гостей из G. Это множество гостей должно содержать всех ваших друзей, и, кроме того, подграф G, образованый гостями, должен быть связен. Вам кажется, что этого будет достаточно, чтобы всем понравилась вечеринка, так как любым двум гостям будет о чем поговорить…
Чтобы сэкономить деньги, вы решили выбрать такое множество гостей, чтобы необходимое общее количество еды было как можно меньшим. Если этого можно достичь несколькими разными способами, предпочитается способ с наименьшим числом гостей.
Люди/вершины в вашем подмножестве G социального графа пронумерованы от 0 до N — 1. Также, для удобства, ваши друзья имеют номера от 0 до F — 1, где F — количество друзей, которых вы хотите пригласить обязательно. Можно также считать, что G всегда связен. Еще раз напоминаем, что лично вы никак не представлены в G.
Входные данные
Первая строка входных данных содержит единственное целое число T, количество тестов. Первая строка каждого теста содержит три целых числа: N — количество вершин в G, F — количество ваших друзей, и M — количество ребер в G. Далее следует M строк, по два целых числа в каждой. I-я такая строка содержит два разных целых числа u и v, что означает взаимную дружбу между человеком №u и человеком №v. После этого, последняя строка теста содержит N целых чисел через пробелы, где i-е число есть количество еды, необходимое человеку №i.
Выходные данные
Выходной файл должен содержать T строк, по одной на тест. В каждой строке — два числа через пробел: минимальное общее количество еды для вечеринки, удовлетворящей вышеприведенным условиям, и минимальное количество человек на такой вечеринке.
Ограничения
T = 50
1 ≤ F ≤ 11
F ≤ N-1
2 ≤ N ≤ 250
N-1 ≤ M ≤ N * (N — 1) / 2
G связен, и не содержит петель или кратных ребер.
Для каждого человека нужное ему количество еды — целое число от 0 до 1000 включительно.
