332A - Выпьем?

Поскольку n ≥ 4, один ход Васи никак не влияет на то, выпьет ли он стакан сока во время другого своего хода. Следовательно, задача заключается просто в том, чтобы найти в заданной строке количество позиций, номера которых (в 0-индексации) кратны n и перед которыми стоит хотя бы три одинаковых символа.

Асимптотика решения — O(|s|)

Код

332B - Максимальная абсурдность

Предварительно построим массив частичных сумм, который позволит отвечать на запрос суммы на отрезке за O(1). Будем перебирать по убыванию число a из ответа — левую границу того из наших отрезков, который лежит левее. Теперь нужно среди отрезков длины k, начинающихся с элемента не левее a + k, выбрать отрезок с максимальной суммой. Поскольку a перебирается по убыванию, то такой отрезок можно поддерживать при переходе от a к a - 1.

Асимптотика решения — O(n).

Код

332C - Месть студентов

Отсортируем приказы в первую очередь по возрастанию b_i, а при равенстве b_i — по убыванию a_i. Можно считать, что в оптимальном решении все приказы, выполненные заведующей, следуют (в отсортированном списке) после тех приказов, которые она не выполнила (это может быть неверно в случае наличия одинаковых приказов, однако на параметры ответа это все равно не влияет). Переберем i — номер первого приказа в отсортированном списке, который выполнит заведующая. Слева от этого приказа нужно выбрать p - k приказов, которые заведующая не выполнит. Поскольку требуется, что сумма b_i у этих приказов была наибольшей, можно выбрать последние p - k приказов, стоящие перед i-ым приказом. Справа от i-ого приказа требуется выбрать k - 1 приказ, который заведующая выполнит. Требуется, чтобы эти приказы имели максимальную сумму a_i. Если i перебирать по убыванию, то эту максимальную сумму можно поддерживать, просто храня k - 1 максимальных a_i из уже проанализированных в какой-нибудь стандартной структуре данных, работающей за логарифмическое время (типа multiset’а в C++),

Асимптотика решения — O(n log n).

Код

332D - Похищение чертежей

В задаче задан неориентированный взвешенный граф без кратных ребер и петель, удовлетворяющий следующему свойству: для любого k-элементного множества S его вершин существует единственная вершина, смежная со всеми вершинами этого множества (*) (эта вершина была названа в условии соседней с S). Для любого k-элементного множества можно вычислить специальную характеристику, равную сумме весов ребер, ведущих из вершин этого множества в соседнюю с ним вершину. Требуется найти среднее арифметическое характеристик всех k-элементных множеств вершин.

Решить эту задачу позволяет следующий факт (доказательство которого приведено ниже): при k ≥ 3 условию задачи удовлетворяет только полный граф из k + 1 вершины. Для полных графов ответ на задачу равен удвоенной сумме длин всех ребер, деленной на n. Точно так же вычисляется и ответ для k = 1. Осталось рассмотреть случай k = 2. Переберем вершину i, которая будет являться соседней с нашим двухэлементным множеством. Выпишем в порядке возрастания все такие номера вершин j, что c_i, j ≠  - 1. Любые две вершины из построенного списка образуют множество, для которого вершина i является соседней, а других таких множеств не существует. Перебирая все пары вершин из этого списка, мы можем прибавить характеристики всех этих множеств к ответу. Поскольку в задаче гарантируется, что граф удовлетворяет свойству (*), то каждая пара вершин будет проанализирована ровно один раз. Отметим, что аналогичный подход используется и в валидаторе к данной задаче.

Асимптотическая сложность решения составляет, таким образом, O(n²)

Код

Доказательство.

Пусть в графе любые k вершин имеют ровно одну общую смежную вершину (*)

Лемма 1. У любых двух вершин ровно k - 1 общая смежная вершина.

Рассмотрим две произвольные различные вершины s, t. Пусть v₁, v₂, ..., v_l — все различные общие смежные вершины этих двух вершин. Если l ≥ k, то мы получим, что вершины из множества {v₁, ..., v_k} имеют две общие смежные вершины s, t, что противоречит (*). Пусть теперь l ≤ k - 2. Рассмотрим множество вершин S = {s, t, v₁, ..., v_l}, состоящее из 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 = {v₁, ..., v_k, v_k + 1}, в котором v₁, ... v_k — произвольные попарно различные вершины нашего графа, v_k + 1 — их общая смежная вершина. Приведем конструктивный способ построения полного подграфа на основе этого множества. Осуществим k - 1 итерацию, на i-ой итерации будем рассматривать вершину v_i. Если эта вершина смежна со всеми вершинами v_i + 1, ..., v_k, то перейдем к следующей итерации. Иначе рассмотрим множество T = {v₁, ..., v_i - 1, v_i + 1, ...v_k + 1}. У вершин из T существует ровно одна общая смежная вершина u (не совпадающая, очевидно, с v_i, поскольку v_i смежна не со всеми вершинами из T). Заменим вершину v_i на u и перейдем к следующей итерации. После окончания последней итерации множество S, очевидно, будет являться множеством вершин полного подграфа.

Покажем, что при k ≥ 3 наш граф — это полный граф из k + 1 вершины. Согласно лемме 2, в этом в графе найдется полный подграф с множеством вершин S = {v₁, ..., v_k + 1}. Допустим, что в нашем графе найдется вершина u, не принадлежащая S. Так как S — множество вершин полного подграфа, а любые две вершины согласно (1) имеют ровно k - 1 общую вершину, то все общие смежные вершины v₁ и v₂ (как и любых двух различных вершин из S) лежат в S. Если любые k вершин имеют общую смежную вершину, то и любые i (2 ≤ i ≤ k - 1) вершин имеют общую смежную вершину (возможно, не единственную). В частности, поскольку k ≥ 3, общую смежную вершину имеют вершины v₁, v₂, u, и эта вершина принадлежит S (как общая смежная вершина v₁ и v₂). Если допустить, что у 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 в этом блоке. Решим задачу динамическим программированием: d_i, j – верно ли, что существует ключ, первые i символов которого – нули и при использовании которого будет выписана строка, получаемая конкатенацией всех (q, j)-суффиксов сообщения. Переходы в этой динамике основаны на постановке в i-ую позицию ключа либо нуля, либо единицы (каждый раз нужно выбирать минимальный допустимый символ). Для восстановления самого ключа требуется сохранять для каждой подзадачи и сами выбранные символы, либо анализировать сами значения динамики.

Асимптотическая сложность решения — O(k·|s|² + |p|).

Код