## easy1. Задача Минимакс

:::spoiler Подсказка 1
:::info
Сделаем бинарный поиск по ответу. Теперь нужно проверить, может ли ответ быть не меньше какого то $k$.
:::

:::spoiler Подсказка 2
:::info
Для фиксированного $k$ представим каждую строку $i$ матрицы как маску, в которой $j$-й бит равен $1$, если $a_{i,j} \ge k$ и $0$ в противном случае. Тогда если у некоторых двух строк битовый or их масок равен $2^m - 1$, то ответ не меньше $k$.
:::

:::spoiler Подсказка 3
:::info
Количество различных масок будет достаточно небольшим.
:::

:::spoiler Разбор
:::info
Сделаем бинарный поиск по ответу. Теперь нужно проверить, может ли ответ быть не меньше какого-то $k$.

Представим каждую строку $i$ матрицы как маску, в которой $j$-й бит равен $1$, если $a_{i,j} \ge k$ и $0$ в противном случае. Тогда если у некоторых двух строк битовый or их масок равен $2^m - 1$, то ответ не меньше $k$.

Чтобы быстро это проверить, для каждой маски сохраним существует ли строка в матрице с такой маской. Переберём две маски от $0$ до $2^m - 1$ и проверим, что их or равен $2^m - 1$ и для обоих масок существуют строки с такой маской.

Такая проверка будет работать за $O(n + 4^m)$. Если в качестве второй маски перебирать только надмаски первой, можно получить $O(n + 3^m)$, но решение заходит и без этой оптимизации.

Асимптотика: $O((n + 3^m) \cdot \log{A})$, где $A$ --- максимально возможное значение $a_{i,j}$.
:::

## easy2. Dog Show

:::spoiler Подсказка 1
:::info
Переберите позицию, в которой окажется собака в момент времени $T$.
:::

:::spoiler Подсказка 2
:::info
Для фиксированной конечной позиции $k$ всегда выгодно подождать в начале $T - k - 1$ секунд, после чего непрерывно идти вперёд, по пути съедая всю еду, которая уже остыла.
:::

:::spoiler Разбор
:::info
Переберём позицию $k$, в которой окажется собака в момент времени $T$. При фиксированной конечной позиции $k$ всегда выгодно подождать в начале $T - k - 1$ секунд, после чего непрерывно идти вперёд, по пути съедая всю еду, которая уже остыла.

Если конечная позиция собаки $k$, то можно съесть еду в позиции $i$ тогда и только тогда, когда выполняются следующие условия:

$t_i < T - k + i$
$i \le k$

Ответ для фиксированного $k$ --- это количество $i$, для которых выполняются эти условия. Чтобы быстро его считать, перенесём $i$ влево и получим:

$t_i - i < T - k$

Будет поддерживать ordered set, в котором хранятся значения $t_i - i$ для всех $i \le k$. Тогда текущий ответ --- это количество меньших чем $T - k$ в set'е, которое можно найти с помощью order_of_key.

Асимптотика: $O(n \cdot \log{n})$.
:::

## easy3. Подземная система

:::spoiler Подсказка 1
:::info
Постройте взвешенный граф, в котором длина кратчайшего пути от $1$ до $n$ является ответом на задачу.
:::

:::spoiler Подсказка 2
:::info
В новом графе сопоставим вершину каждой паре $(v, c)$, где $v$ --- вершина в исходном графе, $c$ --- номер текущей линии. Если убрать в новом графе все неиспользуемые вершины, вершин будет порядка $O(m)$.

Для каждого ребра исходного графа проведём соответствующее ребро веса $0$ в новом графе. Дополнительно для каждой вершины $v$ исходного графа проведём рёбра веса $1$ между всеми парами $((v, c1), (v, c2))$, означающие переход на новую линию.

В таком графе $O(m + n^2)$ рёбер. Как срезать их количество до $O(m)$?
:::

:::spoiler Разбор
:::info
Построим взвешенный граф, в котором длина кратчайшего пути от $1$ до $n$ является ответом на задачу.

В новом графе сопоставим вершину каждой паре $(v, c)$, где $v$ --- вершина в исходном графе, $c$ --- номер текущей линии. Если убрать в новом графе все неиспользуемые вершины, вершин будет порядка $O(m)$.

