# Elimination round 2017 - short editorial

## A. Small Numbers

First of all, find prime factorization of numbers *a* and *b*.

After that you need to notice that if *ab* is divisible by *p*^{2}, (where *p* is a prime number), it is either possible to divide both *a* and *b* by *p* instantly, or you will need to perform one of the latter two operations first to move one of *p* factors to the other number, and then divide both by *p*.

Obviously, parity of occurrence of prime numbers in the multiple *ab* remains unchanged in all operations. Therefore we can either remove *p* factor completely from *ab* or leave it occurring only once. After removing all primes, lets say the ones left are *p*_{1}, *p*_{2}, ..., *p*_{n}. Let us call multiple of all these numbers *d*. Important observation is that *n* can't exceed 14 because multiple of first 15 prime numbers is more than 10^{18}, which means it can't be a product of two numbers *a*, *b* ≤ 10^{9}. Now we simply need to iterate over all possible pairs and chose one with minimum sum that we can obtain from *d*. This can be done in *O*(2^{n}) which fits the time limit.

## B. New Keyboard

Let us use dynamic programming. The state is d[i][j][k], where *i* — is the flag that denotes the previous action (0 for layout switch, and 1 for typing character), *j* is the number of the current layout, and *k* is the number of characters typed so far. The value is the minimal time to reach the state.

Now iterate over *k*. For a given *k* first iterate *j* from 1 to *n* twice. Both times relax d[0][j % n + 1][k] = min(d[0][j % n + 1][k], min(d[0][j][k] + b, d[1][j][k] + a)). Two iterations of *j* from 1 to *n* are needed to ensure that if the layout switches from *n* to 1 it is processed correctly.

Now iterate *j* from 1 to *n* again and relax values for *k* + 1. If there is the *k*-th character of the message in the *j*-th layout, update d[1][j][k + 1] = min(d[0][j][k], d[1][j][k]) + c.

The answer is min(d[1][j][m]), where *m* = *length*(*s*), for all *j* from 1 to *n*.

## C. Folding the Figure

Note that there are exactly 4 possible folding lines: two horizontal and two vertical, because the figure must be at one side of the folding line, and must touch it.

Take any square of the folded figure with the minimal *x*-coordinate. Let it be the cell (*x*_{i}, *y*_{i}). Take line *x* = *x*_{i} as the folding line. Now we need to find *k* - *n* squares of the original figure on the other side of the folding line. So let us find *k* - *n* connected squares of the folded figure containing the square (*x*_{i}, *y*_{i}), for example, using DFS.

## D. Acute Triangles

To count the number of acute triangles let us count the total number of triangles and subtract the number of right and obtuse triangles. For the purpose of this problem let us consider three points on a line to be a degenerate obtuse triangle.

The total number of triangles is equal to the number of ways to choose 3 points of *n*.

Now note the fact: each right or obtuse triangle has exactly one right or obtuse angle. So the number of bad triangles is equal to the number of bad angles.

Now let us count the number of angles not less than 90 degrees with vertices in the given points. Consider the angle vertex and sort other points by their polar angle relative to the chosen point. Now use two pointers: consider the first of the other two points, the matching third points form a continuous segment along the circle, and its ends move in the same direction.

Time complexity is *O*(*n*^{2}*log*(*n*)).

## E. Joining Arrays

Let us consider two solutions for the problem, that take *O*(*k*^{2}·*log*(*k*)) and *O*(*k*^{2}) respectively. The first one brings up core ideas, while the second one being more elusive has simpler implementation.

*O*(*k*^{2}·*log*(*k*)) solution:

Consider three main steps of the solution

- For each array
*X*(*A*or*B*) and each length 1 ≤*length*≤ |*X*| find*minSubsequence*_{X}[*length*] — lexicographically smallest subsequence of*X*that has the given length; - Iterate over
*t*such that 1 ≤*t*≤*min*(*k*- 1, |*A*|) and 1 ≤*k*-*t*≤ |*B*|, take*minSubsequence*_{A}[*t*] and*minSubsequence*_{B}[*k*-*t*], join them; - Joining the given sequences, get the optimal sequence of length
*k*, update the answer with that sequence.

1) To find *minSubsequence*_{X}[*length*] for each *length*, let us do the following:

- Calculate
*next*[*i*][*c*] that will store the next occurence of value*c*after*i*in*X*; - Calculate
*firstSymbol*[*length*][*i*] — the first character of lexicographically smallest subsequence of*X*[*i*..|*X*| - 1] that has given*length*. To calculate it note the following:- If
*j*_{1}=*next*[*i*][1], and it exists, then*firstSymbol*[1][*i*],*firstSymbol*[2][*i*], ...*firstSymbol*[|*X*| -*j*_{1}][*i*] are equal to 1; - If, if
*j*_{2}=*next*[*i*][2], and it exists, then*firstSymbol*[|*X*| -*j*_{1}+ 1][*i*], ...,*firstSymbol*[|*X*| -*j*_{2}][*i*] are equal to 2; - ...
- If
*j*_{3000}=*next*[*i*][3000], and it exists, then*firstSymbol*[*max*(|*X*| -*j*_{1}, |*X*| -*j*_{2}, ..., |*X*| -*j*_{3000 - 1}) + 1][*i*], ...,*firstSymbol*[|*X*| -*j*_{|alphabet|}][*i*] are equal to 3000.

