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², (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₁, p₂, ..., 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¹⁸, which means it can't be a product of two numbers a, b ≤ 10⁹. 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ⁿ) 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²log(n)).

E. Joining Arrays

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

O(k²·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 minSubsequence_X[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 minSubsequence_A[t] and minSubsequence_B[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 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₁ = next[i][1], and it exists, then firstSymbol[1][i], firstSymbol[2][i], ... firstSymbol[|X| - j₁][i] are equal to 1;
  • If, if j₂ = next[i][2], and it exists, then firstSymbol[|X| - j₁ + 1][i], ..., firstSymbol[|X| - j₂][i] are equal to 2;
  • ...
  • If j₃₀₀₀ = next[i][3000], and it exists, then firstSymbol[max(|X| - j₁, |X| - j₂, ..., |X| - j_3000 - 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|²).

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₁ and p₂. 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₁..|S_A|] and S_B[p₂..|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|² + |B|² + k²·log(k)) = O(k²·log(k)).

O(k²) 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₀[v] are the same, because 0-subtree of any vertex is this vertex by itself.

If k = 1 then c₁[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₁, ..., u_s be its descendants of level k in DFS order. Then arr_k + m[v] = c_k[v], c_m[u₁], ..., 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₁[v], c₂[v], ..., c_2^t[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⁰, one by one.

Time complexity: O(nlog(n)).