Yandex. Algorithm 2018: optimization track and ML task from Alice’s developers

A. Time in the looking glass

Time limit 1 second
Memory Limit 512Mb

The office where Bomboslav works has a stylish designer watch. Their dial has a standard marking: on the circle there are 60 divisions corresponding to minutes, 12 of which (starting from upwards from the center of the circle, then evenly with a step of five divisions) are larger than the others, that is, correspond to the clock. Stylish this watch makes the fact that the dial does not contain any numbers, since it is assumed that we all know well which division corresponds to which value of the current time.

Today over the workplace Bomboslava hanged such a clock. Periodically glancing at them, he first noticed some oddity in the direction of the arrows. Looking closer, Bomboslav discovered that in fact there was a mirror above his workplace, and the clock was located on the wall behind him. This means that Bomboslav sees the dial reflected on the vertical axis passing through its center. Now he wants to learn how to quickly determine the current current time, knowing the time that is shown on the reflected dial.

The clock is arranged in such a way that both hands move discretely, that is, the hour hand always points to one of the 12 major divisions corresponding to the current number of hours, and the minute hand to one of the 60 divisions corresponding to the current number of minutes.

Input format
The only line of input contains two integers. $$$h$and $$$m$( $$$0 \ le h \ le 11$, $$$0 \ le m \ le 59$) - the position of the hour hand and the position of the minute hand in the reflected dial, respectively. $$$h = 0$means the hour hand points vertically up, $$$h = 3$match the arrow pointing right to the right, $$$h = 6$- the arrow looks vertically down, $$$h = $$- strictly left. Similar instructions are valid for the minute hand for values $$$m = 0, m = 15, m = 30$and $$$m = 45$.

Output format
Output two integers $$$x$and $$$y$( $$$0 \ le x \ le 11$, $$$0 \ le y \ le 59$) - the real value of the current time on the clock.

Decision:
Consider the movement of the "direct" and "reflected" arrows. During the time when the "straight" arrow turns to a certain angle, the "reflected" turns to the same angle, but in the other direction, that is, the total angle of rotation of the arrows is equal to a full turn. For each arrow, we independently calculate its position. For hourly it is 12 minus the current position, and for the minute - 60 minus the current position. In both cases, you must not forget to replace 12 or 60 by zero.

B. Palindrome factor

Time limit 1 second
Memory Limit 512Mb

Arkady is a big fan of machine learning in any task. He believes in the limitless power of the magic of this popular young science. That is why Arkady constantly constantly comes up with more and more new factors that can be calculated for various objects.

Recall palindrome is a string that is equally read from beginning to end and from end to beginning. For each line in its database, Arkady wants to find its shortest substring consisting of at least two characters and being a palindrome. If there are several such substrings, Arkady wants to choose the lexicographically minimal one.

Input format
The only line of input contains one line from the Arcadius database - a non-empty sequence of lowercase English letters. The length of the string is at least 2 and does not exceed 200,000 characters.

Output format
Print the minimum length substring of the string from the input data, consisting of at least two characters and being a palindrome. Recall that among all such lines, Arkady wants to find the lexicographically minimal.

Decision:
Let there be some kind of substring that is a palindrome. If we remove the first and last character of the palindrome, the remaining string will also be the palindrome. We will repeat the process until a string of two or three letters remains (depending on the parity).

The substrings of length two or three are always a linear amount, and their total length is also linear, so the answer among these lines can be chosen by a naive algorithm. If none of the substrings of this length is a palindrome, then we derive $$$-1$.

C. Separate them all

Time limit 1 second
Memory Limit 512Mb

After work, Olya and Tolya decided to go to the shooting gallery together. After passing the introductory briefing and receiving weapons, they were in positions for firing, and opposite them are $$$n$targets All targets can be considered as figures inflicted on an infinite plane, with each target being a circle or a rectangle, the targets can overlap and intersect in an arbitrary manner.

Before shooting, Olga and Tolya want to make sure that they can uniquely identify the results of their shots. For this, they agreed to hold a straight line that will divide the plane with the targets into two parts. However, so that no one was hurt, they want to draw a straight line so that each target is divided exactly in half, that is, for each circle and each rectangle it must be true that the straight line divides it into two figures of equal area.

