628A - Tennis Tournament

The problem was suggested by unprost.

Here you can simply model the process. Or you can note that after each match some player drops out. In total n - 1 players will drop out. So the first answer is (n - 1) * (2b + 1). Obviously the second answer is np.

С++ solution 1

С++ solution 2

Complexity: O(log²n), O(logn) or O(1) depends on the realization.

628B - New Skateboard

This is one of the problems suggested by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.

The key observation is that the number is divisible by 4 if and only if its last two digits forms a number divisible by 4. So to calculate the answer at first we should count the substrings of length one. Now let's consider pairs of consecutive digits. If they forms a two digit number that is divisible by 4 we should increase the answer by the index of the right one.

C++ solution

Complexity: O(n).

628C - Bear and String Distance

The problem was suggested and prepared by Kamil Debowski Errichto.

Complexity: O(n).

628D - Magic Numbers

Kareem Mohamed Kareem_Mohamed suggested the simpler version of the problem.

Denote the answer to the problem f(a, b). Note that f(a, b) = f(0, b) - f(0, a - 1) or what is the same f(a, b) = f(0, b) - f(0, a) + g(a), where g(a) equals to one if a is a magic number, otherwise g(a) equals to zero. Let's solve the problem for the segment [0, n].

Here is described the standard technique for this kind of problems, sometimes it is called 'dynamic programming by digits'. It can be realized in a two ways. The first way is to iterate over the length of the common prefix with number n. Next digit should be less than corresponding digit in n and other digits can be arbitrary. Below is the description of the second approach.

Let z_ijk be the number of magic prefixes of length i with remainder j modulo m. If k = 0 than the prefix should be less than the corresponding prefix in n and if k = 1 than the prefix should be equal to the prefix of n (it can not be greater). Let's do 'forward dynamic programming'. Let's iterate over digit in position i. We should check that if the position is even than p should be equal to d, otherwise it cannot be equal to d. Also we should check for k = 1 p should be not greater than corresponding digit in n. Now let's see what will be the next state. Of course i' = i + 1. By Horner scheme j' = (10j + p) mod m. Easy to see that . To update the next state we should increase it: z_i'j'k' +  = z_ijk. Of course all calculations should be done modulo 10⁹ + 7.

C++ solution

Complexity: O(nm).

628E - Zbazi in Zeydabad

The problem was suggested by Ali Ahmadi Kuzey.

Let's precalculate the values zl_ij, zr_ij, zld_ij — the maximal number of letters 'z' to the left, to the right and to the left-down from the position (i, j). It's easy to do in O(nm) time. Let's fix some cell (i, j). Consider the value c = min(zl_ij, zld_ij). It's the maximum size of the square with upper right ceil in (i, j). But the number of z-patterns can be less than c. Consider some cell (x, y) diagonally down-left from (i, j) on the distance no more than c. The cells (i, j) and (x, y) forms z-pattern if y + zr_xy > j.

Let's maintain some data structure for each antidiagonal (it can be described by formula x + y) that can increment in a point and take the sum on a segment (Fenwick tree will be the best choice for that). Let's iterate over columns j from the right to the left and process the events: we have some cell (x, y) for which y + zr_xy - 1 = j. In that case we should increment the position y in the tree number x + y by one. Now we should iterate over the cells (x, y) in the current column and add to the answer the value of the sum on the segment from j - c + 1 to j in the tree number i + j .

С++ solution

Complexity: O(nmlogm).

628F - Bear and Fair Set

The problem was suggested and prepared by Kamil Debowski Errichto.

С++ solution

Complexity: O(2^Cn). In our problem C = 5.