Чтобы учесть возможность смены текущей линии, для каждой вершины $v$ исходного графа создадим в новом графе фиктивную вершину $u$. Для всех $c$ проведём ориентированные рёбра $(v, c) \rightarrow u$ веса $1$ и $u \rightarrow (v, c)$ веса $0$. Суммарно в новом графе будет порядка $O(m)$ рёбер.

Чтобы найти ответ на задачу, найдём в новом графе длину кратчайшего пути из $1$ в $n$ с помощью 0-1 BFS.

Асимптотика: $O(m \cdot \log{m})$.
:::

## easy4. Stringforces

:::spoiler Подсказка 1
:::info
Сделайте бинарный поиск по ответу. Теперь нужно научиться проверять, можно ли заменить знаки вопроса на буквы так, чтобы для каждой буквы существовал отрезок из этой буквы длины хотя бы $x$.
:::

:::spoiler Подсказка 2
:::info
$dp_{mask}$ --- минимальный префикс строки, который для каждой буквы из $mask$ содержит подстроку из этой буквы длины хотя бы $x$. Ответ больше или равен $x$, если $dp_{2^k-1} \le n$. Как быстро посчитать такое ДП?
:::

:::spoiler Разбор
:::info
Сделаем бинарный поиск по ответу. Чтобы проверить, не меньше ли ответ какого то $x$, посчитаем $dp_{mask}$ --- минимальный префикс строки, который для каждой буквы из $mask$ содержит подстроку из этой буквы длины хотя бы $x$. Ответ больше или равен $x$, если $dp_{2^k-1} \le n$.

Чтобы быстро посчитать такое ДП, предпросчитаем $next_{c,pos}$ --- начало первого после $pos$ отрезка длины $x$, который содержит только буквы $c$ и знаки вопроса (или бесконечность, если такого нет).

Будем считать ДП вперёд, перебирать символ $c$, который мы сейчас добавим, и обновлять $dp_{mask | 2^c}$ через $next_{c, dp_{mask}} + x$.

Асимптотика: $O((n \cdot k + 2^k \cdot k) \cdot \log{n})$.
:::

## easy5. Открытие порталов

:::spoiler Подсказка 1
:::info
Если порталы расположены во всех вершинах графа, то ответ — сумма длин ребер в минимальном остовном дереве, которое можно найти алгоритмом Краскала.
:::

:::spoiler Подсказка 2
:::info
Ответ --- расстояние от вершины $1$ до ближайшего портала плюс сумма длин рёбер в минимальном остовном дереве графа из всех вершин-порталов, в котором между каждыми двумя вершинами есть ребро с весом, равным кратчайшему расстоянию между этими вершинами. Среди всех таких рёбер имеет смысл рассмотреть только $O(n)$ рёбер.
:::

:::spoiler Разбор
:::info
Сперва заметим, что если порталы расположены во всех вершинах графа, то ответ --- сумма длин ребер в минимальном остовном дереве, которое можно найти алгоритмом Краскала. Однако порталы расположены не во всех вершинах. Попробуем это исправить.

Сделаем небольшой предпросчет: запустим алгоритм Дейкстры одновременно из всех порталов и посчитаем 2 массива: $d_i$ --- расстояние от вершины $i$ до ближайшего портала и $p_i$ --- ближайший к вершине $i$ портал.

Теперь рассмотрим выполнение алгоритма Краскала на графе, состоящем только из порталов. На первой итерации этот алгоритм выберет ребро с минимальным весом среди всех ребер, соединяющем порталы. Только в исходном графе это могут быть не только ребра, но и пути.

Пусть такой кратчайший путь --- из портала $x$ в портал $y$. Заметим, что можно найти путь не длиннее, такой, что $p_i$ на нем будет меняться ровно один раз. Действительно, $p_x = x$, $p_y = y$, значит, на кратчайшем пути хотя бы раз меняется значение $p_i$. Пусть оно меняется на ребре $i \rightarrow j$, причем $p_i = x$. Поскольку путь от $j$ до $p_j$ --- кратчайший путь от $j$ до портала, путь не длиннее пути из $x$ в $y$.

