Финал Facebook Hacker Cup 2012. В основном виды прилегающей местности.

Фото здесь.

Финал TopCoder Open в Голливуде (Флорида, США) 25 - 29 сентября 2011 года.

Финал Russian Code Cup в Москве 17-18 сентября 2011 года.

Фото здесь.

Поездка сборной команды Поволжья на финал Google Code Jam 2011 в Токио.

A. Башни
Общее количество башен равно количество различных чисел в данном наборе. Чтобы получить высоту наибольшей башни, можно было подсчитать для каждой длины количество брусков с такой длинной, и из этих чисел выбрать максимальное.

B. Компьютерная игра
Ограничения в задаче позволяли решать её следующим образом: будем хранить текущее количество здоровья у босса, и суммарный наносимый урон по нему. На очередном шаге выберем из еще не использованных свитков такой, который можно использовать на текущей секунде. Из всех таких, найдем свиток, который наносит больше всего урона, и применим его. Если в какой-то момент мы не смогли использовать ни один из свитков, и суммарный урон не превышает регенерацию, то выводим, что ответа не существует. Иначе продолжаем итерировать алгоритм, пока количество жизни босса не станет неотрицательным.

C. Древнеберляндский язык
Одно из самых простых для понимания решений в данной задаче выглядит так: отсортируем строки по возрастанию длины, при этом запомнив их номер в исходном списке. Будем последовательно строить наш набор, начиная с самых коротких строк: строками длины один могут быть только строки “0” и “1”. Если количество строк длины один в наборе больше двух, следовательно, ответа не существует. Добавим нужное количество строк длины один в ответ на свои места (для этого мы запомнили их номера), и удалим из текущего списка. Затем посмотрим на строки длины два: каждую из оставшихся строк длины 1 можно продолжить двумя способами (дописав к каждому из них символы 0 и 1). Добавим нужное количество строк длины два в наш набор, и снова увеличим длину оставшихся строк на единицу. Будем продолжать этот процесс до тех пор, пока не составим набор целиком. Можно заметить, что если в какой-то момент число допустимых строк превысило количество оставшихся, то лишние строки можно проигнорировать и таким образом время работы составит O(N * максимальную длину из входного набора).

D. Расписание занятий

Эта задача решается методом динамического программирования:

состоянием динамики будет пара чисел – номер аудитории и количество групп, занимавшихся на первой паре в аудитории с номером не превосходящем текущего, для которых вторая аудитория еще не определена. Для каждого состояния будем перебирать количество групп, у которых вторая пара будет проходить в текущей аудитории. При добавлении ответа из нового состояния, нужно домножить его на соответствующие биномиальные коэффициенты (количество способов выбрать группы, у которых первая пара будет в следующей аудитории - X_i + 1, и количество способов выбрать группы, у которых вторая пара будет в текущей аудитории).

E. Испытание для вождя

Сперва по данной раскраске построим следующий граф: каждой клетке сопоставим вершину того же цвета, что и сама клетка. Между соседними клетками проведем ребро веса 0, если клетки одного цвета, и веса 1, если разного. Теперь для каждой клетки посчитаем кратчайшее расстояния из нее, до самой удаленной черной клетки (обозначим его D). Нетрудно видеть, что можно построить последовательность из D + 1 перекрашивания приводящую к искомой раскраске:

• на первом шаге покрасим все клетки на расстоянии меньше либо равном D в черный цвет

• на втором шаге покрасим все клетки на расстоянии меньше либо равном D - 1 в белый цвет

• и т. д.

Из всех клеток, выберем ту, для которой это расстояние минимально, и это расстояние увеличенное на единицу будет ответом на задачу.

• Русская версия
• Английская версия