ВКонтакте запускает третий чемпионат VK Cup

Всем привет! Социальная сеть ВКонтакте возвращает свой блог на Хабр.

Первое, о чём хотим рассказать, — чемпионат по спортивному программированию VK Cup 2016 и разбор нескольких интересных задач с прошлого года.

2497313ccd604aa1848867d3e831b54d.png


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

К участию в нём приглашаются команды из двух человек (можно участвовать и индивидуально), чей возраст от 14 до 23 лет. Отборочные этапы пройдут с марта по май, а в финал будут приглашены лучшие 20 команд. Финал пройдет в Санкт-Петербурге в июле, лучшие восемь команд будут награждены призами:

1 место — 1048576 рублей
2 местo — 524288 рублей
3 местo — 262144 рубля
4–8 места — 131072 рубля

Соревнование будет проходить на площадке Codeforces, регистрация уже открыта — спешите зарегистрировать команду! Начать своё участие необходимо с квалификационных этапов, которые будут проходить 13–14 и 20–21 марта. Участвовать можно как в двух, так и в любом из них. Все подробности доступны по ссылке на странице Чемпионата.
Чемпионат VK Cup с одной стороны следует традициям чемпионатов по программированию, предлагая участникам задачи на алгоритмы и структуры данных. С другой, стороны мы стараемся расширить формат. Так, в ходе чемпионата прошлого года были проведены два необычных раунда (уайлд-кард раунды 1 и 2).

На первом из них участникам предлагались простые задачи, но язык, на котором можно их решать, они узнали только в момент старта раунда. Языком раунда оказался малоизвестный язык Picat. За два часа соревнования участникам надо было изучить основы этого языка и решить несколько задач на нем. Например, одна из задач была о вычислении расстояния Левенштейна.

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

* замена: стоимость замены одного символа на другой равна разности порядковых номеров этих символов в алфавите.
* вставка/удаление: стоимость вставки символа в строку или удаления символа из строки равна порядковому номеру этого символа в алфавите.

Вам даны две строки. Найдите расстояние Левенштейна между ними.


Вот такое решение прислал один из участников:

Решение на Picat
~~~~~
table(+, +, min)
edit(I, J, Cost) ?=>
    str(S), goal(G),
    N = length(S), M = length(G),
    (
        I <= N, J <= M,
        edit(I + 1, J + 1, NextCost),
        Cost = abs(ord(S[I]) - ord(G[J])) + NextCost
    ;
        I <= N,
        edit(I + 1, J, NextCost),
        Cost = ord(S[I]) - 0'a + 1 + NextCost
    ;
        J <= M,
        edit(I, J + 1, NextCost),
        Cost = ord(G[J]) - 0'a + 1 + NextCost
    ;
        I > N, J > M,
        Cost = 0
    ).

main =>
    S = read_line(), G = read_line(),
    cl_facts([$str(S), $goal(G)]),
    edit(1, 1, Cost),
    println(Cost).
~~~~~


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

А вот пример уже задачи классического формата с первого квалификационного раунда.

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

Известно, что каждый сервер пережимает минутный фрагмент за одну секунду. Таким образом, на любом из серверов видеофайл длительностью m минут пережимается за m секунд.

Известно время загрузки в соцсеть каждого из n роликов (в секундах с момента общего старта серверов). Все ролики поступают в разные моменты времени и обрабатываются в порядке поступления. Если ролик поступил в момент времени s, то его можно начать обрабатывать сразу же в этот момент. Некоторые из роликов могут ожидать обработки из-за занятости всех серверов. В таком случае как только какой-либо сервер освободится, он сразу же начнет обрабатывать очередной ролик. Ожидающие обработки ролики складываются в очередь. Если к моменту начала обработки свободны несколько серверов, то его начинает обрабатывать любой из них.

Для каждого из роликов определите момент окончания его обработки.

Входные данные
В первой строке входных данных записаны целые числа n и k (1 ≤ n,  k ≤ 5·10^5) — количество роликов и серверов соответственно.

Далее в n строках следуют описания роликов парами целых чисел s_i,  m_i (1 ≤ s_i,  m_i ≤ 10^9), где s_i — время в секундах, когда пришел i-й ролик, а m_i — его длительность в минутах. Гарантируется, что все s_i различны и ролики заданы в хронологическом порядке загрузки, то есть в порядке увеличения s_i.

Выходные данные
Выведите n чисел e_1,  e_2,  …,  e_n, где e_i — время в секундах от начала работы серверов, когда i-й ролик будет обработан.


Полный текст условия доступен по ссылке. Там же можно попробовать самостоятельно решить и отослать решение на проверку. Для самых нетерпеливых вот описание решения.

Описание решения
Заведем очередь с приоритетами, будем хранить там ближайшее время освобождения каждого из k серверов. Таким образом, в очереди в любой момент времени будет ровно k элементов. Если стандартная библиотека языка не имеет встроенной очереди с приоритетами, то можно просто использовать упорядоченное множество или кучу. Важно, чтобы операции изъятия минимума и добавления элемента работали не дольше логарифма. Тогда при обработке очередного ролика s_i, m_i легко понять, что он будет обработан в момент e_i=max (s_i, A)+m_i, где A — минимальное время освобождения по всем серверам, то есть число в голове очереди с приоритетами (или на вершине кучи или множества). Таким образом надо вывести e_i, удалить из головы очереди элемент и затем добавить туда e_i.

Вот основная часть такого решения на языке С++:

priority_queue, std::greater> q;
int n, k;
scanf("%d %d", &n, &k);
for (int i = 0; i < k; i++)
    q.push(0);
for (int i = 0; i < n; i++)
{
    long long s, m;
    scanf("%lld %lld", &s, &m);
    s = max(s, q.top()) + m;
    printf("%lld\n", s);
    q.pop();
    q.push(s);
}


Ждём вас на VK Cup 2016! Самое время зарегистрировать команду и подключиться к квалификационному раунду. Если не успеете принять участие в первом, то можете участвовавать во втором, который состоится 20–21 марта. Удачи!

© Habrahabr.ru