632A - Grandma Laura and Apples

The problem was suggested by unprost.

Consider the process from the end. The last buyer will always buy a half of an apple and get a half for free (so the last string always is halfplus). After that each buyer increases the number of apples twice and also maybe by one. So we simply have the binary presentation of the number of apples from the end. To calculate the answer we should simply restore that value from the end and also calculate the total money grandma should have.

С++ solution by me.

С++ solution by unprost.

Complexity: O(p).

632B - Alice, Bob, Two Teams

The problem was suggested by Lewin Gan Lewin.

Let's calculate the prefix sums for all numbers (and store it in array s1) and for numbers with letter B (and store it in array s2). Now we can find the sum of all numbers in any segment in O(1) time and the sum of numbers with letter B.

Let's iterate over prefix or suffix to flip and calculate the sum in that case by formulas: sum(s1, 0, n - 1) + sum(s2, 0, i) - 2·sum(s1, 0, i) for prefixes and sum(s1, 0, n - 1) + sum(s2, i, n - 1) - 2·sum(s1, i, n - 1) for suffixes.

C++ solution by me.

Python solution by Lewin.

Complexity: O(n).

632C - The Smallest String Concatenation

The problem was suggested by Lewin Gan Lewin. The proof of the transitivity also belongs to him.

Let's sort all the strings by comparator a + b < b + a and concatenate them. Let's prove that it's the optimal answer. Let that operator be transitive (so if ). Consider an optimal answer with two strings in reverse order by that operator. Because of the transitivity of operator we can assume that pair of strings are neighbouring. But then we can swap them and get the better answer.

Let's prove the transitivity of operator. Consider the strings as the 26-base numbers. Then the relation a + b < b + a equivalent to . The last is simply the relation between real numbers. So we proved the transitivity of the relation a + b < b + a.

C++ solution by me.

Python solution by Lewin.

Complexity: O(nLlogn), where L is the maximal string length.

632D - Longest Subsequence

The problem was suggested by Denis Bezrukov pitfall.

Let cnt_x be the number of occurences of the number x in the given array (easy to see that we can ignore the numbers greater than m). Let's iterate over and 1 ≤ k, x·k ≤ m and increase the value in the position k·x in some array z by the value cnt_x. So the value z_l equals the number of numbers in the given array which divide l. Let's find the minimal l with the maximum value z_l (1 ≤ l ≤ m). Easy to see that the answer to the problem is the numbers which divide l.

Let's calculate the complexity of the solution. The number of the pairs (k, x) we can bound with the value .

C++ solution by me.

Java solution by pitfall.

Complexity: O(n + mlogm).

632E - Thief in a Shop

The problem was suggested by Alexey Chesnokov CleRIC.

Let k = 2, then it is the standard problem which can be solved by FFT (Fast Fourier Transform). The solution is the following: consider the polynomial which the i-th coefficient equals to one if and only if there is the number i in the given array. Let's multiply that polynomial by itself and find i for which the coefficient in square not equals to 0. Those values i will be in the answer. Easy to modificate the solution for the arbitrary k. We should simply calculate the k-th degree of the polynomial. The complexity will be WlogWlogk, where W is the maximal sum.

We can improve that solution. Instead of calculating the k-th degree of the polynomial we can calculate the k-th degree of the DFT of the polynomial. The only problem is the large values of the k-th degrees. We can't use FFT with complex numbers, because of the precision problems. But we can do that with NTT (Number-theoretic transform). But that solution also has a problem. It can happen that some coefficients became equals to zero modulo p, but actually they are not equal to zero. To get round that problem we can choose two-three random modules and get the complexity O(W(logW + logk)).

The main author solution has the complexity O(WlogWlogk) (FFT with complex numbers), the second solution has the same complexity, but uses NTT and the third solution has the improved complexity (but it was already hacked by halyavin).

С++ solution, complex FFT by me.

С++ solution, NTT by me.

С++ solution, improved NTT by me.

С++ solution by CleRIC.

P.S.: To get faster solution you should each time multiply the polynomials of the required degree, but not of the degree 2²⁰.

Complexity: O(WlogWlogk) or O(W(logW + logk)), depending the bravery of the coder :-)

UPD: It turns out that the first approach also has complexity O(W(logW + logk)). See below the comment of halyavin.

632F - Magic Matrix

The problem was suggested by Lewin Gan Lewin. The solution and proof also belongs to him.

Consider the undirected complete graph with n nodes, with an edge between nodes i, j with cost a_ij. Let B_ij denote the minimum possible value of the max edge of a path from i to j. We know that a_ij ≥ B_ij by definition.

If the matrix is magic, we can choose arbitrary k₁, k₂, ..., k_m such that a_ij ≤ max(a_i, k1, a_k1, k2, ..., a_km, j) by repeating invocations of the inequality given. Also, you can show that if this inequality is satisfied, then the matrix is magic (by choosing an m = 1 and k₁ arbitrary).

So, this shows that the matrix is magic if and only if a_ij ≤ B_ij. Thus, combining with a_ij ≥ B_ij, we have a_ij = B_ij.

We need a fast way to compute B_ij for all pairs i, j. This can be computed as the MST, as the path in the MST minimizes the max edge between all pairs of nodes. So, the algorithm works as follows. First, find the MST on the complete graph. Then, the matrix is magic if and only if the max edge on the path between i, j in the MST is exactly equal to a_i, j. Also you shouldn't forget to check symmetry of the matrix and diagonal for zeros.

P.S.: Unfortunately we couldn't increase the value n in this problem: the tests already had the size about 67MB and they couldn't be given with generator. So most of the users who solved this problem uses bitset-s. The complexity of their solution is , where b = 32 or b = 64.

C++ solution, binary lifts by me.

Java solution by Lewin.

Complexity: O(n²logn) or O(n²).