Тогда, т.к. $p_i = x$, $p_j = y$, можно рассчитать длину этого пути: она равна $d_i + w(i, j) + d_j$, где $w(i, j)$ --- вес ребра $(i, j)$. Алгоритм Краскала прибавит эту величину к ответу и объединит порталы $x$ и $y$. При этом объединятся поддеревья ближайших к ним вершин.

А теперь видим, что ничего не изменилось, и следующее по весу ребро можно найти точно таким же способом --- $\min{d_i + w(i, j) + d_j}$. Если это ребро снова лежит между вершинами $x$ и $y$, то DSU не даст посчитать это ребро, иначе это ребро соединяет другую пару порталов и войдет в ответ.

Как это считать. Из определения ребер в новом графе нетрудно понять, что их столько же, сколько и в исходном: каждому ребру $(i, j)$ веса $w(i, j)$ в старом графе соответствует ребро $(p_i, p_j)$ веса $d_i + w(i, j) + d_j$ в новом графе. Поэтому построим новый граф и запустим на нем алгоритм Краскала --- он посчитает вес минимального остовного дерева в графе, где вершины --- порталы.

Осталось заметить, что если в стартовой вершине есть портал, то мы нашли ответ, а если нет --- то надо сначала дойти до ближайшего портала, чтобы можно было начать считать миностов. Для этого можно просто в конце прибавить к ответу число $d_1$.

Асимптотика: $O(m \log n).$
:::

## extra. Пусть будет

:::spoiler Подсказка 1
:::info
Пусть:

- $cnt_i$ --- количество задач, назначенных сотруднику $i$
- $sum_i$ --- сумма $cnt_i$ во всём поддереве $i$
- $sz_i$ --- размер поддерева $i$

Решение корректно тогда и только тогда, когда $sum_1 = n$ и для всех $i$ выполняется $sum_i \le sz_i$.
:::

:::spoiler Подсказка 2
:::info
Задача решается жадным алгоритмом.
:::

:::spoiler Подсказка 3
:::info
Будет работать такой жадный алгоритм:

Изначально все $cnt_i$ равны $0$. Будем поддерживать приоритетную очередь, в которой для всех возможных $i$ лежит значение, которое прибавится к ответу, если мы назначим сотруднику ещё одну задачу, т.е. $f_i \cdot ((cnt_i + 1) ^ 2 - {cnt_i} ^ 2)$.

На каждой из $n$ итераций возьмём минимальный элемент из приоритетной очереди. Проверим, корректным ли будет решение, если мы добавим ещё одну задачу соответствующему сотруднику. Если да, то добавим её и положим в приоритетную очередь новое значение для сотрудника.

Как быстро проверять корректность решения?
:::

:::spoiler Разбор
:::info
Пусть:

- $cnt_i$ --- количество задач, назначенных сотруднику $i$
- $sum_i$ --- сумма $cnt_i$ во всём поддереве $i$
- $sz_i$ --- размер поддерева $i$

Решение корректно тогда и только тогда, когда $sum_1 = n$ и для всех $i$ выполняется $sum_i \le sz_i$. Будет работать следующий жадный алгоритм:

Изначально все $cnt_i$ равны $0$. Будем поддерживать приоритетную очередь, в которой для всех возможных $i$ лежит значение, которое прибавится к ответу, если мы назначим сотруднику ещё одну задачу, т.е. $f_i \cdot ((cnt_i + 1) ^ 2 - {cnt_i} ^ 2)$.

На каждой из $n$ итераций возьмём минимальный элемент из приоритетной очереди. Проверим, корректным ли будет решение, если мы добавим ещё одну задачу соответствующему сотруднику. Если да, то добавим её и положим в приоритетную очередь новое значение для сотрудника.

Чтобы быстро проверять корректность решения, будем для каждого сотрудника $i$ хранить значение $can_i = sz_i - sum_i$. Решение корректно, если все $can_i \ge 0$.

При добавлении одной задачи сотруднику $x$ все $can_i$ на пути от $x$ до корня уменьшаются на $1$. Решение корректно после добавления задачи сотруднику $x$ если минимум $can_i$ на пути от $x$ до корня не меньше $1$.

Нам нужно быстро прибавлять на пути до корня и брать минимум на пути до корня. Такая задача решается при помощи Heavy-Light декомпозиции.

Асимптотика: $O(n \log^2{n})$.
:::