When Olya and Tolya finally finished working out all the conditions for dividing the target into two parts, they began to doubt that it was possible to hold such a direct line and asked you to answer this question.

Input format
The first line of the input contains an integer $$$n$( $$$1 \ le n \ le $ 100,00$) - the number of targets. Each of the following $$$n$strings contains an integer $$$t_i$( $$$0 \ le t_i \ le 1$) denoting the type of target. If a $$$t_i = 0$then the target is a circle and then three integers follow. $$$r_i$, $$$x_i$and $$$y_i$, determining the radius and coordinates of the center of the circle, respectively ( $$$1 \ le r_i \ le 1000$, $$$−10000 \ le x_i, y_i \ le 10000$). If $$$t_i = 1$, then the target is a rectangle, which is then defined by eight integers $$$x_ {1, i}, y_ {1, i}, x_ {2, i}, y_ {2, i}, x_ {3, i}, y_ {3, i}, x_ {4, i}, y_ {4, i}$- coordinates of all four vertices ( $$$−10000 \ le x_ {j, i}, y_ {j, i} \ le $ 1000$) listed in clockwise or counterclockwise order. It is guaranteed that these four vertices form a rectangle of nonzero area.

Output format
If there is a line that divides each of the existing circles and rectangles into two parts of the same area, output “Yes”. Otherwise, output “No”.

Decision:
To solve this problem, we need a simple geometric fact that a straight line divides a circle into two equal parts if and only if it passes through its center. Similarly for a rectangle, a straight line divides it into two parts of equal area if and only if it passes through the intersection point of the diagonals. In both cases, sufficiency follows from symmetry with respect to this point, and the need can be established by drawing a straight line parallel to this one through this point.

Now we just need to check whether all the centers of the figures given in the input data are true on the same line. For convenience, we will consider doubled coordinates of the centers; then, to obtain the center of the rectangle, it is enough to add the coordinates of two opposite vertices.

If among the constructed set of points there are at most two different points, then the answer is definitely positive. Otherwise, consider any pair of different points, and verify that all other points lie on the line defined by this pair. The most convenient way to check that three points $$$a$, $$$b$and $$$c$( $$$a \ ne b$) lie on one straight line - use vector product of vectors $$$b - a$and $$$c - a$. The final complexity of the solution: $$$O (n)$.

D. Task for interview

Time limit 3 seconds
Memory Limit 512Mb

Alexey regularly conducts interviews with candidates for an intern position. And although he had already conducted more than one hundred interviews, recently this process has not been easy for him - candidates began to solve all the tested and fulfilled tasks of Alexei without difficulty!

There is nothing to do, and on the threshold of the next interview, Aleksey came up with a new task. There is a numeric sequence, in the first step consisting of two numbers 1. At each step, the next step between each two adjacent elements is added a new element equal to their sum. After the first few steps, the sequence looks like this:
eleven
1 2 1
1 3 2 3 1
1 4 3 5 2 5 3 4 1

At the interview, Alexei wants to ask the candidate to write a program that, given the number $$$n$will determine how many times the number $$$n$will occur in sequence on $$$n$m step? Alexey has not yet learned how to solve his problem, but he heard that the candidate he will be interviewing now has achieved good results in sports programming, therefore, most likely, he will easily cope with this issue.

Input format
The input contains a single number. $$$n$( $$$1 \ le n \ le 10 ^ {13}$).

Output format
Output one integer equal to the number of occurrences of the number. $$$n$to the sequence described in the condition in step $$$n$.

Decision:
We prove several lemmas.

Lemma 1. Numbers that are neighboring at some step are mutually simple.

We prove by induction. The base is obvious (1 and 1 are mutually simple). Let it be proven for $$$n$steps. All numbers written on $$$n + 1$m step, are the sum
two adjacent on $$$n$th step of numbers, that is, the sum of two mutually simple numbers. But GCD ( $$$a + b$, $$$b$) = GCD ( $$$a$, $$$b$) = 1. The lemma is proved.

Lemma 2. No ordered pair of neighboring numbers. $$$(a, b)$can not occur in the sequence more than once (at one step, or at different).

