A. Время в зазеркалье

Рассмотрим движение "прямой" и "отражённой" стрелки. За то время, когда "прямая" стрелка повернётся на некоторый угол, "отражённая" повернётся на тот же угол, но в другую сторону, то есть суммарный угол поворота стрелок равен полному обороту. Для каждой стрелки независимо вычислим её позицию. Для часовой это 12 минус текущая позиция, а для минутной — 60 минус текущая позиция. В обоих случая надо не забыть заменить 12 или 60 на ноль.

B. Фактор палинромности

Пусть существует какая-то подстрока, являющаяся палиндромом. Если мы уберём первый и последний символ палиндрома, оставшаяся строка тоже будет палиндромом. Будем повторять процесс до тех пор, пока не останется строка из двух или трёх букв (в зависимости от чётности).

Подстрок длины два или три всегда линейное количество, и суммарная их длина также линейна, поэтому среди таких строк ответ можно выбрать наивным алгоритмом. Если же ни одна из подстрок такой длины не является палиндромом, то выведем  - 1.

C. Разделите их все

Для решения этой задачи нам потребуется простой геометрический факт, что прямая делит окружность на две равные части если и только если она проходит через её центр. Аналогично для прямоугольника, прямая делит его на две части равной площади если и только если она проходит через точку пересечения диагоналей. В обоих случаях достаточность следует из симметрии относительно этой точки, а необходимость может быть установлена проведением через эту точку прямой, параллельной данной.

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

Если среди построенного множества точек не более двух различных, то ответ точно положительный. В противном случае рассмотрим любую пару различных точек, и проверим, что все остальные точки лежат на определяемой этой парой прямой. Наиболее удобный способ проверить, что три точки a, b и c (a ≠ b) лежат на одной прямой~--- использовать векторное произведение векторов b - a и c - a. Итоговая сложность решения: O(n).

D. Задача для собеседования

Докажем несколько лемм.

Лемма 1. Числа, оказавшиеся на каком-то шаге соседними, являются взаимно простыми.

Докажем по индукции. База очевидна (1 и 1 взаимно просты). Пусть доказано для n шагов. Все числа, выписанные на n + 1-м шаге, являются суммой двух соседних на n-м шаге чисел, то есть суммой двух взаимно простых чисел. Но НОД (a + b, b) = НОД (a,b)=1. Лемма доказана.

Лемма 2. Никакая упорядоченная пара соседних чисел (a, b) не может возникнуть в последовательности более одного раза (ни на одном шаге, ни на разных).

Пусть это не так, тогда отметим номер k шага, на котором в первый раз возникло повторение (то есть повторилась пара, существующая на этом или на предыдущем шаге). Пусть пара (p, q) возникла на k-м и на i ≤ k-м шаге. Но тогда, если p > q, то p было построено как сумма соседей q и p - q (если p < q, то q было построено как сумма p и q - p), то есть на k - 1-м и на i - 1-м шагах также существовало повторение, что противоречит нашему предположению. Лемма доказана.

Лемма 3. Любая упорядоченная пара взаимно простых чисел неизбежно будет соседней на некотором шаге.

Пусть мы имеем числа pq, стоящие рядом на некотором шаге и пусть p > q (без ограничения общности). Тогда p было получено как сумма p - q+q, то есть на предыдущем шаге рядом стояли p - q и q. Если p - q < q, то два шага назад справа от q стояло число 2q - p, если p - q > q, то слева от p - q стояло число p - 2q и так далее. Так как p и q взаимно просты, то на каком-то шаге этот процесс, по сути являющийся разновидностью алгоритма Евклида, приведёт к тому, что с одной стороны окажется 1, а с другой — некоторое натуральное число. Но пара (1, x) или (x, 1) для любого x будет соседней последовательности на x-м шаге. А так как действия восстанавливаются однозначно, то это значит, что и исходная пара (p, q) в какой-то момент встретится в качестве соседней.

Таким образом, каждая упорядоченная пара взаимно простых чисел ровно один раз встречается в качестве соседей в заданной последовательности. Поэтому задача сводится к подсчёту количества упорядоченных пар взаимно простых чисел, дающих в сумме n. Так как если p и n взаимно просты, то и p и n - p взаимно просты, то количество таких пар можно поставить в однозначное соответствие количеству чисел, взаимно простых с n, или значению функции Эйлера от n.

