The Sword of Midnight by Mischeviouslittleelf
Второго апреля прошёл первый квалификационный раунд Russian Code Cup 2017, на котором были побиты рекорды посещаемости за последние три года. Предлагаем вам немного цифр и разбор задач раунда:
A. Марсианский волейбол
B. Раскраска стены
C. Магический артефакт
D. Менеджер памяти
E. ЛИСА
На раунд зарегистрировалось 4552 участника, из них 1001 — новички, открывшие для себя RCC лишь в этом году. Активных участников в этот раз оказалось в два раза больше, чем в 2015 и 2016 годах! Всего нам прислали 6586 решений. Как обычно, популярнее всего — C++ в разных вариациях (2346 решений — C++ 14, 1425 на плюсах 11-й версии и примерно по 500 решений у GNU C++ 6.2 и Visual C++ 2013). Второе место по популярности у Java 8.0 (649), а третье — у Python (402 на Python 3.5 + 60 решений на PyPy 2.4.0). Самыми непопулярными для спортивного программирования оказались Perl, D и Haskell (на последнем написали ровно одно решение за весь раунд). Список всех поддерживаемых нами языков можно найти здесь.
По итогам раунда 200 участников прошли квалификацию и попали в отборочный раунд, который состоится 14 мая. Но лишь восемь из них решили все пять задач. Общие результаты можно посмотреть здесь, мы же перечислим тех пятерых, которые серьёзно оторвались от остального топа по набранному штрафному времени:
- Евгений Капун, Санкт-Петербург
- Станислав Ершов, Санкт-Петербург
- Пётр Митричев, Цюрих, Швейцария
- Макото Соеджима, Токио, Япония
- Максим Финютин, Тольятти
Мы поздравляем всех прошедших квалификацию. Всем остальным желаем удачи на втором квалификационном раунде, который пройдёт уже в это воскресенье, 16 апреля, с 12:00 до 14:00 по московскому времени.
A. Марсианский волейбол
Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт
Волейбольный матч на Марсе играется двумя командами до k очков, при этом для победы отрыв должен быть хотя бы на 2 очка. За каждый розыгрыш мяча одна из команд получает ровно 1 очко.
На текущий момент матча счет первой команды равен x, а счет второй команды равен y. Какое минимальное количество мячей будут разыграны до окончания матча?
Входные данные
Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1???t???5000).
Каждый тестовый пример описывается одной строкой, содержащей три целых числа, разделенных пробелами: k, x и y (1???k???100; 0???x,?y???100).
Гарантируется, что счет мог быть получен при корректной незавершенной игре.
Выходные данные
Для каждого теста в отдельной строке выведите ответ на него — минимальное количество мячей, которые будут разыграны до окончания матча.
Первое наблюдение, которое необходимо сделать: для минимизации длительности игры только команда с наибольшим счётом должна получать очки. Рассмотрим условие победы одной из команд. Необходимо набрать как минимум k очков и обогнать проигравшую команду как минимум на 2 очка.
Итоговый ответ: max(k,?min(x,?y)?+?2)?–?max(x,?y).
B. Раскраска стены
Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт
Девочка Маша смотрит на стену в своей комнате. Стена выложена квадратной плиткой, но вместо некоторых плиток установлены лампы. Таким образом, можно представить, что стена представляет собой клетчатый прямоугольник размером n???m, в некоторых клетках которого находятся лампы.
У Маши есть краски k различных цветов. Маша хочет покрасить все плитки на стене так, чтобы на любом вертикальном или горизонтальном отрезке плиток, ограниченном с каждого конца краем стены или лампой, цвета не повторялись. При этом лампы Маша, размуеется, красить не будет. Маше не обязательно требуется использовать все цвета.
Маша просит вас придумать, как ей покрасить стену.
Входные данные
Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t.
Каждый из тестов описывается следующим образом: в первой строке описания теста содержатся три числа n, m, k (1???n,?m???100, 1???k???max(n,?m)) — размеры стены и количество различных красок у Маши.
В следующих n строках содержатся по m чисел aij:
- aij?=?0, если на позиции (i,?j) находится лампа;
- aij?=?1, если на позиции (i,?j) находится плитка.
Суммарное количество плиток и ламп по всем тестам не превосходит 105.
Выходные данные
Для каждого теста в отдельной строке сначала выведите ответ на него:
- NO, если не существует ни одного способа покрасить стену так, как хочет Маша.
- YES, если способ перекрасить есть. В этом случае в следующих n строках выведите по m чисел bij — цвет плитки на позиции (i,?j) или 0, если на этой позиции лампа. Если подходящих раскрасок несколько, выведите любую из них.
Чтобы решить задачу, выясним, сколько минимум цветов нужно, чтобы условия выполнялись. Для этого найдём самый длинный непрерывный отрезок плиток по вертикали или по горизонтали. Пусть длина этого отрезка равна L.
Затем представим квадрат L???L, где первая строка — это последовательность чисел от 1 до L, а каждая следующая получается циклическим сдвигом предыдущей на один вправо. Такими квадратами замостим наш исходный прямоугольник, откинув лишнее и не забыв про лампы. Например, если L?=?4, замощение будет начинаться так:
1 2 3 4 1 2 3 4 1 2
2 3 4 1 2 3 4 1 2 3
3 4 1 2 3 4 1 2 3 4
…
Данное замощение будет удовлетворять условию задачи, так как для любого горизонтального и вертикального отрезка длины L выполнено, что в нём все цвета различны, а значит, для меньших длин тоже.
Если у Маши цветов меньше, чем L, то ответа не существует.
C. Магический артефакт
Ограничение по времени — 2 секунды
Ограничение по памяти — 256 мегабайт
Максим играет в компьютерную игру. Она состоит из n уровней, которые пронумерованы от 1 до n. Их можно проходить в любом порядке, на i-й уровень Максим тратит ai секунд.
Кроме того, Максим может найти магический артефакт, который усилит его персонажа. Артефакт в игре ровно один, и его местонахождение точно неизвестно — на i-м уровне он находится с вероятностью pi. После получения артефакта играть становится существенно проще — с ним Максим проходит i-й уровень за bi секунд (bi???ai). Обратите внимание, что артефакт не действует на том уровне, на котором Максим его нашёл.
Максим хочет проходить уровни в таком порядке, чтобы минимизировать математическое ожидание времени игры. Помогите ему вычислить, какого минимального математического ожидания он сможет добиться, выбрав некоторый порядок прохождения уровней. Максим выбирает порядок уровней заранее, этот порядок не должен зависеть от того, на каком уровне окажется артефакт.
Математическим ожиданием случайной величины называется сумма по всем возможным исходам произведения вероятности этого исхода на значение величины. В данном случае исходы соответствуют тому, на каком уровне окажется артефакт, а значение величины — время прохождения, если артефакт оказался на этом уровне, а Максим проходит уровни в выбранном порядке.
Входные данные
Входные данные содержат несколько тестовых примеров. В первой строке задано одно число t — количество тестов (1???t???1000).
Каждый из тестов описывается следующим образом: в первой строке задано число n — количество уровней (1???n???105).
В следующих n строках описаны уровни. Каждый из них задаётся тремя целыми числами: ai, bi, xi — время прохождения уровня до и после нахождения артефакта и значение, которое помогает вычислить вероятность найти артефакт на этом уровне. Вероятность вычисляется по формуле pi?=?xi?/?107 (1???bi???ai???105; 0???xi???107; сумма всех xi равна 107).
Сумма n по всем тестам не превосходит 5·105.
Выходные данные
Для каждого теста выведите одно число — математическое ожидание времени игры при оптимальном выборе порядка прохождения уровней. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10?-?6.
Обозначим как ci выигрыш во времени, который Максим получает от артефакта на i-м уровне: ci?=?ai?–?bi.
Пусть уровни проходятся в порядке 1,?2,?...,?n. Если артефакт был найден на i-м уровне, то время прохождения равно сумме значений bj плюс c1?+?...?+?ci. Тогда математическое ожидание времени прохождения равно:
b1?+?...?+?bn?+?p1·c1?+?p2·(c1?+?c2)?+?...?+?pn·(c1?+?...?+?cn).
b1?+?...?+?bn не зависит от порядка уровней, поэтому будем стремиться уменьшить оставшуюся часть суммы. Если раскрыть скобки, можно заметить, что она равна сумме ci·pk по всем парам i, k, таким, что i???k.
Посмотрим, как изменится сумма, если поменять местами уровни i и i?+?1. Среди слагаемых ci·pk изменится только ci·pi?+?1 — оно заменится на ci?+?1·pi. Если порядок уровней является оптимальным, то ci·pi?+?1???ci?+?1·pi (иначе их можно было бы поменять местами и улучшить ответ). Преобразуем это неравенство:
ci?/?pi???ci?+?1?/?pi?+?1.
В оптимальном ответе для всех i от 1 до n?–?1 верно это неравенство. Значит, в оптимальном ответе уровни отсортированы по ci?/?pi, и, чтобы получить его, нужно их отсортировать. Заметим, что если pi?=?0, то можно считать ci?/?pi?=??.
Сортировать по ci?/?pi нужно осторожно. Если производить деление в числах с плавающей точкой, то в случае когда ci?=?pi?=?0, получится NaN, что приведёт к ошибке. Если сравнивать дроби ci?/?pi и ck?/?pk при помощи компаратора ci·pk?<?ck·pi, то в случае когда ci?=?pi?=?0, результат всегда будет false, что тоже приведёт к неправильной сортировке. Поэтому уровни с ci?=?pi?=?0 нужно обработать отдельно. Эти уровни могут быть пройдены в любой момент: нетрудно заметить, что они не вносят никакого вклада в ответ, кроме фиксированных слагаемых bi. Их можно поместить, например, в самый конец.
После сортировки нужно посчитать искомое математическое ожидание. Оно вычисляется по вышеприведённой формуле при помощи префиксных сумм ci.
D. Менеджер памяти
Ограничение по времени — 3 секунды
Ограничение по памяти — 256 мегабайт
Петя активно ведет разработку своего собственного менеджера памяти MEM 2.0 для хранилища на базе магнитных 7D блоков. Однако он столкнулся с проблемой оптимальной выдачи данных из хранилища пользователям.
Всего в менеджере Пети хранится n блоков с данными, пронумерованных от 1 до n, и имеется q запросов о выдаче данных с одного или нескольких из них. Запросы необходимо обработать в том порядке, в котором они поступили.
Для выдачи данных у Пети есть k указателей, каждый из которых указывает на один из блоков. Изначально Петя может поставить указатели на любой набор блоков.
Петин менеджер умеет мгновенно выдавать данные из любого числа блоков, если на каждый из них указывает хотя бы один указатель. Если же это не так, менеджер сначала переставляет указатели, чтобы условие выполнялось, а затем выдает данные — время выполнения этой операции для i-го запроса составляет si миллисекунд, можно переставить любое число указателей.
Петя хочет реализовать переставление указателей в менеджере так, чтобы суммарное время ответа на все запросы пользователей было минимальным. Запросы необходимо обработать в том порядке, в котором они поступили, менять местами запросы нельзя. Помогите ему.
Рассмотрим приведенные в примере тесты.
В первом тесте Петя изначально может поставить указатели на блоки 1, 2 и 4 — после этого первые два запроса выполнятся мгновенно. Перед третьим запросом за s3?=?1 миллисекунду он может поставить указатели на блоки 2, 3 и 5, а перед четвертым запросом за s4?=?1 миллисекунду он может поставить указатели на блоки 1, 3 и 5. Суммарное время на все запросы будет равно s3?+?s4?=?2 миллисекунды.
Во втором тесте Пете невыгодно выполнять первые два запроса мгновенно (ставя изначально указатели на блоки 1, 2 и 4), потому что потом ему придется потратить 10 миллисекунд, чтобы поставить указатели на другие блоки. Поэтому оптимальная стратегия для Пети — изначально поставить указатели на блоки 1, 2 и 3, перед вторым запросом на блоки 1, 3, 4 за s2?=?1 миллисекунду, а перед последним запросом поставить указатели на блоки 1, 3 и 5 за s4?=?3 миллисекунды. Итого суммарное время ответа на запросы s2?+?s4?=?4 миллисекунды.
Входные данные
Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1???t???1000).
Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержатся три числа n, k, q — количество блоков в менеджере, количество указателей и количество пользовательских запросов соответственно (1???k???n???105, 1???q???106).
В следующей строке содержится q целых чисел si — время, требуемое для перестановки указателей при ответе на i-й запрос (1???si???104).
В следующих q строках содержится описание запросов пользователей, i-й запрос описывается одной строкой, где первое число ci описывает количество блоков данных, которое пользователь хочет получить (1???ci???k), а следующие ci чисел описывают номера этих блоков bi,?j в возрастающем порядке (1???bi,?j???n).
Гарантируется, что сумма n во всех тестах одних входных данных не превосходит 105, а также сумма ci во всех тестах одних входных данных не превосходит 106.
Выходные данные
Для каждого теста выведите ответ на него — минимальное суммарное время ответа на все запросы пользователей.
Для начала для каждого запроса qi найдем goi — минимальное j, такое, что среди qj,?qj?+?1,?...,?qi не более k различных чисел: это будет означать, что перед j-м запросом можно так поставить указатели, что j, j?+?1, ..., i запросы выполнятся мгновенно. Это делается за O(sum(|qi|)), например, двумя указателями, если идти с конца массива запросов.
Теперь будем использовать динамическое программирование, вычислим значения dpi — минимальное время, за которое можно выполнить первые i запросов. Если goi?=?0, то dpi?=?0. Если нет, то несложно видеть, что dpi?=?minj?=?goi..i(dpj?-?1?+?sj) — мы выбираем запрос j, перед которым будем менять указатели, и платим соответствующую стоимость. Так как goi не убывают, посчитать эту величину можно либо поддерживая set значений dpj?-?1?+?sj, либо используя очередь с операцией «минимум».
E. ЛИСА
Ограничение по времени — 3 секунды
Ограничение по памяти — 256 мегабайт
Илья работает в Лаборатории Изучения Строковых Алгоритмов (ЛИСА). Сейчас он пытается решить такую задачу.
Задан массив строк s1,?s2,?...,?sn и q запросов. Каждый запрос характеризуется двумя целыми числами li и ri (1???li???ri???n). Для ответа на запрос необходимо сделать следующее. Назовем строку представимой, если ее можно получить следующим образом: выберем две строки sx и sy, где li???x,?y???ri, выберем непустой префикс строки sx и непустой суффикс строки sy, возьмем их конкатенацию. Ответом на запрос является количество различных представимых строк для заданных li и ri.
Например, пусть s?=?[abc,?ab,?ac,?bcac], выберем li?=?2, ri?=?3. Представимыми будут строки:
x?=?2, y?=?2: ab?=?a?+?b, aab?=?a?+?ab, abb?=?ab?+?b, abab?=?ab?+?ab*.
x?=?2, y?=?3: ac?=?a?+?c, aac?=?a?+?ac, abc?=?ab?+?c, abac?=?ab?+?ac.
x?=?3, y?=?2: ab?=?a?+?b, aab?=?a?+?ab, acb?=?ac?+?b, acab?=?ac?+?ab.
x?=?3, y?=?3: ac?=?a?+?c, aac?=?a?+?ac, acc?=?ac?+?c, acac?=?ac?+?ac.
Всего получилось 12 различных представимых строк.
Помогите Илье решить задачу достаточно быстро.
Входные данные
В первой строке заданы два целых числа n и q — количество слов и запросов соответственно (1???n,?q???105).
Каждая из следующих n строк содержит непустые слова si, состоящие из строчных латинских букв. Суммарная длина всех слов не превосходит 105.
Следующие q строк содержат пары чисел li, ri (1???li???ri???n) — левая и правая граница i-го запроса соответственно.
Выходные данные
Выведите q строк, i-я из них должна содержать единственное целое число — ответ на i-й запрос.
Рассмотрим сначала задачу для двух конкретных строк: посчитаем количество вхождений каждой буквы в первую строку и каждой буквы во вторую строку, не будем при этом учитывать первую букву в первой строке и последнюю букву во второй строке, которые надо взять в любом случае. Чтобы получить ответ, надо вычислить произведение длин строк и отнять от этого значения сумму cnt1[letter] * cnt2[letter] по всем буквам. Доказательство утверждения оставим как упражнение, такая задача предлагалась на северном четвертьфинале — 2015 (http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf, задача C). Широкий круг участников мог решать её на кубке трёх четвертьфиналов.
Для n строк задача решается похожим образом: добавим все строки в префиксный бор, добавим все строки в суффиксный бор, посчитаем количество вершин в первом боре и во втором боре (кроме корня), перемножим эти два числа — столько строк мы можем сгенерить, прикладывая путь в префиксном боре к пути в суффиксном боре. Теперь нужно вычесть повторения, это делается аналогично: в префиксном боре считается количество каждой буквы на рёбрах, кроме буквы на рёбрах из корня, эти значения перемножаются, эта сумма вычитается из произведения числа вершин в борах.
Осталось научиться отвечать на запросы на отрезке. Будем использовать sqrt-декомпозицию, разобьём строки в группы по сумме длин. Станем жадно набирать в группу строки, пока суммарная длина в группе не окажется больше корня из суммы длин, последняя строка может быть достаточно большой.
Теперь используем алгоритм Мо, отсортируем запросы по блоку левой границы при равном блоке по правой границе, тогда между сменами блока левой границы правая граница будет двигаться только вправо. Чтобы добавить строку в бор или удалить её из бора, станем пересчитывать количество вершин в поддереве и, соответственно, число вхождений букв в бор.
Все на второй раунд!
Напоминаем: второй раунд — в это воскресенье, с 12:00 по московскому времени. На момент написания статьи зарегистрировалось уже более 4600 участников, будет интересно. Присоединяйтесь!
Кроме того, мы решили попробовать открыть в telegram группу, посвященную RCC и спортивному программированию в целом. Welcome!