Let it not so, then we note the number $$$k$the step in which the repetition occurred for the first time (that is, the pair that existed in this or the previous step was repeated). Let a couple $$$(p, q)$originated on $$$k$m and on $$$i$m step ( $$$i \ le k$). But then, if $$$p> q$then $$$p$was built as a sum of neighbors $$$q$and $$$p-q$(if a $$$p <q$then $$$q$was built as a sum $$$p$and $$$q-p$), that is, on $$$k-1$m and on $$$i-1$m steps also existed repetition, which contradicts our assumption.
The lemma is proved.

Lemma 3. Any ordered pair of mutually simple numbers will inevitably be a neighbor at some step.

Suppose we have numbers $$$pq$standing next to at some step and let $$$p> q$(without loss of generality). Then $$$p$was received as an amount $$$p-q$+ $$$q$that is, on the previous one
stood next to each other $$$p-q$and $$$q$. If a $$$p-q <q$then two steps back to the right of $$$q$there was a number $$$2q-p$, if a $$$p-q> q$then to the left of $$$p-q$there was a number $$$p-2q$and so on. Because $$$p$and $$$q$
are mutually simple, then at some step this process, which is essentially a kind of Euclidean algorithm, will lead to the fact that $$$1$and on the other - some
natural number. But a couple $$$(1, x)$or $$$(x, 1)$for anyone $$$x$will be the next sequence on $$$x$m step. And since actions are restored unequivocally,
this means that the original pair $$$(p, q)$at some point will meet as the next.

Thus, each ordered pair of mutually simple numbers occurs exactly once as neighbors in a given sequence. Therefore, the problem is reduced to counting the number of ordered pairs of mutually simple numbers, giving a total of $$$n$. So how if $$$p$and $$$n$mutually simple, then $$$p$and $$$n-p$are mutually simple, then the number of such pairs can be put in one-to-one correspondence with the number of numbers that are mutually simple with $$$n$, or the value of the Euler function from $$$n$.

Counting the number of such numbers is a well-known problem and is based on the multiplicativity of the Euler function: if $$$n = p_1 ^ {k_1} \ cdot p_2 ^ {k_2} \ cdot \ ldots \ cdot p_n ^ {k_n}$then mutually simple with $$$n$
numbers will be $$$(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 })$. Unfolding $$$n$on prime factors over time $$$O (\ sqrt {n})$.

E. Backup

Time limit 5 seconds
Memory Limit 512Mb

To ensure the safety of user data, Arkady constantly invents and tests new backup schemes. This time, he numbered all his computers with data from 1 to $$$n$and for each computer number from 1 to $$$n − 1$assigned a backup computer $$$p_i$. At the same time, he strictly observed the rule that the number of the backup computer is always greater than the number of the computer itself, that is, $$$p_i> i$. For this reason, the computer with the number $$$n$There is no computer for backup.

In the course of the current experiment, Arkady chose a certain configuration of values $$$p_i$and will sequentially shut down the computers one by one every second. The experiment ends when Arkady turns off the computer with the number $$$n$. Initially, on each computer there is a block of data of size 1. When you turn off the computer with the number $$$x$, initially located on it a data block of size 1 is transferred to a computer with a number $$$p_x$while the number on the computer $$$x$if there were other data blocks (received from other computers when they were turned off), they disappear. If the computer $$$p_x$already disabled, then the data block from the computer $$$x$nowhere is transmitted and disappears too.

Arkady wants the experiment to go on as long as possible, but he has to observe one additional additional constraint: if he is going to $$$k$data blocks, in order to preserve the iron this computer must be immediately turned off in the next second. Note that the last second (during which the computer turns off $$$n$) is not counted.

Input format
The first line of the input contains an integer $$$t$( $$$1 \ le t \ le20$) - the number of test examples.

Followed by $$$t$test case descriptions, each description begins with a string containing two integers $$$n$and $$$k$( $$$1 \ le n \ le $ 100,00$, $$$2 \ le k \ le 10$) - the number of computers participating in the experiment and the maximum number of data blocks on one computer, respectively. The second line contains $$$n − 1$number $$$p_1, p_2, \ ldots, p_ {n − 1}$( $$$i + 1 \ le p_i \ le n$).

