Приветствую всех участников раунда!

237A - Free Cash

Из условия задачи легко понять, что если в некоторую минуту придут k человек, то Валере нужно иметь в кафе не менее k касс. Значит, требуется найти максимальное количество людей, которые придут в одну и ту же минуту, а это делается очень просто множеством способов, например, просто насчитав в массив cnt[h][m] количество людей, которые придут в час h и минуту m, а потом найдя в этом массиве максимум.

237B - Young Table

Решение, которое опишем ниже, почти никак не использует хитрую форму таблицы (кстати, такая таблица называется диаграммой Юнга). Заполним таблицу числами от 1 до s следующим способом: будем идти по строкам таблицы начиная с первой слева направо, после конца текущей строки переходим на начало следующей, и в процессе каждой из клеточек присвоим число по порядку обхода от 1 до s. Очень просто показать, что такой порядок чисел удовлетворяет оба неравенства из условия.

Теперь опишем алгоритм приведения таблицы из того вида, как она нам дана во входных данных, в описанный выше вид.

Возьмем число 1 и посмотрим, где оно находится в этих двух таблицах. Если это число стоит не на своем месте, то поставим его на свое место, соответственно то число, которое там стояло, встанет на старое место единицы. Аналогично сделаем для 2, 3, ..., s. Очевидно, что этот алгоритм сделает не более s шагов и приведет таблицу в вид, описанный в первом абзаце.

237C - Primes on Interval

Для начала с помощью решета Эратосфена выделим все простые числа от 1 до b и пометим их единичками в массиве d, то есть если p — простое, то d[p] = 1, иначе d[p] = 0.

Заметим, что если l — корректное число, то l + 1 тоже корректно. В самом деле, для позиций x от a до b - l количество простых в отрезке с началом в x могло лишь увеличиться (мы же длину отрезка увеличили, а значит, количество простых в нем никак не могло уменьшиться). А кроме того исчез из рассмотрения один отрезок с началом в точке b - l + 1, так как при увеличении длины его правый конец стал больше, чем число b.

Таким образом, мы показали, что функция f(l), возвращающая TRUE или FALSE (корректно число или нет) монотонна, а значит, мы можем с помощью бинарного поиска найти наименьшее l, для которого f(l) = TRUE, или ответить, что такого не существует.

Функция f(l) считается очень просто — можно проитерироваться по всем числам от a до b - l + 1 и найти для каждого начала количество простых чисел в соответствующем отрезке длины l, это можно сделать с помощью частичных сумм, насчитанных по массиву d.

237D - T-decomposition

Возьмем любое ребро начального графа, очевидно два его конца принадлежат некоторому множеству x_i, значит, вес любой его Д-декомпозиции как минимум 2. Покажем, как постороить декомпозицию именно такого веса. Для этого каждое из ребер исходного графа превратим в отдельное множество x_i, то есть все они будут состоять из двух элементов.

Очевидно, что первые два условия выполняются. Для выполнения третьего условия для начала соединим все множества по принципу: добавим ребро между двуми множествами, если их пересечение не пусто. Однако построенный таким образом граф не является деревом, покажем другой способ соединения вершин.

Для того, чтобы сделать из него дерево, достаточно для каждой вершины v начального дерева выделить все x_i, в которых она содержится, и соединить их в цепочку в любом порядке, добавив нужное количество ребер.

Несложно понять, что такой граф не будет содержать циклов, будет связен, а значит является деревом. Постоенная Д-декомпозиция будет иметь вес 2, и количество вершин n - 1.

237E - Build String

Эта задача несложно решается алгоритмом поиска максимального потока минимальной стоимости на трехслойном графе:

1. первый слой состоит из n вершин, каждая из которых отвечает за свою строку из входных данных; в i-ую вершину этого слоя входит по одному ребру из истока с пропускной способностью c_i и стоимостью i;

2. второй стой состоит за 26·n вершин, каждая из которых отвечает за количество определенных букв в каждой из строк из входных данных; в вершины этого слоя входят ребра только из первого слоя стоимостью 0 и пропускной способностью равной количеству соответствующих букв в соответствующей строке;

3. третий слой состоит из 26 вершин, каждая из которых отвечает за количество соответствующих букв в строке t; в вершины этого слоя входят ребра только из второго слоя стоимостью 0 и бесконечной пропускной способностью; кроме того, из вершин третьего слоя выходят ребра в сток стоимостью 0 и пропускной способностью, равной количеству соответствующих букв в строке t.

Если максимальный поток в этой сети меньше, чем |t|, то ответ равен  - 1, а иначе — минимальной стоимости максимального потока.