Мероприятия
14 Марта 2016
VK Cup
13-14 марта, 20-21 марта
Первое, о чём хотим рассказать, – чемпионат по спортивному программированию VK Cup 2016 и разбор нескольких интересных задач с прошлого года.
Несколько слов о Чемпионате. ВКонтакте проводит третий VK Cup — чемпионат по программированию среди русскоязычных молодых специалистов, студентов, школьников и просто любителей алгоритмов и структур данных. К участию в нём приглашаются команды из двух человек (можно участвовать и индивидуально), чей возраст от 14 до 23 лет. Отборочные этапы пройдут с марта по май, а в финал будут приглашены лучшие 20 команд. Финал пройдет в Санкт-Петербурге в июле, лучшие восемь команд будут награждены призами:
Соревнование будет проходить на площадке Codeforces, регистрация уже открыта — спешите зарегистрировать команду! Начать своё участие необходимо с квалификационных этапов, которые будут проходить 13-14 и 20-21 марта. Участвовать можно как в двух, так и в любом из них. Все подробности доступны по ссылке на странице Чемпионата.
Чемпионат VK Cup с одной стороны следует традициям чемпионатов по программированию, предлагая участникам задачи на алгоритмы и структуры данных. С другой, стороны мы стараемся расширить формат. Так, в ходе чемпионата прошлого года были проведены два необычных раунда (уайлд-кард раунды 1 и 2). На первом из них участникам предлагались простые задачи, но язык, на котором можно их решать, они узнали только в момент старта раунда. Языком раунда оказался малоизвестный язык Picat. За два часа соревнования участникам надо было изучить основы этого языка и решить несколько задач на нем. Например, одна из задач была о вычислении расстояния Левенштейна.Условие задачи:
1 место — 1048576 рублей
2 место — 524288 рублей
3 место— 262144 рубля
4-8 места — 131072 рубля
2 место — 524288 рублей
3 место— 262144 рубля
4-8 места — 131072 рубля
Соревнование будет проходить на площадке Codeforces, регистрация уже открыта — спешите зарегистрировать команду! Начать своё участие необходимо с квалификационных этапов, которые будут проходить 13-14 и 20-21 марта. Участвовать можно как в двух, так и в любом из них. Все подробности доступны по ссылке на странице Чемпионата.
Чемпионат VK Cup с одной стороны следует традициям чемпионатов по программированию, предлагая участникам задачи на алгоритмы и структуры данных. С другой, стороны мы стараемся расширить формат. Так, в ходе чемпионата прошлого года были проведены два необычных раунда (уайлд-кард раунды 1 и 2). На первом из них участникам предлагались простые задачи, но язык, на котором можно их решать, они узнали только в момент старта раунда. Языком раунда оказался малоизвестный язык Picat. За два часа соревнования участникам надо было изучить основы этого языка и решить несколько задач на нем. Например, одна из задач была о вычислении расстояния Левенштейна.Условие задачи:
Расстояние Левенштейна между строками, состоящими из символов английского алфавита, вычисляется как минимальная суммарная стоимость последовательности действий, позволяющих преобразовать одну строку в другую. Разрешенные действия:
* замена: стоимость замены одного символа на другой равна разности порядковых номеров этих символов в алфавите.
* вставка/удаление: стоимость вставки символа в строку или удаления символа из строки равна порядковому номеру этого символа в алфавите.
Вам даны две строки. Найдите расстояние Левенштейна между ними.
Второй Уайлд-Кард раунд проходил в течение недели. За это время участникам надо было составить и реализовать наиболее точный алгоритм поиска плагиата для решений задач по программированию. К сожалению, на интернет-соревнованиях по программированию некоторые участники копируют друг у друга решения, делая мелкие (а иногда не очень) правки. Участниками нужно было написать программу, которая читает последовательность файлов и выделяет группы эквивалентных решений. Победитель раунда сильно продвинулся в поиске плагиата, а его решение теперь используется на 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-й ролик будет обработан.
Полный текст условия доступен по ссылке. Там же можно попробовать самостоятельно решить и отослать решение на проверку. Для самых нетерпеливых вот описание решения.
Ждём вас на VK Cup 2016! Самое время зарегистрировать команду и подключиться к квалификационному раунду. Если не успеете принять участие в первом, то можете участвовавать во втором, который состоится 20-21 марта. Удачи!
Источник:
* замена: стоимость замены одного символа на другой равна разности порядковых номеров этих символов в алфавите.
* вставка/удаление: стоимость вставки символа в строку или удаления символа из строки равна порядковому номеру этого символа в алфавите.
Вам даны две строки. Найдите расстояние Левенштейна между ними.
Второй Уайлд-Кард раунд проходил в течение недели. За это время участникам надо было составить и реализовать наиболее точный алгоритм поиска плагиата для решений задач по программированию. К сожалению, на интернет-соревнованиях по программированию некоторые участники копируют друг у друга решения, делая мелкие (а иногда не очень) правки. Участниками нужно было написать программу, которая читает последовательность файлов и выделяет группы эквивалентных решений. Победитель раунда сильно продвинулся в поиске плагиата, а его решение теперь используется на 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-й ролик будет обработан.
Полный текст условия доступен по ссылке. Там же можно попробовать самостоятельно решить и отослать решение на проверку. Для самых нетерпеливых вот описание решения.
Ждём вас на VK Cup 2016! Самое время зарегистрировать команду и подключиться к квалификационному раунду. Если не успеете принять участие в первом, то можете участвовавать во втором, который состоится 20-21 марта. Удачи!
Источник:
