Hello, friends!

Winter 188th Codeforces Round is coming!

We wished to prepare for you some enjoyable problems (as we believe, not very difficult) with nice ideas and clear statements.

"We" includes authors of the problems yaro and Rei, Codeforces Rounds supervisor Gerald and the platform founder MikeMirzayanov. Special thanks to Pasha (PavelKunyavskiy) and Artem (RAD) for the testing and helpful comments.

Last time I was preparing a competition here on Codeforces, Rounds were still "beta". Well, with less "beta" comes greater responsibility. So I wish the authors and the organizers a successfully held Round. As for the participants, I wish you the unconventional ideas, the clean code (and a clean keyboard, of course), and satisfaction from five (well, possibly the less number will also do...) correct and accepted solutions!

It seems to us that it is not an easy job to arrange the problems by their difficulty, so we have chosen the dynamic scores. Still (out of curiousity) let us put a bet on the following relative difficulties for the problems: div.1 — B-B-C-C-E, div.2 — A-B-C-C-E. How close is our guess?

UPD Sorry for the problems with the Codeforces testing queue during the round.

We will still be happy if you rate our contest (when it will be over): short survey.

And with the gap of one hack the winner of div.1 is meret (Jakub Pachocki)!

Div.1 standings, Div.2 standings.

Analysis (thanks to Rei for the translation).

A. Mirror-number.
First note that if the interval contains a number with a digits and a number with b digits (where a > b) then there is no need to consider the number with b digits (as the weight of 10^k is greater then the weights of the numbers less than 10^k).
If we consider only numbers with fixed number of digits (s + 1), then the sum of a and its reflection is constant. Thus, as product grows as multipliers with fixed sum get closer, the picture is the following: the weight grows from 10^s to 5· 10^s - 1, then it stays the same for 5· 10^s and then it goes down, and reaches its minimum (zero) value at 10^s + 1 - 1.
This is the proof, and the solution is: the maximum weight is reached at either l, r or 5· 10^s (we may check all the s such that 5· 10^s belongs to the interval, for example). 

B. Tetris revisited

It's easy to see that the field may be filled with such figures if and only if there is no isolated cell.

There are many different ways to do that, we will show some of them.

1. Domino filling.

We construct greedy matching on the cells of our field combining them in domino-like figures (rectangles 1  ×  2).

Passing through the array that represents our field (from left to right, from top to bottom) we combine the still free horizontal pairs of connected cells into the horizontal dominoes. Then we do the same thing with the still free vertical pairs. Naturally, some cells may be still free. But such cells should be adjoined with some of the dominoes (if they were not isolated). We may attach each of these cells to any of the adjoint dominoes. All resulting figures will contain no more than 5 cells, because the cells still empty after matching can not be neighbour cells and can not be adjacent to the left side of dominoes (by the virtue of the order of our matching).

The last thing that has to be done is the coloring of the figures in accordance with the output format. For example, we may color them like that: color all the cells in the plane in 9 colors  (i, j) -> (i % 3) * 3 + j % 3. Then paint each domino in the color of its black cell (according to chess coloring). Each figure will have the color of the domino it grows from.

2. Greedy.

We pass through the array representing the field, again in the same order. Figure for any still free cell may be constructed greedily, but we have to be accurate in order to avoid appearance of new isolated cells. So we just add all the cells that do become isolated when we fill the current figure. Acting in such a fashion we will eventually get the covering by the figures of no more than 5 cells (and at least two, of course).

It is possible to color the figure immediately after its formation. We only need to check the colors of all already colored adjacent figures and to take any color, different from all of them. It is not hard to see that 10 colors are enough.

C. Genetic engineering.

Suppose we've built a string wp of length k < n and want to know how many ways there exist to complement wp to the suitable string of length n.
What parameters do we need to know in order to build it further?
First of all, we need to know the index wp is covered up to (we denote it by ci and call it covering index). Also we want to have some information about what the string ends with.
Here comes rather standard idea: let's find all the prefixes ALL_P of the {s_i} and add to our state the largest prefix such that wp ends with p_k (as an alternative, you may consider a vertex in a trie constructed with the collection's strings).
Now I'll try to convince you that it's enough to set the things going. First of all, when we add a symbol c to wp we can easily get p_k + 1 and it will be equal to the largest string in ALL_P such that the string p_k + c ends with (we can precalculate all the transitions in advance). So the only thing we want to know how to calculate (in order to use dynamic programming approach) is the new covering index. But we notice that it can be changed only by some string from the collection that w_p + c ends with. Now we observe that it is sufficient to check only the largest from all such strings (denote it fs), and that it necessarily contains in p_k + 1 (so it also can we easily precalculated for all strings in ALL_P). We observe further that the new covering index depends only on the length of fs: it either equals the old one if fs doesn't cover the symbol ci + 1, or equals to (k + 1) if the fs covers that symbol.

After calculating all the quantities d[k][k - cov.index][max. prefix] the required number of strings equals the sum of d[n][0][mp] for all mp.

D. Powerful array.
Let's solve the problem offline in O(n sqrt(t)) time and O(n) memory. For the simplicity of the reasoning let t = n.

Assume we know the answer to the problem for some interval and want to find it to another one. Let us move the left end of the first one towards the left end of the second, similarly dealing with the right ends. By moving the end by one and for every value in the array maintaining the number of its appearances in the current interval, we will be able to calculate the answer and maintain the numbers of appearances at the same time in O(1). From now on we call the procedure of movement by 1 a step.

