A. Time Through the Glass

Consider the movement of "real" and "reflected" hands. If "real" hands rotates for some angle, "reflected" hand passes exactly the same angle in other direction. Thus, the sum of angles of two hands is always equal 360 degrees. For each hand we will find its resulting position independently. For hour hand it is 12 minus the current position, while for minute hand it is 60 minus current position. In both cases we should not forget to replace 12 or 60 with 0.

B. Palindromic Feature

Consider some substring of the given string that is a palindrome. We can remove its first character and its last character and the string will remain a palindrome. Continue this process till the string length becomes two or three (depending on parity).

The number of substrings of length two or three is linear, same as their total length. Thus, we can apply naive algorithm to select optimum palindrome. If there is no palinromic substring of length two or three, print  - 1.

C. Divide Them All

To solve this problem we will use a simple geometry fact that a line split a circle in two parts of equal area if and only if this line passes through the circle center. Similarly, a line splits a rectangle in two parts of equal area if and only if it passes through the intersection point of its diagonals. In both cases, sufficiency follows from point symmetry and necessity can be shown by considering a line that passes through the center and is parallel to a given one.

Now we only need to check whether there exists a line that contains all the centers. For the sake of simplicity we will work with doubled coordinates to keep them integer. This allows us to get the center of the rectangle by computing the sum of coordinates of two opposite vertices.

If there are no more than two distinct points among the set of all center, the answer is definitely positive. Otherwise, consider any pair of distinct points and check that each center belongs to the line they define. To check whether three points a, b and c (a ≠ b) belong to one line we can compute the cross product of vectors b - a and c - a. Overall complexity of this solution is O(n).

D. Interview Task

We would like to start with some lemmas.

Lemma 1. Any two neighboring integers are co-prime at any step.

Use math induction. Base case is trivial as 1 and 1 are co-prime. Consider the statement is correct for first n steps. Then, any integer produced during step n + 1 is a sum of two co-prime integers. However, gcd(a + b, b) = gcd(a, b), thus, any two neighbors are still co-prime.

Lemma 2. Each ordered pair of integers (a, b) appears as neighbors exactly once (and at one step only).

Proof by contradiction. Let k be the first step such that some ordered pair appeared for the second time. Denote this pair as (p, q) and i ≤ k is the step of another appearance o this pair. Without loss of generality let p > q, then p was obtained as a sum of p - q and q, thus during the steps i - 1 and k - 1 there was also a repetition of some pair, that produces a contradiction.

Lemma 3. Any ordered pair of co-prime integers will occur at some step.

Let p and q be neighbors at some step. Then, if p > q it was obtained as a sum of p - q and q, so they were neighbors on the previous step. Two steps behind we had either p - 2q and q, or p - q and 2q - p (depending on which is greater, p - q or q) and so one. The process is similar to Euclid algorithm and continues while we don't have 1 and x. Finally, pairs (1, x) and (x, 1) always appear at step x$. Moving along the actions in backward direction we conclude that any of the intermediate pairs should appear during the process, thus, pair (p, q) also appears.

Notice, that we are only interested in the first n steps, as any integer, produced on step x is strictly greater than x. Now, as we know that any pair of co-prime integers occurs exactly once we would like to compute the number of pairs (p, q) such that gcd(p, q) = 1 and p + q = n. if gcd(p, q) = 1, then gcd(p, p + q) = gcd(p, n) = 1. It means we only have to compute Euler function of integer n.

Compute Euler function is a well-studied problem. This know this is a multiplicative function, so n = p₁^k₁·p₂^k₂·...·p_n^k_n, the number of co-prime integers is (p₁^k₁ - p₁^k₁ - 1)·(p₂^k₂ - p₂^k₂ - 1)·... (p_n^k_n - p_n^k_n - 1). Factorization of n can be done in time.

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²ⁿ).