332A - Выпьем?
Поскольку n ≥ 4, один ход Васи никак не влияет на то, выпьет ли он стакан сока во время другого своего хода. Следовательно, задача заключается просто в том, чтобы найти в заданной строке количество позиций, номера которых (в 0-индексации) кратны n и перед которыми стоит хотя бы три одинаковых символа.
Асимптотика решения — O(|s|)
Код
332B - Максимальная абсурдность
Предварительно построим массив частичных сумм, который позволит отвечать на запрос суммы на отрезке за O(1). Будем перебирать по убыванию число a из ответа — левую границу того из наших отрезков, который лежит левее. Теперь нужно среди отрезков длины k, начинающихся с элемента не левее a + k, выбрать отрезок с максимальной суммой. Поскольку a перебирается по убыванию, то такой отрезок можно поддерживать при переходе от a к a - 1.
Асимптотика решения — O(n).
Код
332C - Месть студентов
Отсортируем приказы в первую очередь по возрастанию bi, а при равенстве bi — по убыванию ai. Можно считать, что в оптимальном решении все приказы, выполненные заведующей, следуют (в отсортированном списке) после тех приказов, которые она не выполнила (это может быть неверно в случае наличия одинаковых приказов, однако на параметры ответа это все равно не влияет). Переберем i — номер первого приказа в отсортированном списке, который выполнит заведующая. Слева от этого приказа нужно выбрать p - k приказов, которые заведующая не выполнит. Поскольку требуется, что сумма bi у этих приказов была наибольшей, можно выбрать последние p - k приказов, стоящие перед i-ым приказом. Справа от i-ого приказа требуется выбрать k - 1 приказ, который заведующая выполнит. Требуется, чтобы эти приказы имели максимальную сумму ai. Если i перебирать по убыванию, то эту максимальную сумму можно поддерживать, просто храня k - 1 максимальных ai из уже проанализированных в какой-нибудь стандартной структуре данных, работающей за логарифмическое время (типа multiset’а в C++),
Асимптотика решения — O(n log n).
Код
332D - Похищение чертежей
В задаче задан неориентированный взвешенный граф без кратных ребер и петель, удовлетворяющий следующему свойству: для любого k-элементного множества S его вершин существует единственная вершина, смежная со всеми вершинами этого множества (*) (эта вершина была названа в условии соседней с S). Для любого k-элементного множества можно вычислить специальную характеристику, равную сумме весов ребер, ведущих из вершин этого множества в соседнюю с ним вершину. Требуется найти среднее арифметическое характеристик всех k-элементных множеств вершин.
Решить эту задачу позволяет следующий факт (доказательство которого приведено ниже): при k ≥ 3 условию задачи удовлетворяет только полный граф из k + 1 вершины. Для полных графов ответ на задачу равен удвоенной сумме длин всех ребер, деленной на n. Точно так же вычисляется и ответ для k = 1. Осталось рассмотреть случай k = 2. Переберем вершину i, которая будет являться соседней с нашим двухэлементным множеством. Выпишем в порядке возрастания все такие номера вершин j, что ci, j ≠ - 1. Любые две вершины из построенного списка образуют множество, для которого вершина i является соседней, а других таких множеств не существует. Перебирая все пары вершин из этого списка, мы можем прибавить характеристики всех этих множеств к ответу. Поскольку в задаче гарантируется, что граф удовлетворяет свойству (*), то каждая пара вершин будет проанализирована ровно один раз. Отметим, что аналогичный подход используется и в валидаторе к данной задаче.
Асимптотическая сложность решения составляет, таким образом, O(n2)
Код
Доказательство.
Пусть в графе любые k вершин имеют ровно одну общую смежную вершину (*)
Лемма 1. У любых двух вершин ровно k - 1 общая смежная вершина.
Рассмотрим две произвольные различные вершины s, t. Пусть v1, v2, ..., vl — все различные общие смежные вершины этих двух вершин. Если l ≥ k, то мы получим, что вершины из множества {v1, ..., vk} имеют две общие смежные вершины s, t, что противоречит (*). Пусть теперь l ≤ k - 2. Рассмотрим множество вершин S = {s, t, v1, ..., vl}, состоящее из l + 2 ≤ k элементов. Если l + 2 < k, дополним это множество до k-элементного произвольными вершинами, не входящими в S. Полученное множество назовем T. Согласно (*), существует единственная вершина u, не входящая в T, которая смежна со всеми вершинами из T. В частности, эта вершина смежна с вершинами s и t. Однако по построению во множестве T должны были находиться все вершины, смежные c s и t, в том числе и вершина u. Получили противоречие. Значит, l = k - 1.
Лемма 2. В нашем графе найдется полный подграф из k + 1 вершины.
Рассмотрим множество S = {v1, ..., vk, vk + 1}, в котором v1, ... vk — произвольные попарно различные вершины нашего графа, vk + 1 — их общая смежная вершина. Приведем конструктивный способ построения полного подграфа на основе этого множества. Осуществим k - 1 итерацию, на i-ой итерации будем рассматривать вершину vi. Если эта вершина смежна со всеми вершинами vi + 1, ..., vk, то перейдем к следующей итерации. Иначе рассмотрим множество T = {v1, ..., vi - 1, vi + 1, ...vk + 1}. У вершин из T существует ровно одна общая смежная вершина u (не совпадающая, очевидно, с vi, поскольку vi смежна не со всеми вершинами из T). Заменим вершину vi на u и перейдем к следующей итерации. После окончания последней итерации множество S, очевидно, будет являться множеством вершин полного подграфа.
Покажем, что при k ≥ 3 наш граф — это полный граф из k + 1 вершины. Согласно лемме 2, в этом в графе найдется полный подграф с множеством вершин S = {v1, ..., vk + 1}. Допустим, что в нашем графе найдется вершина u, не принадлежащая S. Так как S — множество вершин полного подграфа, а любые две вершины согласно (1) имеют ровно k - 1 общую вершину, то все общие смежные вершины v1 и v2 (как и любых двух различных вершин из S) лежат в S. Если любые k вершин имеют общую смежную вершину, то и любые i (2 ≤ i ≤ k - 1) вершин имеют общую смежную вершину (возможно, не единственную). В частности, поскольку k ≥ 3, общую смежную вершину имеют вершины v1, v2, u, и эта вершина принадлежит S (как общая смежная вершина v1 и v2). Если допустить, что у u есть две смежных вершины x, y из S, то получим противоречие (1) (поскольку у этих двух смежных вершин будет k общих смежных вершин). Следовательно, в S существует единственная вершина x, смежная с u. Возьмем вершину y из S, отличную от x. У вершин (u, x, y) есть общая смежная вершина, и она принадлежит S. Но это значит, что u имеет две смежных вершины из S. Противоречие.
332E - Двоичный ключ
Переберем cnt — количество единичных бит в ключе. Заметим, что cnt достаточно перебирать до min(|s|, k), поскольку ключи, содержащие более чем |s| единичных бит, не могут являться минимальными лексикографически.
Научимся решать задачу для фиксированного cnt. Заметим, что любой полный проход по ключу соответствует выписыванию cnt из k просмотренных символов контейнера, т.е. контейнер разбивается на блоки длины k, а сообщение — на блоки длины cnt (последние блоки могут иметь меньшую длину). Пронумеруем символы каждого блока сообщения от 0 до cnt–1. Назовем (q, j)-суффиксом сообщения суффикс его q-ого блока, начинающийся с позиции j в этом блоке. Решим задачу динамическим программированием: di, j – верно ли, что существует ключ, первые i символов которого – нули и при использовании которого будет выписана строка, получаемая конкатенацией всех (q, j)-суффиксов сообщения. Переходы в этой динамике основаны на постановке в i-ую позицию ключа либо нуля, либо единицы (каждый раз нужно выбирать минимальный допустимый символ). Для восстановления самого ключа требуется сохранять для каждой подзадачи и сами выбранные символы, либо анализировать сами значения динамики.
Асимптотическая сложность решения — O(k·|s|2 + |p|).
Код