Output format
For each of $$$t$test examples output a single integer - the maximum possible duration of the experiment, that is, the maximum number of a second at which Arkady can turn off the computer with the number $$$n$.

Decision:
In the problem, we are given a root tree, at every step one of the tree's vertices is deleted. Moreover, if the root of the vertex has not yet been removed, then its value is increased by 1 (initially, all values ​​are equal to 1). If the value of some vertex becomes equal $$$k$it is she who is removed in the next step. It is required to maximize the step number at which the root vertex will be deleted.

Note that if the root vertex is less than $$$k - 1$then you can delete all the vertices of the tree before touching the vertex number $$$n$. Otherwise, all children of the root are divided into three sets: those whose subtrees will be completely removed, those whose root will remain untouched, and one subtree, after removing the root of which we remove the vertex itself. $$$n$. Make a detour to the depth of our tree and we will support three values ​​of dynamic programming:

$$$a (v)$equals the number of vertices that can be deleted in a given subtree if you can delete a vertex $$$v$and not necessarily the last. It is easy to see that $$$a (v)$equals the size of the subtree.

$$$b (v)$equals the number of vertices that can be deleted in a given subtree if the vertex is $$$v$should remain untouched. Equals $$$a (v) - 1$if u vertex $$$v$less $$$k - 1$son Otherwise, you need to choose some $$$k - 2$child for which the value will be used $$$a (u)$and for all others use $$$b (u)$. As such $$$k - 2$descendants profitable to take the top with the maximum difference $$$a (u) - b (u)$.

$$$c (v)$equals the number of vertices that can be deleted in a given subtree if you can delete a vertex $$$v$but it must be the last remote vertex of the subtree. Magnitude $$$c (n)$and will be the answer to the problem. Required to choose some $$$k - 2$child for which the value will be used $$$a (u)$one descendant for which we use $$$c (u)$and for all others the answer will be added $$$b (u)$. We will sort through which of the descendants will be used $$$c (u)$(that is, who will be the last remote descendant, after which the vertex will also be deleted $$$v$). Now among the rest you want to take the sum of all the value $$$b (u)$and $$$k - 2$maximum $$$a (u) - b (u)$. To do this, it is sufficient to have the sum of all $$$b (u)$and the list of sons ordered by $$$a (u) - b (u)$. If vertex $$$x$, for which we decided to take value $$$c (x)$gets to the vertices with the maximum difference, then use the following $$$k - 1$a vertex (there is such a thing, otherwise we just destroy the entire subtree).

The total complexity of the solution $$$O (n \ log n)$.

F. Processor liars

Time limit 3 seconds
Memory Limit 512Mb

For testing new machine learning algorithms, Evgeny uses $$$n \ cdot m$processors located in single size board cells $$$n \ times m$. Thus, processors occupy $$$n$rows by $$$m$processors in each. In this case, two processors are considered to be adjacent if they are located in adjacent cells of one row, or at the same position in adjacent rows.

As a result of an unsuccessful experiment with a new algorithm, some of the processors learned to lie to Eugene. However, due to the fact that only the basic version of the algorithm was used, if a processor starts to lie, then it will always do so, so its results are still not difficult to interpret.

Now Eugene is faced with the task of determining which of the processors constantly give out incorrect information, but first he wants to assess the scale of the problem. To this end, he sent each of the processors a question: is it true that among his neighboring processors there are both serviceable processors and liar processors? To the surprise of Eugene, all processors answered in the affirmative to such a request. Now he wants to know what the minimum number of liar processors can be on the board?

Input format
$$$n$and $$$m$( $$$1 \le n \le 7$, $$$1 \le m \le 100$) — .

— - , , -.

Decision:
, $$$n \le 7$. $$$i$, $$$i - 1$. , , .

$$$dp(i, m_1, m_2)$where $$$i$1 $$$m$, but $$$m_1$and $$$m_2$— 0 $$$2^n - 1$. -, , $$$i$, $$$i - 1$, $$$m_1$and $$$m_2$. $$$O(m \cdot 2^{2n})$. , $$$m_3$$$$dp(i + 1, m_2, m_3)$.

$$$O(m \cdot 2^{3n})$. , $$$(m_1, m_2)$( $$$m_3$).

: , $$$O(nm 2^{2n})$.