A. Маленькие числа

Для начала разложим числа a и b на простые.

Теперь заметим, что если какое-то простое число p входит в произведение ab в степени выше первой, то мы можем либо сразу поделить оба числа на число p, либо если же одно из чисел не делится на p, то перенесём в него множитель p из другого числа, после чего поделим на p.

Очевидно, что чётность вхождения простых чисел в произведение ab не меняется во всех операциях. Тогда давайте оставим все простые в первой степени. Остались числа p₁, p₂, ..., p_n. Давайте назовём произведение всех этих простых чисел d, d ≤ ab. Утверждается, что этих простых не может быть больше 14. Если 1 ≤ a, b ≤ 10⁹, то произведение ab ≤ 10¹⁸, а произведение первых 15 простых чисел превышает 10¹⁸) Теперь заметим, что конечный ответ — пара чисел (x, y) таких, что xy = d. Из этого следует, что второй элемент пары определяется однозначно по первому. Переберём всевозможные делители d за число x за O(2ⁿ), и выберем наилучшую пару.

B. Новая клавиатура

Используем для решения метод динамического программирования. Состояние — d[i][j][k], где i — флаг, обозначающий тип предыдущего действия (0, если это было переключение раскладки, и 1, если это был набор символа), j — номер текущей раскладки, и k — количество набранных символов. Значение — минимальное время, необходимое, чтобы достичь этого состояния.

Переберем k. Для фиксированного k переберем j от 1 до n два раза. Обновим d[0][j % n + 1][k] = min(d[0][j % n + 1][k], min(d[0][j][k] + b, d[1][j][k] + a)). Перебрать j от 1 до n два раза нужно потому, что после набора k-го символа может быть включена раскладка с номером большим, чем раскладка, в которой будет набран следующий символ, и будет необходимо произвести переключение раскладок по циклу до нужной. После этого переберем j еще раз и обновим значения для k + 1. Если в j-й раскладке есть k-й символ сообщения, d[1][j][k + 1] = min(d[0][j][k], d[1][j][k]) + c.

В конце ответ равняется min(d[1][j][m]), где m = length(s), по всем j от 1 до n.

C. Складывание фигуры

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

Возьмем любую из клеток сложенной фигуры с минимальной координатой по оси OX — клетку (x_i, y_i). За линию сгиба возьмем вертикальную прямую x = x_i, касающуюся этой клетки. Теперь слева нужно восстановить k - n клеток первоначальной фигуры, чтобы после складывания левой части вдоль линии сгиба на правую получилась данная во входных данных сложенная фигура. Так как k - n ≤ n (иначе после сгиба получилось бы больше n клеток), достаточно выделить из сложенной фигуры k - n клеток, образующих связную фигуру, содержащую клетку (x_i, y_i). Это можно сделать простым обходом в глубину.

D. Остроугольные треугольники

Для подсчета числа остроугольных треугольников достаточно из общего числа треугольников вычесть количество прямоугольных и тупоугольных треугольников. Будем считать три точки на одной прямой вырожденным тупоугольным треугольником.

Общее количество треугольников, которые можно построить с вершинами в заданных точках равно C_n³.

Заметим факт: количество прямоугольных и тупоугольных треугольников равно количеству прямых и тупых углов с вершинами в заданных точках.

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

Время работы решения: O(n²log(n)).

E. Объединение массивов

Приведем два решения этой задачи — за O(k²·log(k)) и O(k²).

Решение за O(k²·log(k)):

Разобьем решение задачи на три пункта:

• 1) Для каждого массива X (A или B) и каждой длины 1 ≤ length ≤ |X| найдем minSubsequence_X[length] — лексикографически минимальную подпоследовательность X длины length;
• 2) Переберем длину подпоследовательности в первом массиве — 1 ≤ t ≤ min(k - 1, |A|). Если 1 ≤ k - t ≤ |B|, возьмем minSubsequence_A[t] и minSubsequence_B[k - t], их надо объединить;
• 3) Объединим две подпоследовательности в одну, получив тем самым лексикографически минимальную подпоследовательность длины k, обновим ответ.

1) Чтобы найти minSubsequence_X[length] для каждого length, выполним следующие пункты:

