Russian Code Cup 2017 Elimination Round — Editorial

Revision en2, by RussianCodeCup, 2017-05-14 15:07:17

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 p2, (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 p1, p2, ..., pn. 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 1018, which means it can't be a product of two numbers a, b ≤ 109. 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(2n) 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 (xi, yi). Take line x = xi 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 (xi, yi), 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(n2log(n)).

E. Joining Arrays

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

O(k2·log(k)) solution:

Consider three main steps of the solution

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

1) To find minSubsequenceX[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 j1 = next[i][1], and it exists, then firstSymbol[1][i], firstSymbol[2][i], ... firstSymbol[|X| - j1][i] are equal to 1;
    • If, if j2 = next[i][2], and it exists, then firstSymbol[|X| - j1 + 1][i], ..., firstSymbol[|X| - j2][i] are equal to 2;
    • ...
    • If j3000 = next[i][3000], and it exists, then firstSymbol[max(|X| - j1, |X| - j2, ..., |X| - j3000 - 1) + 1][i], ..., firstSymbol[|X| - j|alphabet|][i] are equal to 3000.
  • 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 SA and SB, now we need to join them to lexicographically smallest sequence. Let us use two pointers p1 and p2. If SAp1 ≠ SBp2, we move the smaller pointer, appending the value it points at to the answer. If SAp1 = SBp2, use binary search to find the longest common prefix of SA[p1..|SA|] and SB[p2..|SB|], and compare the following elements. Use hashes to compare subarrays of SA and SB.

This step takes O((|SA| + |SB|)·log(max(|SA|, |SB|))) = O(k·log(k)).

So the total time complexity is O(|A|2 + |B|2 + k2·log(k)) = O(k2·log(k)).

O(k2) 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 ck[v] — the label of its equivalence class that its k-subtree belongs to.

If k = 0 all c0[v] are the same, because 0-subtree of any vertex is this vertex by itself.

If k = 1 then c1[v] is the number of children of v .

Now let us see how we can convert arrays ck[v] and cm[v] to an array ck + m[v]. First let us assign the array arrk + m[v] to each vertex v, that will uniquely identify its k-subtree. Let u1, ..., us be its descendants of level k in DFS order. Then arrk + m[v] = ck[v], cm[u1], ..., cm[us]. 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 arrk + m[v] to integers ck + 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 ck[v] it is easy to check whether there are two equal k-subtrees. To do it you must find two vertices with the same ck, 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 c1[v], c2[v], ..., c2t[v] (2t 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 2t, 2t - 1, ..., 20, one by one.

Time complexity: O(nlog(n)).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English RussianCodeCup 2017-05-14 15:07:17 0 (published)
en1 English RussianCodeCup 2017-05-14 15:06:56 12872 Initial revision for English translation
ru1 Russian RussianCodeCup 2017-05-14 15:06:37 14228 Первая редакция (сохранено в черновиках)