- If
- After that we can use
*firstSymbol*[*length*][*i*] to restore lexicographically smallest subsequence of each array, one by one.

This step takes *O*(|*X*|^{2}).

3) Given two lexicographically minimal subsequences *S*_{A} and *S*_{B}, now we need to join them to lexicographically smallest sequence. Let us use two pointers *p*_{1} and *p*_{2}. If *S*_{Ap1} ≠ *S*_{Bp2}, we move the smaller pointer, appending the value it points at to the answer. If *S*_{Ap1} = *S*_{Bp2}, use binary search to find the longest common prefix of *S*_{A}[*p*_{1}..|*S*_{A}|] and *S*_{B}[*p*_{2}..|*S*_{B}|], and compare the following elements. Use hashes to compare subarrays of *S*_{A} and *S*_{B}.

This step takes *O*((|*S*_{A}| + |*S*_{B}|)·*log*(*max*(|*S*_{A}|, |*S*_{B}|))) = *O*(*k*·*log*(*k*)).

So the total time complexity is *O*(|*A*|^{2} + |*B*|^{2} + *k*^{2}·*log*(*k*)) = *O*(*k*^{2}·*log*(*k*)).

*O*(*k*^{2}) solution:

Let us index arrays, let array *A* have number 0, and array *B* have number 1. Let us build the answer one element after another, and maintain the values *dp*[*i*][*j*], where *i* is the number of the array (0 or 1), *j* is the index in this array, *dp*[*i*][*j*] is the minimal index in array 1 - *i*, that can be appended to the answer, if we are at index *j* in array *i*.

At the *t*-th of the *k* iterations we find the minimum element that can be appended to the answer, and still the answer can be completed by adding another *k* - *t* - 1 elements. Also we must note that both subsequences from the two arrays must be non-empty.

After adding the element *v*, update the *dp* values in *O*(|*A*| + |*B*|). To do it, use *next* array, the same as in previous solution.

## F. Two Trees

There is a requirement that *k*-subtree must have a vertex at depth *k*. Let us temporarily remove this limitation.

Consider all *k*-subtrees for some value of *k*. They can be divided to equivalence classes. Let each vertex *v* have *c*_{k}[*v*] — the label of its equivalence class that its *k*-subtree belongs to.

If *k* = 0 all *c*_{0}[*v*] are the same, because 0-subtree of any vertex is this vertex by itself.

If *k* = 1 then *c*_{1}[*v*] is the number of children of *v* .

Now let us see how we can convert arrays *c*_{k}[*v*] and *c*_{m}[*v*] to an array *c*_{k + m}[*v*]. First let us assign the array *arr*_{k + m}[*v*] to each vertex *v*, that will uniquely identify its *k*-subtree. Let *u*_{1}, ..., *u*_{s} be its descendants of level *k* in DFS order. Then *arr*_{k + m}[*v*] = *c*_{k}[*v*], *c*_{m}[*u*_{1}], ..., *c*_{m}[*u*_{s}]. So its (*k* + *m*)-subtree is identified by its *k*-subtree and *m*-subtrees from the bottom vertices of its *k*-subtree. See the picture below for *k* = 3 and *m* = 1.

To get the list of descendants at level *k*, let us run one DFS from the root, when entering the vertex, put it to its *k* levels ancestor list.

To transform *arr*_{k + m}[*v*] to integers *c*_{k + m}[*v*] we can either use hashing, or trie, or unordered_map. Each vertex is considered only once in each of these arrays, so the total time is *O*(*n*).

Given array *c*_{k}[*v*] it is easy to check whether there are two equal *k*-subtrees. To do it you must find two vertices with the same *c*_{k}, considering only vertices that have descendants of level *k* (now we need to bring back this requirement).

To find the maximal such *k*, let us first count *c*_{1}[*v*], *c*_{2}[*v*], ..., *c*_{2t}[*v*] (2^{t} is the maximal power of 2 not exceeding *n*). After that make some kind of binary ascending by *k*: start with *k* = 0, and try to add 2^{t}, 2^{t - 1}, ..., 2^{0}, one by one.

Time complexity: *O*(*nlog*(*n*)).

## More news

- Solution of the final round of RCC 2017 The final round of RCC 2017 is over! We congratulate the winners! Here you can find solutions for the final tasks. 11.09.2017
- Russian Code Cup — Eliminataion Round, Some News 11.05.2017