402A - Орехи

Достаточно просто перебрать количество коробок, которыми мы воспользуемся. Предположим, это число равно ans. Тогда всего мы можем получить ровно cnt = ans + min((k - 1) * ans, B) отсеков. Если cnt * v ≥ a, тогда ответ равен ans.

402B - Деревья в ряду

Достаточно перебрать высоту первого дерева от 1 до 1000. При фиксированной высоте первого дерева высоты деревьев однозначно определены, то есть имеют вид: a, a + k, a + 2k и так далее. После этого необходимо подсчитать количество операций, чтобы получить красивый ряд из деревьев при фиксированной минимальной высоте. Обновим ответ. После этого выведем для самой оптимальной высоты все операции.

402C - Ищем граф / 403A - Ищем граф

Опишу два решения.

Первое. Рассмотрим все пары чисел (i, j) (1 ≤ i < j ≤ n). Выведем 2n + p пар в лексикографическом порядке.

Во-первых, понятно что достаточно доказать, что 0-интересный граф верный. Более того, достаточно показать, что  - 3 интересный граф является верным. А как выглядит граф из первых 2n - 3 ребер. Очевидно, это граф имеет вид треугольников с общим ребром 1-2. Теперь предположим мы возьмем подмножество, которое не содержит вершины 1 и 2. Нетрудно увидеть, что в таких подграфах будет ноль ребер. Если в подмножестве ровно одна из вершин 1 или 2, то таких ребер будет k - 1, где k размер такого подграфа. Если две, то таких ребер 2 * (k — 2) + 1, где k размер подграфа.

Второе. Напишем перебор, который построит нам 0-интересные графы с количеством вершин 5, 6, 7, 8, 9. Теперь заметим, чтобы построить p-интерсный граф с n вершинами, достаточно построить 0-интересный граф, и потом в него p любых ребер, которых еще нет в графе. Как построить 0-интересный граф с n вершинами? Очень просто. Мы просто возьмем k несвязных компонент из построенных нами графов с вершинами от 5 по 9 так, чтобы суммарно в них было ровно n вершин.

402D - Улучшаем массив / 403B - Улучшаем массив

Опять опишу два решения.

