Всем привет! Социальная сеть ВКонтакте возобновляет свой блог на Хабре.
Первое, о чём хотим рассказать, – чемпионат по спортивному программированию 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. За два часа соревнования участникам надо было изучить основы этого языка и решить несколько задач на нем. Например, одна из задач была о вычислении расстояния Левенштейна.
Вот такое решение прислал один из участников:
Второй Уайлд-Кард раунд проходил в течение недели. За это время участникам надо было составить и реализовать наиболее точный алгоритм поиска плагиата для решений задач по программированию. К сожалению, на интернет-соревнованиях по программированию некоторые участники копируют друг у друга решения, делая мелкие (а иногда не очень) правки. Участниками нужно было написать программу, которая читает последовательность файлов и выделяет группы эквивалентных решений. Победитель раунда сильно продвинулся в поиске плагиата, а его решение теперь используется на Codeforces для поиска читеров.
А вот пример уже задачи классического формата с первого квалификационного раунда.
Полный текст условия доступен по ссылке. Там же можно попробовать самостоятельно решить и отослать решение на проверку. Для самых нетерпеливых вот описание решения.
Ждём вас на VK Cup 2016! Самое время зарегистрировать команду и подключиться к квалификационному раунду. Если не успеете принять участие в первом, то можете участвовавать во втором, который состоится 20-21 марта. Удачи!
Первое, о чём хотим рассказать, – чемпионат по спортивному программированию 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-й ролик будет обработан.
Известно, что каждый сервер пережимает минутный фрагмент за одну секунду. Таким образом, на любом из серверов видеофайл длительностью 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 марта. Удачи!