Рубина по вечерам любит
раскладывать пасьянс. Для этого она использует фамильную колоду карт. В колоде
Рубины m * n карт,
каждая из которых имеет одну из m мастей и достоинство от 1 до n. В колоде нет двух карт одной масти с
одинаковым достоинством.
Рубина уже
перетасовала карты и разложила их в ряды. Выясните, получится ли у неё разложить
пасьянс.
Если пасьянс
разложить не удастся, выведите «N0». Иначе в первой строке выведите «YES», а в следующих n * m строках
выведите описания карт в порядке их перекладывания в стопки. Описание карты
должно представлять из себя два числа через пробел — её масть и достоинство.
Если существует несколько различных порядков, удовлетворяющих условию задачи,
можно вывести любой из них.
Давайте рассматривать разбиения на суммы, в которых все
слагаемые упорядочены по невозрастанию. Тогда мы можем действовать следующим
образом: в каждый момент у нас есть какая-то текущая степень, сумма которую
осталось добить, и мы знаем сколько слагаемых осталось поставить. Мы можем либо
взять ещё одно слагаемое текущей степени, либо перейти на степень на одну
меньшую.
Наивный способ оформить данное решение в виде динамического
программирования: dp(sum, deg, count) = dp(sum, deg - 1, count) + dp(sum - k^deg, deg, count - 1)
И база: dp(0, 0,
0) = 1.
Ответ лежит в dp(n, log_k(n) + 1, l ).
Проблема такой наивной динамики: sum до 10^18. Но это не проблема на самом деле: мы
знаем что sum % ^deg = n % ^deg, так как sum получена из n вычитанием степеней k больше либо равных deg. А также мы
знаем что если sum / ^deg больше count, то ответ для такой dp равен 0. Это потому что нам надо использовать count слагаемых каждое из которых не больше ^deg и набрать sum, и при этом ^deg * count < sum. Таким образом вместо sum можно хранить sum / ^deg, и этот
параметр не превосходит I .
Тогда модифицированная dp выглядит так:
dp(s, deg, count) = dp(s * k + n_k[deg - 1], deg - 1, count) + dp(sum - 1,
deg, count - 1),
Где n_k[deg - 1] = n / k^(deg - 2) % k. (то есть (deg - 1)-ый разряд
в k-ичной записи числа n).
База остаётся прежней: dp(0, 0, 0) = 1.
Ответ лежит в dp(0, I og_k(n) + 1, I ).
Состояний в dp - I * I og_k (n) * I , каждое
вычисляется за O(1).
Таким образом общая сложность - 0(I^2 log(n) ).
Задача J. Динамическая
сложность строки
Ограничение по
времени: 5 секунд
Ограничение по памяти: 64 мегабайта
Подстрока — это несколько подряд
идущих символов в строке. Префикс строки — это подстрока, включающая первый
символ строки. Суффикс строки — это подстрока, включающая последний символ
строки.
Рассмотрим строку «квалификация».
Строки «валик» или «акация» не являются её подстроками, т.к. буквы этих строк
не идут в ней подряд. «валиф» и «каци» являются подстроками, при этом они обе
не являются ни префиксом, ни суффиксом. «квал» является префиксом, а «кация»
суффиксом строки. Сама строка «квалификация» является собственным суффиксом и
префиксом.
В данной задаче мы считаем, что
номера символов в строке индексируются с нуля.
Периодом строки s назовём
минимальное положительное целое число T, для которого для любого 0 ^ i < |s| верно, что s[i] = s[i mod T], где i mod T — остаток от
деления i на
T.
Грань строки — это её непустой
префикс, который не является всей строкой и при этом равен её суффиксу.
Сложностью строки назовём число различных периодов её граней. Динамической
сложностью строки назовём сумму сложностей всех её префиксов.
Для данного
числа п
требуется найти бинарную строку (над алфавитом {., X}) длины п, имеющую
максимальную динамическую сложность.
Единственная строка содержит целое число п (1 <= п <= 25).
В первой
строке выведите искомую строку длины n, во второй строке выведите её динамическую
сложность. Если существует несколько строк с максимальной динамической
сложностью, можно вывести любую из них.
|
тест
|
ответ
|
|
1
|
0
|
|
2
|
1
|
|
10
|
.X..X..X..
14
|
Рассмотрим третий пример.
Рассмотрим все префиксы строки и посчитаем их сложность:
«.» — граней нет ^ сложность = 0
«.X»
— граней нет ^ сложность = 0
«.X.»
— грань «.» (период 1) ^ сложность = 1
«.X..»
— грань «.» (период 1) ^ сложность = 1
«.X..X» — грань «.X» (период 2) ^
сложность = 1
« .X..X. » — грани « . » (период 1) и « .X. » (период 2) ^ сложность = 2
« .X..X.. » — грани « . » (период 1) и « .X.. » (период 3) ^ сложность = 2
«.X..X..X» — грани «.X» (период 2) и «.X..X» (период 3) ^
сложность = 2
«.X..X..X.» — грани «.»
(период 1), «.X.»
(период 2) и «.X..X.» (период 3) ^
сложность = 3
«.X..X..X..» — грани «.»
(период 1), «.X..»
(период 3) и «.X..X..» (период 3) ^
сложность = 2
Получаем, что строка «.X..X..X.. » имеет динамическую
сложность 14.
Разбор задачи J. Динамическая сложность строки
Давайте за 2^n переберём все бинарные строки
длины n. После этого за O(n * n) посчитаем их динамическую сложность. Это делается следующим
образом:
1)
Для каждого префикса
посчитаем его период за линейное время с помощью префикс-функции или z-функции. Это
суммарно делается за O(n * n)
2)
Теперь переберём все
префиксы строки. Для каждого префикса будем за время O(n) находить его сложность: все грани строки можно перечислить
за линейное время с помощью алгоритма префикс-функции, после чего взять его
заранее посчитанный период и добавить в словарь. Сложностью данной строки будет
размер словаря. Такой словарь можно реализовать за константное время, храня его
в одном integer’e и добавлять элементы, добавляя бит в нужную позицию.
Общая
сложность решения: O(n * n * 2^n). Оно отработает несколько
минут, после чего вы можете создать новое решение, в котором занести ответы на
все 25 тестов в массив констант.
Этого
уже достаточно, чтоб сдать задачу, однако, у жюри также есть решения за O(n * 2^n) и 0(2^n), но мы их не будем приводить здесь, т.к. их описание
требует гораздо больший объём текста.
Задача K. Открытый
Кубок - 2
Ограничение по времени: 2 секунды
Ограничение по памяти: 256
мегабайт
Эндрю — тренер по спортивному
программированию. Прямо сейчас идёт этап Открытого Кубка по программированию, и
Эндрю интересны результаты тех команд, которые он тренирует.
В его любимом браузере есть
функция поиска текста на странице: Эндрю вводит некоторую строку, и браузер
показывает все её вхождения. Эндрю хочет воспользоваться этим функционалом,
чтобы смотреть результаты своих команд. Для этого ему нужно выбрать строку,
которая входит во все названия его команд и не входит в название ни одной
другой команды.
Но таблица текущих результатов
Открытого Кубка устроена так, что команда начинает отображаться в ней только в
тот момент, когда впервые отправляет решение на проверку. Изначально таблица
пуста. Это означает, что при появлении в таблице результатов каждой новой
команды Эндрю, возможно, потребуется обновить строку поиска. Среди всех команд
Эндрю есть одна любимая, которая, к счастью для него, сделала первую попытку на
соревновании. Так что даже в таблице результатов из одной команды Эндрю есть,
за кого болеть.
Найдите
строку, по которой должен искать Эндрю после каждой появляющейся в таблице команды.
В первой
строке записано целое число n — общее число команд, которые отправляли свои
решения на проверку. Далее в n строках перечислены названия этих команд
в том порядке, в котором они появлялись в таблице результатов. Названия команд
попарно различны и состоят только из строчных латинских букв и символов
подчёркивания «_».
После названия тех команд, которые тренирует Эндрю, добавлен символ «+».
Суммарная длина всех названий не превосходит 2 • 105.
После
появления в таблице результатов каждой из команд найдите общую подстроку
названий команд Эндрю, не содержащуюся в названиях других команд (учитываются
лишь те команды, который в этот момент присутствуют в таблице результатов).
Если подходящей строки не существует, нужно выдать «-1 -1». В противном случае
нужно вывести целые числа l и r такие, что искомая строка входит в
название любимой команды Эндрю с позиции l по позицию r (считая
позиции с нуля). Если подходящих строк несколько, выведите самую короткую из
них, а если и таких несколько, то ту, для которой минимально значение l.
|
тест
|
ответ
|
|
6
|
0 0
|
|
mit_kotiki+
|
2 2
|
|
sjtu_koty+
|
4 4
|
|
itmo_first
|
5 6
|
|
msu_koshki
|
46
|
|
mipt_alot
|
-1 -1
|
|
spsu_kot
|
|
Построим
общее суффиксное дерево для всех строк из входа, при этом при построении
отметим в каждой вершине, каким строкам она принадлежала. Далее используем
классический приём объединения множеств вдоль дерева -- обходим суффиксное
дерево в глубину и поддерживаем множество, содержащее все номера строк, которые
могут быть встречены в поддереве, сливая эти множества снизу. При этом при
объединении множеств будем добавлять элементы меньшего множества к большему,
что в сумме отработает за nlog^2n.
Далее,
имея такое множество, мы должны узнать наименьший номер строки из второго типа,
в котором встречается ребро (logn) и наименьший номер строки из первого типа, в котором оно не
встречается. Второй запрос также может быть сделан за logn, но в
авторском решении он реализован с помощью бинарного поиска и сравнения номера
элемента с количеством элементов, меньших него за log^2 n.
Итоговая асимптотика: O(n log^2 n).