Первое. Динамическое программирование. Подсчитаем динамическое программирование d[i][j] какое максимальный ответ мы можем получить, если перед нами сейчас префикс длины i и последний раз мы сокращали на gcd в позиции j. Понятно, что позиции следует перебирать в порядке убывания, как и размер префикса. Всего мы можем улучшить ответ в двух позициях в динамике из текущего состояния. А именно, d[i - 1][j] = max(d[i - 1][j], d[i][j]) — просто не будем сокращать на gcd текущий префикс. d[i - 1][i - 1] = max(d[i - 1][i - 1], d[i][j] + f(tgcd[j]) * i - f(tgcd[i - 1]) * i — выполним сокращение в текущей позиции. tgcd[i] — gcd всех чисел на префиксе длины i. Функция f(a) — возвращает красоту числа. Такую функцию просто реализовать за . Кроме того, можно ускорить работу этой функции, достаточно просто насчитать массив маленьких простых чисел. В таком решении очень важно не забыть, что каждый раз пересчитывать красоту чисел не нужно. Достаточно завести map < int, int >  — который сохранит уже посчитанные значения. База динамики d[n][n] = curBeauty — текущая красота массива.

Второе. Жадность. Возьмем самую правую позицию, которая может улучшить ответ. Выберем эту позицию, и сократим в ней на gcd. Докажем, почему так делать верно. Пусть оптимальное решение (последовательность сокращений) имеет вид r₁ > r₂ > ... > r_k. А мы построили решение l₁ > l₂ > ... > l_m используя жадность. Понятно, то r₁ ≤ l₁, поскольку до этого позиции  > l₁ не могли ничего улучшить, ведь иначе наша жадность взяла бы их в качестве своего первого выбора. С другой стороны, r₁ ≥ l₁, ведь иначе мы можем взять и сократить в позиции l₁ и только улучшить ответ, а это противоречило бы оптимальности решения r_i. То есть, r₁ = l₁, а значит, мы можем воспользоваться нашими соображениями и далее, для больших индексов i.

402E - Строго положительная матрица / 403C - Строго положительная матрица

Будем смотреть на матрицу a как на матрицу смежности некоторого графа из n вершин. Причем, если a_ij > 0, значит мы имеем ориентированное ребро в графе между вершинами (i, j). Иначе, мы получим, что ориентированного ребра нет. Тогда, пусть b = a^k. Тогда что обозначает b_ij? Верно, количество путей длины ровно k в нашем графе из вершины i в вершину j. Пусть pos такое, что a[pos][pos] > 0. То есть, у нас есть петля в графе. Значит, если из вершины pos достижимы все остальные вершины и наоборот, из всех остальных вершин достижима вершина pos, то тогда ответ YES, иначе ответ NO. Понятно, что если достижимость отсутствует, то понятно что для любого k a^k_ipos = 0. Если же достижимость имеется, то мы сможем добраться до петли, покрутиться некоторое количество раз в петле, а потом отправиться в нужную вершину.

403D - Красивые пары чисел

Во первых отметим, что на самом деле, длина последовательности не больше чем 50. Уже хорошо, а почему? Поскольку все числа b_i - a_i различны, то 0 + 1 + ... + 50 > 1000. Также представим, что мы имеем на самом деле последовательность попарно не пересекающихся отрезков, c_i = b_i - a_i + 1 — длина отрезка. . Хорошо. Посчитаем динамическое программирование: d[i][j][k] — количество последовательностей из чисел c₁ < c₂ < ... < c_i таких, что c_i ≥ 1 и c₁ + c₂ + ... + c_i = j и максимальное число в ней строго меньше чем k. Такая динамика поможет нам посчитать количество способов назначить длины отрезкам. Пересчитать такую динамику очень просто:

• база d[0][0][1] = 1,
• d[i][j][k + 1] = d[i][j][k + 1] + d[i][j][k] — просто увеличим верхнюю границу.
• d[i + 1][j + k][k + 1] = d[i + 1][j + k][k + 1] + d[i][j][k] — ставим текущую границу в последовательность, тем самым увеличиваем сумму и верхнюю границу.

Такую динамику нужно написать, используя O(N²) памяти, где N = 1000. После этого, умножим каждое d[i][j][k] на i!, поскольку мы располагать последовательность c_i не в порядке возрастания. Таким образом мы умеем считать количество способов назначить длины отрезков.

Хорошо. Теперь как получить ответ для n, k? Пусть sum[len] = d[k][len][x], где x — некоторая верхняя граница. Очевидно, что нам дополнительно нужно еще раздать еще n - len единичек. С помощью этих единиц мы можем увеличивать расстояние между отрезками. Количество способов раздать эти единички равно числу C(n - len + k, k). Таким образом, для каждого n просуммируем по len полученные величины и сложим в ответ.

Также следует обратить внимание на то, массив C[n][k] должен быть достаточно большим и аккуратно расставить размерности.

403E - Два корневых дерева

Во-первых для каждой вершины первого и второго дерева подсчитаем две величины in[s], out[s] — время входа и время выхода из вершины в порядке обхода dfs из вершины 1. Теперь с каждому ребру из обоих деревьев мы сопоставим пару (p, q) — где p = min(in[u], in[v]), q = max(in[u], in[v]) где величины in, out для каждой вершины мы берем из дерева другого цвета. Теперь для каждой дерева мы построим два дерева отрезков (в сумме 4 дерева отрезков, да). В первом дереве отрезков мы будем пары хранить в следующем виде: мы будем хранить пару в вершине (вершина дерева отрезков это некоторый отрезок (l, r)) дерева отрезков тогда и только тогда, когда ее левая граница лежит внутри отрека (l, r). Аналогично, во втором дереве отрезков мы будем хранить пару в вершине (вершина дерева отрезков это некоторый отрезок (l, r)) дерева отрезков тогда и только тогда, когда ее правая граница лежит внутри отрека (l, r). Все пары в дереве отрезков мы будем хранить по возрастанию правой границы (левой во втором дереве). Такие деревья отрезков требуют памяти, и построить можно за время .

Хорошо. Как теперь ответить на запрос (l, r) — удалить ребра из дерева, такое что одна из вершин имеет время входа внутри (l, r) ? Будем спускаться по дереву отрезков. Предположим, мы сейчас находимся в некоторой его вершине. Поскольку в первом дереве мы храним все пары по возрастанию правой границы, то ответ на запрос, это некоторый суффикс массива его правый границы. После того, как мы обработаем эти ребра и начнем следующий этап, нам нужно модифицировать наше дерево. А именно, для каждой вершины дерева, в которой мы рассматривали суффиксы мы должны их удалить, иначе мы можем обработать их несколько раз. Таким образом, имеем решение за .

Авторское решение по Е: 6052738