Подсчёт же количества таких чисел является известной задачей и опирается на мультипликативность функции Эйлера: если n = p₁^k₁·p₂^k₂·...·p_n^k_n, то взаимно простых с n чисел будет (p₁^k₁ - p₁^k₁ - 1)·(p₂^k₂ - p₂^k₂ - 1)·... (p_n^k_n - p_n^k_n - 1). Раскладываем n на простые множители за время .

E. Резервное копирование

В задаче нам дано корневое дерево, на каждом шагу одна из вершин дерева удаляется. При этом, если корень вершины ещё не был удалён, то его значение увеличивается на 1 (изначально все значения равны 1). Если значение какой-то вершины становится равным k, то именно она удаляется на следующем шаге. Требуется максимизировать номер шага на котором будет удалена корневая вершина.

Заметим, что если у корневой вершины менее k - 1 потомка, то можно удалить все вершины дерева, перед тем как трогать вершину номер n. В противном случае, все дети корня разделяются на три множества: те, чьи поддеревья будут удалены полностью, те, у которых корень останется не тронутым, и одно поддерево, после удаления корня которого мы удаляем и саму вершину n. Сделаем обход в глубину нашего дерева и будем поддерживать три значения динамического программирования:

a(v) равняется количеству вершин, которые можно удалить в данном поддереве, если можно удалить вершину v и не обязательно последней. Несложно заметить, что a(v) равняется размеру поддерева.

b(v) равняется количеству вершин, которые можно удалить в данном поддереве, если вершина v должна остаться не тронутой. Равняется a(v), если у вершины v менее k - 1 сына. В противном случае нужно выбрать каких-то k - 2 потомка, для которых будет использовано значение a(u) и для всех остальных использовать b(u). В качестве таких k - 2 потомков выгодно взять вершины с максимальной разницей a(u) - b(u).

c(v) равняется количеству вершин, которые можно удалить в данном поддереве, если можно удалить вершину v, но она должна быть последней удалённой вершиной поддерева. Величина c(n) и будет являться ответом на задачу. Требуется выбрать какие-то k - 2 потомка, для которых будет использовано значение a(u), одного потомка, для которого мы используем c(u) и для всех остальных к ответу добавится b(u). Переберём, для какого из потомков будет использовано c(u) (то есть кто будет последним удалённым потомком, после чего будет удалена и вершина v). Теперь среди оставшихся требуется взять сумму всех значение b(u) и k - 2 максимальных a(u) - b(u). Для этого достаточно иметь предподсчитанными сумму всех b(u) и список сыновей, упорядоченных по a(u) - b(u). Если вершина x, для которой мы решили взять значение c(x) попадает в вершины с максимальной разностью, то использовать следующую k - 1 вершину (такая обязательно есть, иначе мы просто уничтожаем всё поддерево).

Итоговая сложность решения .

F. Процессоры-лжецы

Воспользуемся тем фактом, что n ≤ 7 и будем вычислять динамику по профилю. Пусть мы заполнили первых i столбцов таблицы, причём на первых i - 1 столбце все процессоры вернули ожидаемый результат. Тогда, для того чтобы продолжить заполнять таблицу нам важно лишь знать, какие из процессоров врут среди последних двух столбцов.

Посчитаем dp(i, m1, m2), где i меняется от 1 до m, а m1 и m2~--- битовые маски от 0 до 2ⁿ - 1. Значением динамики будет минимальное количество процессоров-лжецов, которое потребуется, чтобы заполнить первые i столбцов так, чтобы среди первых i - 1 столбца все процессоры вернули ожидаемый результат, а состояние процессоров в последнем и предпоследнем столбце были равны m1 и m2 соответственно. Всего различных состояний O(m·2²ⁿ). Наконец, для вычисления перехода будет перебирать новую маску m3 и пробовать перейти в состояние dp(i + 1, m2, m3).

Работая с масками с помощью предподсчёта и битовых операций получим результат O(m·2³ⁿ). Работу программы можно значительно ускорить, если предпосчитать все корректные переходы их каждой пары масок (m1, m2) (то есть запомнить все подходящие к ним маски m3).

Упражнение: придумайте, как получить решение за время O(nm2²ⁿ).