yaro's blog

By yaro, 11 years ago, translation, In English

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).

Full text and comments »

  • Vote: I like it
  • +331
  • Vote: I do not like it

By yaro, 13 years ago, translation, In English

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 10k is greater then the weights of the numbers less than 10k).
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 10s to 5· 10s - 1, then it stays the same for 5· 10s and then it goes down, and reaches its minimum (zero) value at 10s + 1 - 1.
This is the proof, and the solution is: the maximum weight is reached at either l, r or 5· 10s (we may check all the s such that 5· 10s 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 ALLP of the {si} and add to our state the largest prefix such that wp ends with pk (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 pk + 1 and it will be equal to the largest string in ALLP such that the string pk + 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 wp + 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 pk + 1 (so it also can we easily precalculated for all strings in ALLP). 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 c1, c2, ..., ck and a0, a1, ..., ak - 1 are already given and we need to check whether the sequence {ai} 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 as, as + 1, ..., as + 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 ci, and we may choose any convenient a0, a1, ..., ak - 1. We will now think that a0, a1, ..., ak - 2 are zeros and ak - 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 (ck, ck - 1, ..., c2, c1).

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

an = c1 * an - 1 + c2 * an - 2 + ... + ck * an - k.

Then by obvious induction we have: Ap· xs = xs + p for any p ≥ 0. Hence p is a period iff for any vector x that appears in our sequence: Ap· x = x. If the sequence is not long then it is not self-evident still that Ap is an identity matrix, because x does not take all possible values. But we have chosen x0 = (0, 0, ..., 0, 1) before, so it is obvious that vectors x0, x1, x2, ..., xk - 1 form a basis. Hence if Ap· xi = xi for any i then Ap is the identity matrix.

So we just need to do the following:

1) Construct the matrix A from the coefficients ci.

2) Check that A2k - 1 is the identity matrix. (If not, then 2k - 1 is not a period.)
If 2k - 1 is a period, then we have to check that it is minimal. Minimal period divides any period so we only need to check the divisors of 2k - 1.

3) Generate all maximal divisors of 2k - 1 and check that they are not periods (using A again).

(By maximal divisor of n we mean divisors of the type n/q where q is a prime number.)

Last thing we need to notice that such a sequence always exists. Moreover, amount of appropriate sets of ci is pretty large. One may prove that there are such sets (because they correspond to the coefficients of the irreducible factors of the cyclotomic polynomial over ). So we can just take them at random and check.

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

By yaro, 13 years ago, translation, In English

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.

Full text and comments »

  • Vote: I like it
  • +114
  • Vote: I do not like it

By yaro, 13 years ago, translation, In English
Let us solve this problem for every point P independently. We will show how to do this in linear time, that is, O(N). It seems that the most easy way to do this is to count the number of triangles not containing P (call them good), and then subtract this value from the total number of triangles.

Consider triples of vertices A, B, C that form a triangle, such that: P doesn't lie in ABC; AB separates P and C in the polygon; P lies in the polygon to the right from AB (clockwise). Note, that every good triangle provides us one such triple and each triple forms a good triangle. Thus, we may consider such triples instead of good triangles.

Let's consider an arbitrary vertex of the polygon. We want it to become an A-vertex in some triple. Then we can obtain the set of vertices, suitable for B-vertex in a triple moving diagonals from A (clockwise) until we reach P. Then for the fixed A the number of triples is equal to the sum of the number of triples for this A and the fixed B, which is equal to the sum of some linear series (as all suitable C lie between A and B and their number is equal to the vertex-distance between A and B minus one).

The only thing left to do is to find the last B (last until P is reached) for each vertex of the polygon. And this is a simple exercise on the two pointers technique.

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By yaro, 13 years ago, translation, In English

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).

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

By yaro, 13 years ago, translation, In English
Good morning (day, evening, night)!

Today's round problems authors are we — Rei and yaro. We've been thoroughly selecting the problemset, so hope you'll enjoy the final edition.

Thanks to problem coordinator Artem Rakhov for invaluable help in round preparation, and to those, who makes codeforces more comfortable, functional and stable.

Wish you good luck!

UPD. Analysis: A B C D E

Full text and comments »

Announcement of Codeforces Beta Round 51
  • Vote: I like it
  • +74
  • Vote: I do not like it

By yaro, 13 years ago, translation, In English
А. Guilty — to the kitchen!
Let us reformulate the statement: we need to find the maximum possible value of x (mentioned in the statement) so that the amount of each ingredient will be enough. Clearly, such x equals min(b_i / a_i). Now it suffices to take minimum of the two values: soup volume we gained and the volume of the pan.

В. Game of chess unfinished.

In this problem you are to check exactly what the statement says: if the king's position and all the positions reachable by him in one turn are "beaten", — that's a mate. Thus, we have to determine "beaten" positions correctly. Let us remove the black king from the chessboard, leave the positions of  the rooks "unbeaten" (not to forget about possible taking of the rook by the black king), mark positions reachable by rooks "beaten" and then mark positions reachable by white king as "beaten".

С. Safe cracking.
The answer in this problem is always affirmative, which means it is always possible to make all the numbers equal to one. Greedy approach (here we somehow make two adjacent numbers even and then divide them by two) leads the sum of numbers to become less or equal to six in logarithmic (and certainly less than 1000) number of operations. There are several ways do deal with extremal cases: for instance, many of the participants coped with this by the analysis of all of the cases left. The greedy approach only is not sufficient: the crucial test for hacks was (1 1 1 2).

D. Strange town.
Let us associate some numbers a_i with the vertices of the graph. If, for each edge, we assign it the sum of its endpoints' numbers, then the sum of prices along arbitrary hamiltonian cycle will be equal to the doubled sum of a_i. Therefore, it suffices us to devise such numbers a_i so that their pairwise sums will be distinct (as the edge prices should be distinct). As all of the edge prices are bounded above by 1000, we have to think of an efficient strategy to obtain such a_i. Let's choose them in greedy way, so that newly added a_i should not be equal to (a_p + a_q - a_k) for each triple of already chosen a_p, a_q, a_k. It is clear that a_n = O(n^3) as there are O(n^3) "blocking" triples (p, q, k).
Another idea lies in that equality AB+CD=AC+BD should hold for every quadruple of distinct vertices A, B, C, D (summands stay for edge prices), because a hamiltonial cycle with edges AB and CD can be easily rearranged in the cycle with edges AC and BD and the sums of these cycles should be equal.
You may think of how this idea was used by jury to check your solutions in exact and fast way.

The solution of the problem E will appear soon.

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it