Going through the queries in such a fashion, evidently, will cost us O(n^2) steps.
Let p = sqrt(n). Divide the array into p equal parts Q_1, ..., Q_p. Now consider the queries of the form (Q_i, Q_j) for all i and j (there will be approx. n such queries). Clearly, there doesn't exist an order in which we can go through the queries in o(n sqrt(n)) time as the transition from any interval to the other one is done in no less than sqrt(n) steps.

Nevertheless, there exists a traversal order that guarantees O(n sqrt(n)) steps in the worst case.
Let's sort the query intervals according to the following rule: first come the intervals with the left ends in Q_1, then the intervals with the left ends in Q_2, and so on. And if the left ends of the two queries belong to the same part, then the interval with the more left right end is assumed to be smaller.

In order to prove the stated asymptotic behavior we will follow the steps of the left and the right ends independently. We note that the left ends that belong to the same Q_i make <= n / p steps, and transition to Q_{i+1} costs no more than 2 * n / p steps. Therefore the left ends make <= n/p * n + 2*n steps (the second summand is O(n), and it's negligible).
The right ends in the common group move only to the right, and this proves <= n * p steps (during the whole process) estimate. We will estimate the transition to the next Q_i at no more than n steps, so overall we get <= 2 * n * p steps.
Thus, the total number of steps is no more than (n / p * n + 2 * n * p). Now we choose p = sqrt(n) which proves the statement.

Solution: let us sort the queries by this rule, then make transitions from a query to the next one according to the obtained order.

Note 1. There is nothing special (except for nonadditivity) with the function in the statement.

Note 2. In the case of distinct n and t we can similarly prove the nice estimate 2 * n * sqrt(t), mostly nice because of its exactness (if you follow the proof carefully, you will easily construct the maximal test).

E. Long sequence.
Firstly let's note that there are only 49 different possible inputs.
So any solution that works finite time at all tests (even if does not pass timelimit) is enough, because we can memorize all the answers. It is not necessary, of course, but may help with slow solutions.

Then, let's answer a more particular question. Assume that c₁, c₂, ..., c_k and a₀, a₁, ..., a_k - 1 are already given and we need to check whether the sequence {a_i} generated by them is long or not. We know that if it is periodic, then it is possible to find any non-zero k-tuple among k-tuples a_s, a_s + 1, ..., a_{s + k - 1}. So initial k-tuple has no real matter if only it is not zero. Thus the property of sequence "to be long" depends only on coefficients c_i, and we may choose any convenient a₀, a₁, ..., a_k - 1. We will now think that a₀, a₁, ..., a_k - 2 are zeros and a_k - 1 = 1.

Consider the transition matrix A of our sequence: for i < k the i-th row of A is equal to (0, 0, ... 0, 1, 0, ..., 0) with 1 at (i + 1)-th position and last row of A is equal to (c_k, c_k - 1, ..., c₂, c₁).

Denote by x_s vector (a_s, a_s + 1, ..., a_{s + k - 1})^T.
Then for any integer s we have: A· x_s = x_s + 1.
Last is just a reformulation of the recurrent formula:

Hello, dear participants and spectators!

Let me remind you that the elimination phase of the open programming competition "Yandex.Algorithm" comes to an end. With it this means that the time for the most important event of the phase has come: the elimination round for the finals (finals will be held at the Yandex Summer School)! This means that today two hundred best participants of the tournament (based on the results of the previous qualification rounds) will compete to get into the top-15 of the world olympiad programming community.

We hope that the round will be appreciated not only by the participants but also by the spectators, who will have the opportinity to watch the events developing for at least two hours.

Please, pay attention to the problems' costs: 500, 1000, 2000, 2500, 2500. I also advise you to read all the statements, as the choice of the costs and the order is certainly subjective.

Round will be rated for all the participants (including those competing hors concours).
Good luck to the participants. The problems are going to be rather hard, so you'll have to do your best!

I also wish a spectacular round to the rest!

Round is over. According to the results, 20 participants solved at least three problems, and just one (the winner) was able to solve the fourth. The first three places were taken by Petr Mitrichev, Gennady Korotkevich and Sergey Kopeliovich. Congratulations!

In addition to this, 15 leaders advanced to the finals: Petr, tourist, Burunduk1, ivan.metelsky, dzhulgakov, e-maxx, LayCurse, rng_58, pieguy, zeliboba, ktuan, levlam, wata, dolphinigle, Progger .

Problems proved to be rather tough. Here's the full analysis.

In this problem one should answer the query: how many beautiful numbers are there in the interval from 1 to R.

Clearly, to check whether a number is divisible by all its digits, it is sufficient to know the remainder of a division by the lcm of all possible digits (call this lcm M), that is M = 8 * 9 * 5 * 7 = 2520. The standart dynamic solution is supposed to maintain such state parameters: the length of the number, "strictly less" flag, current remainder of a division by M and the mask of already taken digits.

The first note: we can maitnain the lcm of the digits already taken, not the mask. This will decrease the number of different values of the last parameter (from 256 to 4 * 3 * 2 * 2 = 48, where 4 is the number of different powers of 2 etc).

Then, it is a good idea to pre-count transitions to the new parameters. But we wanted and tried to set such a time limit restriction, so that this solution would not be enough to avoid TL.

The idea that will decrease the running time even more lies in number theory. If we add digits from the end of a number we may see that the remainder of a number after division by 5 depends only on the last digit. Therefore, we may maintain the flag "last digit = 5 or 0" and ban transitions to the digit 5 if the flag is set to "false". Such an idea reduces the number of states by 5 * 2 / 2 = 5. This solution is fast enough to pass in any language, though there are even more powerful optimizations (the trick mentioned above can be done with digit 2 also).