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
Unable to parse markup [type=CF_TEX]
. 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,
Unable to parse markup [type=CF_TEX]
, 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
Unable to parse markup [type=CF_TEX]
is the step of another appearance o this pair. Without loss of generality letUnable to parse markup [type=CF_TEX]
, then p was obtained as a sum ofUnable to parse markup [type=CF_TEX]
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
Unable to parse markup [type=CF_TEX]
it was obtained as a sum ofUnable to parse markup [type=CF_TEX]
and q, so they were neighbors on the previous step. Two steps behind we had eitherUnable to parse markup [type=CF_TEX]
and q, orUnable to parse markup [type=CF_TEX]
andUnable to parse markup [type=CF_TEX]
(depending on which is greater,Unable to parse markup [type=CF_TEX]
or q) and so one. The process is similar to Euclid algorithm and continues while we don't have 1 and x. Finally, pairsUnable to parse markup [type=CF_TEX]
andUnable to parse markup [type=CF_TEX]
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
Unable to parse markup [type=CF_TEX]
andUnable to parse markup [type=CF_TEX]
. ifUnable to parse markup [type=CF_TEX]
, thenUnable to parse markup [type=CF_TEX]
. 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
Unable to parse markup [type=CF_TEX]
, the number of co-prime integers isUnable to parse markup [type=CF_TEX]
. Factorization of n can be done in
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:
Unable to parse markup [type=CF_TEX]
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 thatUnable to parse markup [type=CF_TEX]
equals the total number of nodes in the subtree.Unable to parse markup [type=CF_TEX]
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,Unable to parse markup [type=CF_TEX]
is equal toUnable to parse markup [type=CF_TEX]
. Otherwise, we should pick k - 2 descendant to use valueUnable to parse markup [type=CF_TEX]
, while for other we useUnable to parse markup [type=CF_TEX]
. This k - 2 descendants are selected by maximum value ofUnable to parse markup [type=CF_TEX]
.Unable to parse markup [type=CF_TEX]
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 ofUnable to parse markup [type=CF_TEX]
is the final answer. We have to select some k - 2 descendants to useUnable to parse markup [type=CF_TEX]
, one to useUnable to parse markup [type=CF_TEX]
and for others we takeUnable to parse markup [type=CF_TEX]
. Try every descendant as a candidate forUnable to parse markup [type=CF_TEX]
and for other use greedy algorithm to pick bestUnable to parse markup [type=CF_TEX]
. Precompute the sorted array of all descendants and compute the sum of k - 2 best. If descendant x to be used withUnable to parse markup [type=CF_TEX]
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 
.
F. Lying Processors
We are going to use the fact that
Unable to parse markup [type=CF_TEX]
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
Unable to parse markup [type=CF_TEX]
, where i varies from 1 to m, m1 and m2 are bitmasks in range from 0 toUnable to parse markup [type=CF_TEX]
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 isUnable to parse markup [type=CF_TEX]
. Finally, to compute the relaxations we try all possible masksUnable to parse markup [type=CF_TEX]
for the new stateUnable to parse markup [type=CF_TEX]
.Applying bit operations and some precomputations we obtain
Unable to parse markup [type=CF_TEX]
running time. We can speed it up a lot by precomputing all validUnable to parse markup [type=CF_TEX]
for a pair ofUnable to parse markup [type=CF_TEX]
.Exercise: come up with
Unable to parse markup [type=CF_TEX]
solution.