• Посчитаем next[i][c], в котором будет храниться следующее после i вхождение символа c в X;
• Посчитаем firstSymbol[length][i] — первый символ лексикографически минимальной подпоследовательности массива X[i..|X| - 1] длиной length. Для этого заметим следующее:
  • Если j₁ = next[i][1] существует, то firstSymbol[1][i], firstSymbol[2][i], ... firstSymbol[|X| - j₁][i] начинаются с 1;
  • Если j₂ = next[i][2] существует, то firstSymbol[|X| - j₁ + 1][i], ..., firstSymbol[|X| - j₂][i] начинаются с 2;
  • ...
  • Если j_|alphabet| = next[i][|alphabet| существует, то firstSymbol[max(|X| - j₁, |X| - j₂, ..., |X| - j_{|alphabet| - 1}) + 1][i], ..., firstSymbol[|X| - j_|alphabet|][i] начинаются с |alphabet|.
  где alphabet — максимальное возможное число в массиве X.
• Посчитав firstSymbol[length][i], можно восстановить лексикографически минимальную подпоследовательность X для каждой длины итеративно по одной букве.

Этот пункт работает за O(|X|²).

3) Найдя две лексикографически минимальные подпоследовательности S_A и S_B, их надо объединить в одну лексикографически минимальную длиной k. Будем двигаться по подпоследовательностям двумя указателями p₁ и p₂. Если S_Ap1 ≠ S_Bp2, то двигаем указатель, стоящий на меньшем числе. Если S_Ap1 = S_Bp2, двоичным поиском найдем наибольший общий префикс S_A[p₁..|S_A|] и S_B[p₂..|S_B|] и сравним следующие числа. Для сравнения подотрезков S_A и S_B можно использовать хеши.

Этот пункт работает за O((|S_A| + |S_B|)·log(max(|S_A|, |S_B|))) = O(k·log(k)).

Итого, суммируя все три пунта, получаем асимптотику O(|A|² + |B|² + k²·log(k)) = O(k²·log(k)).

Решение за O(k²):

Будем называть массив A нулевым, а массив B — первым. Будем строить ответ по одному элементу. Также будем поддерживать вспомогательное значение dp[i][j], где i — номер массива (0 или 1), а j — индекс в этом массиве. dp[i][j] равно минимальному индексу в массиве 1 - i, с которого можно продолжать строить ответ, если в массиве i мы остановимся на индексе j.

На t-й из k итераций построения ответа будем находить минимальный элемент, такой, что, добавив его в ответ, последовательность можно закончить, то есть что оставшихся элементов хотя бы k - t - 1. Также нужно учесть, что подпоследовательности обоих массивов, из которых строится ответ, должны быть обе непустые.

После добавления найденного элемента v в ответ, за O(|A| + |B|) обновим значения dp. Для обновления будем пользоваться посчитанным в предыдущем решении массивом next.

F. Два поддерева

По условию, в k-поддереве обязательно есть вершины на глубине k. Временно отменим это требование.

Рассмотрим все k-поддеревья для некоторого k. Их можно разбить на классы эквивалентности. Каждой вершине поставим в соответствие c_k[v] — метку класса эквивалентности, которому принадлежит её k-поддерево.

При k = 0 все c₀[v] равны, так как 0-поддерево любой вершины — это она сама.

При k = 1 c₁[v] равно количеству детей вершины.

Научимся по массивам c_k[v] и c_m[v] строить массив c_k + m[v]. Для начала, поставим в соответствие каждой вершине v массив arr_k + m[v], который будет однозначно задавать класс эквивалентности её k + m-поддерева. Пусть u₁, ..., u_s — потомки вершины v на расстоянии k в порядке обхода dfs. Тогда поставим в соответствие вершине v массив arr_k + m[v] = c_k[v], c_m[u₁], ..., c_m[u_s]. То есть, k + m-поддерево вершины задаётся k-поддеревом вершины и m-поддеревьями нижней части k-поддерева. Ниже приведена иллюстрация для k = 3 и m = 1.

Чтобы получить для каждой вершины список её потомков на расстоянии k, запустим поиск в глубину от корня. Будем поддерживать в стеке путь до корня и каждую вершину класть в массив для её предка на расстоянии k.

Чтобы преобразовать массивы arr_k + m[v] в числа c_k + m[v], можно захешировать их, использовать бор или unordered_map из массива в номер. Время работы будет O(n), поскольку каждая веришна встречается в списках arr только один раз.

Имея массив c_k[v], можно легко проверить, что существует два одинаковых k-поддерева. Для этого нужно найти две вершины с одинаковым c_k, при этом нужно рассматривать только вершины, у которых есть потомки на расстоянии k от неё (это то требование, которое мы отменили в начале).

Чтобы найти максимальное k, посчитаем c₁[v], c₂[v], ..., c_2^t[v] (2^t — максимальная степень двойки, не превосходящая n). После этого используем аналог двоичных подъемов по k: начнём с k = 0 и по очереди попытаемся прибавить к нему 2^t, 2^t - 1, ..., 2⁰.

Время работы решения: O(nlog(n)).