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

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


Несколько слов о Чемпионате. ВКонтакте проводит третий 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<long long, std::vector<long long>, std::greater<long long>> 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 марта. Удачи!

Комментарии (8)


  1. Jeditobe
    13.03.2016 23:13
    -4

    Всем привет, кто в этом чате! Приходите на наш хакатон в Ставрополе!

    https://habrahabr.ru/company/reactos/blog/279139/


    1. littleone
      13.03.2016 23:24
      +2

      Это уж слишком!


      1. Jeditobe
        13.03.2016 23:26
        -2

        Вынужден идти на крайние меры. Мероприятие уже на носу, а список по иногородним участникам на гостиницу нужно утвердить как можно раньше.

        И кстати, у нас нет возрастных ограничений от слова "вооообще".


  1. AleksDesker
    14.03.2016 05:19
    +9

    Раз… раз… готов поклясться, секунду назад здесь было 3 комментария. Нечто пожирает комменты?


    1. valera5505
      14.03.2016 07:54

      Причем в боковой панельке ("Блог на Хабрахабре") 4 комментария, при заходе на эту страницу написано "Комментарии (4)", а если нажать кнопку обновления комментариев, то в скобках будет единица.
      Либо какой-то баг, либо комментарии теперь удаляют в обход НЛО
      UPD. Теперь комментариев 5


    1. littleone
      14.03.2016 10:54

      Да, точно! Это я оставил комментарий, но его больше нет даже в моем профиле.


    1. littleone
      14.03.2016 10:57

      Хабр точно деградирует. Компания превратилась в место для рекламы и бюрократии.


    1. Boomburum
      14.03.2016 11:33
      +2

      Комментарии с нарушением правил сайта удаляются, вместе с ними пропадают те, что были написаны под ним. Донт паник )


      1. vlivyur
        14.03.2016 13:32

        А пересчитывать их количество не надо? Меня уверяют что их тут 10 на данный момент. Но даже с моим комментарием столько не наберётся.


  1. TheTony
    14.03.2016 08:42

    Никак не могу сообразить, как определяется сумма 131072 р. (остальные умножаются на 2х, видно)?
    UPD: Понял, все-таки это 2 в степени.


    1. noxwell
      14.03.2016 08:44
      +1

      Первое место = 2^20, остальные получаются делением пополам.