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 \ne 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 \leq 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_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_n^{k_n}$, the number of co-prime integers is $(p_1^{k_1}-p_1^{k_1-1}) \cdot (p_2^{k_2}-p_2^{k_2-1}) \cdot \ldots (p_n^{k_n}-p_n^{k_n-1})$. Factorization of $n$ can be done in $O(\sqrt{n})$ time.↵
↵
E. Backup↵
------------------------↵
↵
In this problem we are given a rooted tree. At one step, one node is removed. If the node is being removed and its immediate ancestor is still present, the value in this ancestor is increased by $1$ (initially all values are equal to $1$). If the value of some node is equal to $k$, it should be removed at the next step. The goal is to maximize the number of step when root is removed.↵
↵
Notice, that if the root has only $k - 1$ descendant we can remove the whole tree before touching the node $n$. Otherwise, descendants should be split in three sets: totally removed subtrees, subtrees with their root remaining, and one subtree, whose root is removed at the end causing the node $n$ to be removed as well. Run depth-first search to compute the following value of dynamic programming:↵
↵
$a(v)$ is the number of nodes we can remove in subtree of $v$ if we are allowed to remove $v$ at any point. One can show that $a(v)$ equals the total number of nodes in the subtree.↵
↵
$b(v)$ is the number of nodes we can remove in subtree of $v$ if we are not allowed to touch node $v$. If there are less than $k - 1$ descendants, $b(v)$ is equal to $a(v) - 1$. Otherwise, we should pick $k - 2$ descendant to use value $a(u)$, while for other we use $b(u)$. This $k - 2$ descendants are selected by maximum value of $a(u) - b(u)$.↵
↵
$c(v)$ equal to the number of nodes we can remove if we are allowed to remove node $v$ but this should be done at the very end. Value of $c(n)$ is the final answer. We have to select some $k - 2$ descendants to use $a(u)$, one to use $c(u)$ and for others we take $b(u)$. Try every descendant as a candidate for $c(u)$ and for other use greedy algorithm to pick best $a(u) - b(u)$. Precompute the sorted array of all descendants and compute the sum of $k - 2$ best. If descendant $x$ to be used with $c(x)$ is among these $k - 2$ use the $k - 1$ (there should be at least $k - 1$ descendants, otherwise we destroy the whole subtree).↵
↵
The overall complexity is $O(n \log n)$.↵
↵
F. Lying Processors↵
-------------------↵
↵
We are going to use the fact that $n \leq 7$ and compute profile dynamic programming. If we already filled first $i$ columns of the table and everything is correct for first $i - 1$ columns, we only need to know the state of last to columns in order to be able to continue.↵
↵
Let $dp(i, m1, m2)$, where $i$ varies from $1$ to $m$, $m1$ and $m2$ are bitmasks in range from $0$ to $2^n - 1$ mean the minimum number of processors required to fill first $i$ columns in order to make first $i - 1$ columns correct and last two columns be filled as $m1$ and $m2$ respectively. The number of different states is $O(m \cdot 2^{2n})$. Finally, to compute the relaxations we try all possible masks $m3$ for the new state $dp(i + 1, m2, m3)$.↵
↵
Applying bit operations and some precomputations we obtain $O(m \cdot 2^{3n})$ running time. We can speed it up a lot by precomputing all valid $m3$ for a pair of $(m1, m2)$.↵
↵
Exercise: come up with $O(nm 2^{2n})$ solution.
---------------------↵
↵
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 \ne 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 \leq 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_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_n^{k_n}$, the number of co-prime integers is $(p_1^{k_1}-p_1^{k_1-1}) \cdot (p_2^{k_2}-p_2^{k_2-1}) \cdot \ldots (p_n^{k_n}-p_n^{k_n-1})$. Factorization of $n$ can be done in $O(\sqrt{n})$ time.↵
↵
E. Backup↵
------------------------↵
↵
In this problem we are given a rooted tree. At one step, one node is removed. If the node is being removed and its immediate ancestor is still present, the value in this ancestor is increased by $1$ (initially all values are equal to $1$). If the value of some node is equal to $k$, it should be removed at the next step. The goal is to maximize the number of step when root is removed.↵
↵
Notice, that if the root has only $k - 1$ descendant we can remove the whole tree before touching the node $n$. Otherwise, descendants should be split in three sets: totally removed subtrees, subtrees with their root remaining, and one subtree, whose root is removed at the end causing the node $n$ to be removed as well. Run depth-first search to compute the following value of dynamic programming:↵
↵
$a(v)$ is the number of nodes we can remove in subtree of $v$ if we are allowed to remove $v$ at any point. One can show that $a(v)$ equals the total number of nodes in the subtree.↵
↵
$b(v)$ is the number of nodes we can remove in subtree of $v$ if we are not allowed to touch node $v$. If there are less than $k - 1$ descendants, $b(v)$ is equal to $a(v) - 1$. Otherwise, we should pick $k - 2$ descendant to use value $a(u)$, while for other we use $b(u)$. This $k - 2$ descendants are selected by maximum value of $a(u) - b(u)$.↵
↵
$c(v)$ equal to the number of nodes we can remove if we are allowed to remove node $v$ but this should be done at the very end. Value of $c(n)$ is the final answer. We have to select some $k - 2$ descendants to use $a(u)$, one to use $c(u)$ and for others we take $b(u)$. Try every descendant as a candidate for $c(u)$ and for other use greedy algorithm to pick best $a(u) - b(u)$. Precompute the sorted array of all descendants and compute the sum of $k - 2$ best. If descendant $x$ to be used with $c(x)$ is among these $k - 2$ use the $k - 1$ (there should be at least $k - 1$ descendants, otherwise we destroy the whole subtree).↵
↵
The overall complexity is $O(n \log n)$.↵
↵
F. Lying Processors↵
-------------------↵
↵
We are going to use the fact that $n \leq 7$ and compute profile dynamic programming. If we already filled first $i$ columns of the table and everything is correct for first $i - 1$ columns, we only need to know the state of last to columns in order to be able to continue.↵
↵
Let $dp(i, m1, m2)$, where $i$ varies from $1$ to $m$, $m1$ and $m2$ are bitmasks in range from $0$ to $2^n - 1$ mean the minimum number of processors required to fill first $i$ columns in order to make first $i - 1$ columns correct and last two columns be filled as $m1$ and $m2$ respectively. The number of different states is $O(m \cdot 2^{2n})$. Finally, to compute the relaxations we try all possible masks $m3$ for the new state $dp(i + 1, m2, m3)$.↵
↵
Applying bit operations and some precomputations we obtain $O(m \cdot 2^{3n})$ running time. We can speed it up a lot by precomputing all valid $m3$ for a pair of $(m1, m2)$.↵
↵
Exercise: come up with $O(nm 2^{2n})$ solution.
