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

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

    Первое, о чём хотим рассказать, – чемпионат по спортивному программированию 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 марта. Удачи!
    • +13
    • 20,5k
    • 8
    ВКонтакте 86,91
    Компания
    Поделиться публикацией
    Похожие публикации
    Комментарии 8
      +9
      Раз… раз… готов поклясться, секунду назад здесь было 3 комментария. Нечто пожирает комменты?
        0
        Причем в боковой панельке ("Блог на Хабрахабре") 4 комментария, при заходе на эту страницу написано "Комментарии (4)", а если нажать кнопку обновления комментариев, то в скобках будет единица.
        Либо какой-то баг, либо комментарии теперь удаляют в обход НЛО
        UPD. Теперь комментариев 5
          0
          Да, точно! Это я оставил комментарий, но его больше нет даже в моем профиле.
            0
            Хабр точно деградирует. Компания превратилась в место для рекламы и бюрократии.
              +2
              Комментарии с нарушением правил сайта удаляются, вместе с ними пропадают те, что были написаны под ним. Донт паник )
                0
                А пересчитывать их количество не надо? Меня уверяют что их тут 10 на данный момент. Но даже с моим комментарием столько не наберётся.
              0
              Никак не могу сообразить, как определяется сумма 131072 р. (остальные умножаются на 2х, видно)?
              UPD: Понял, все-таки это 2 в степени.
                +1
                Первое место = 2^20, остальные получаются делением пополам.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое