Before contest

Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

06:55:56

Register now »

Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

06:55:56

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | Um_nik | 3309 |

3 | Petr | 3298 |

4 | dotorya | 3225 |

5 | W4yneb0t | 3218 |

6 | OO0OOO00O0OOO0O0…O | 3199 |

7 | Radewoosh | 3150 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | Syloviaely | 3073 |

# | User | Contrib. |
---|---|---|

1 | tourist | 186 |

2 | rng_58 | 175 |

3 | csacademy | 167 |

4 | Petr | 160 |

5 | Swistakk | 156 |

6 | Errichto | 150 |

7 | lewin | 149 |

8 | Zlobober | 144 |

9 | matthew99 | 141 |

9 | adamant | 141 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Hi Codeforces!

The Codeforces Round #438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined) is going to be held on 05 Oct at 9:05 (UTC+2)! The round will be **rated for everyone**.

This round is organised in collaboration with 2nd Hello Barcelona ACM ICPC Bootcamp 2017 and supported by Sberbank, the biggest commercial and investment bank of Central and Eastern Europe, with over 175 years of history.

150 students from 53 universities, including ITMO, University of New South Wales, St. Petersburg State University, MIPT, Ural Federal University, Tomsk State University, Novosibirsk State University, Saratov State University, Samara National Research, Perm State University, and many other top global universities such as USA’s highest placing team, Central Florida University, along with Canada’s University of Waterloo, high-scoring Asian teams from Hangzhou Dianzi and Singapore, and Tokyo University, as well as Stockholm’s KTH, will be competing as individuals for the online round, which includes those of you from Codeforces!

The past week has been full of intense competitions, job interviews with Sberbank, and contest analysis and lectures by Andrey Stankevich (Andrewzta), Mike Mirzayanov (MikeMirzayanov), Gleb Evstropov (GlebsHP), Artem Vasilyev (VArtem) and Mikhail Tikhomirov (Endagorion).

The event is completely international, as teams from all parts of the globe compete and practice side-by-side. They say a picture is worth a thousand words, so here is a selection to give you some idea of what’s happening at our boot camp.

And, once again, we can’t wait to see you all compete on the international stage, smoothing the road towards the April World Finals in Beijing.

The round’s creators are Endagorion, ifsmirnov, zemen and Arterm — team MIPT Jinotega, two-time medalist ACM-ICPC World Final (2016-17). The round is combined for both divisions, will contain seven problems and last for three hours.

Good luck!

**Scoring: 250-500-1000-1500-2250-2500-3500**

**UPD**: Thanks for participating, glory to the winners!

We will publish the editorial as soon as the Barcelona Bootcamp activities conclude.

**UPD2**: the English editorial is here.

A few people have been asking me for tips on practicing. Since explaining this many times is boring, I will be doing a live stream with a small practice routine: virtual round participation and upsolving the problems immediately after (maybe solving something else as well). I'll try to answer your questions as I go, so join in if you're interested.

The stream will start around 16:00MSK on Saturday, September 2nd on my Youtube channel.

UPD: sorry, the stream is going to start at 18:00, not 16:00.

Hello! I've been trying to install moj plugin on a topcoder applet in a new environment. The problem is I'm getting `Exception in thread "AWT-EventQueue-2" java.lang.NoSuchMethodError: com.topcoder.client.contestApplet.common.LocalPreferences.removeProperty(Ljava/lang/String;)Ljava/lang/String;...`

when trying to save preferences of CodeProcessor, at this point:

Pressing the save button doesn't do anything except for raising the exception in the console. Does someone have any information relevant to resolving this issue? Thanks!

Here's my first attempt to participate in a contest while screencasting and commenting in English as it goes, you can watch the video here. Let me know what you think!

**UPD**: screencast of today's DGCJ round.

This time I've decided to play with spoilers to faciliate the presentation as some of the guys here did before. Tell me what you think about this write-up!

Topics: dynamic programming.

Summary: the first "hard" problem of the contest. Knowing your basic DP problems helps a lot, but coming up with the precisely correct solution may take a lot of persistence.

Solution: Suppose that we are allowed to make left circular shifts as well as right ones.

First of all, making a shift is effectively moving a character to a different position in the string. Clearly, moving a character more than once makes no sense since we could have just moved it to its final destination instead without wasting any operations. Also, it obvious that the number of occurences of each character should be the same in both strings since it is preserved by shifts.

Now, consider the characters that are *not* moved by any operation made, and match them with their final destinations in the second string.

Both sets have to respect their relative order since we are not allowed to move them around. Hence, they have to form a common subsequence of the two strings. Note that if the solution made *k* operations, the common subsequence will have length *n* - *k*.

Moreover, we can make any common subsequence of size *k* into a solution that makes exactly *n* - *k* operations: just move all non-stationary characters to their destinations.

We can see that the minimal number of operations is exactly *n* - *k*, where *k* is the size of the longest common subsequence

... think about how the answer could be larger or smaller than this quantity, and try to reach a contradiction with the help of the previous spoilers.

Refer to the link above for the discussion of the *O*(*n*^{2}) DP algorithm to the LCS problem.

Ok, nevermind.

Clearly, the number of occurences of each character must still agree in both strings. Further, it still makes no sense to move the same character twice. Further, the stationary characters still have to form a common subsequence. However, the second sample case shows us that the answer can be greater than *n* - *LCS*(*s*, *t*).

Consider a stationary character *s*_{i} and its destination counterpart in the second string *t*_{j}. Respective to *s*_{i}, we are only allowed to move characters from right part of *s* to the left.

Consider a symbol `x`

. Count its occurences to the right of *s*_{i} and *t*_{j}, denote the counts *A* and *B*. The above reasoning must imply *A* ≥ *B*. For *s*_{i} and *t*_{j} to be possibly matched, this condition must hold for all symbols.

A reasonable line of action is to implement the DP solution for LCS while requiring the conditions above. But are the conditions strong enough to allow only valid solutions (that is, stationary sets of characters that can be extended to a sequence of operations)?

It may not be easy to prove or disprove right away. This is a totally OK situation, even for experienced participants.

If you have a plausible guess that you can't prove but have to confirm, a good idea is to *stress test* it: implement a brute-force solution that is sure to be right, and check if it agrees with your hypothesis on many random cases. If it does, you are very confident that the guess is right, and if it doesn't, you have a counter-example and can investigate further.

Happily, yes!

We have to prove that a satisfactory common subsequence of length *k* gives rise to an operation sequence of length *n* - *k*, or, equivalently, that all non-stationary characters can be moved to correct positions. If there are no stationary characters, then everyone can be rearranged in any order with one operation per character, hence we are done.

Consider the rightmost stationary pair *s*_{i} and *t*_{j}, and the character collections *A* and *B* that lie to the right of *s*_{i} and *t*_{j}. We must have that in the sense that no character occurs more times in *B* than in *A*. We can easily obtain *B* in the final configuration by choosing an equal sub(multi)set in *A* and arranging them in the required order while staying to the right of *s*_{i}.

What should we do with all the rest elements *A*' = *A*\ *B*? We must spend one operation per element of *A*' to move them to the right of *s*_{i} into their final positions. However, we may as well postpone the decision and "merge" *A*' with the next group of characters to the left of *s*_{i}. We then continue with the new rightmost group, and so on until there are no stationary characters left.

Can you solve the problem much faster than *O*(*n*^{2}), or provide hard evidence that a faster solution does not exist?

The problem is closely related to the LCS problem. What does the world know about the complexity of LCS? If we were to show that this problem is at least as hard as LCS, how would we do that?

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

Topics: greedy.

Summary: a gatekeeper for inexperienced and/or impatient contestants. Many details to take into account, but otherwise tractable.

Solution: Since we aim to maximize the number, let us look what is the largest first digit we can possibly place. Let *d* denote the first digit of *n*.

*d*>*y**d*=*y**x*<*d*<*y**d*=*x**d*<*x*

In case 1 we can place *y*, in case 3 we can place *x*, and in case 5 we are forced to make the number shorter by one digit (effectively, placing 0). Since the new number is already compared less than *n*, the rest can be maximized without restraint, that is, filling with *y*'s.

If *d* = *x* or *d* = *y* we may have a chance to match the first digit. However, we cannot tell right away if the first digit can be actually extended to a complete number that does not exceed *n*, e.g. *n* = 20, *x* = 1, *y* = 2.

We may proceed over digits of *n* until we meet a digit *d*' other than *x* and *y*, or the end of the number. In the latter case, the answer is just *n*.

If *d*' > *x*, then the number can be extended to the end (refer to the initial rule for the first letter). If *d*' < *x*, the number can not be extended further and we have to roll back and make some of the eariler digits smaller.

Naturally, we can only decrease *y* to *x*, hence we find rightmost placed *y*, change it to *x* and maximize the rest of the number (since we placed smaller digit at an earlier point).

It follows that *n* starts with *x* and proceeds with a digit smaller than *x*. We can see that there is no satisfactory number of the same length, hence we should decrease the length.

Come on, this is easy to come up yourself (or find in the above spoilers). I mean, seriously?

One can see that this is an *O*(*n*) solution since we make at most one backward pass, and at most two forward passes.

You may want to check the following:

- Can your answer start with a zero?
- Can your answer be a zero?
- Do you handle
*n*= 10^{100 000}correctly? - Okay, I don't know. Try stresstesting!

How many (modulo 10^{9} + 7) positive numbers are there that consist only of digits *x* and *y* and do not exceed *n*? Solve in *O*(*n*) time.

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

Topics: hashing/string algorithms.

Summary: while this is a simple problem, some approaches are better than others in terms of complexity, memory, and implementation tediousness. Pick your poison!

Solution: As a start, how can we prove why the Fibonacci sequence as described in the statement is not 1-recursive?

Then there must exist a function *f*(*x*_{1}) such that *f*(*a*_{i}) = *a*_{i + 1}. But then we must have simultaneously *f*(1) = 1 and *f*(1) = 2, a contradiction!

Indeed, suppose that **any occurence of a number x is followed by the same number y (or the end of the sequence)**. It means that the function defined by

We can see by now that *k*-recursiveness is all about non-contradicting continuations of *k*-tuples: **if there are two consecutive k-tuples of elements followed by different numbers, then the sequence is not k-recursive**. Otherwise, the function defined by

We could do that explicitly by writing out all *k*-tuples along with the subsequent elements, and check for conflicts. This takes *O*(*n*^{3}) time when done explicitly,

time if we sort the tuples and compare only the adjacent pairs,

time if we hash the tuples beforehand using the rolling polynomial hashes.

The rest of the solution is binary search on *k*, with the resulting complexity , or .

Solve the problem:

- in with simple string algorithms (no hashes!)
- in
*O*(*n*^{2}) with simple string algorithms (no hashes!) - in with harder string algorithms (no hashes either!)

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

Topics: greedy, sorting, implementation.

Summary: while the solution is not exactly evident from the start, one has to jumps a lot of hoops and dodge a lot of spikes to avoid all possible mistakes with precision, query limit and whatnot.

Solution:

Suppose that we're willing to spend some amount of goods so that vendor's perceived price is a small ε.

Suppose that we choose to spend only *i*-th good, then we have to spend ε / *d*_{i}, with our perceived value being ε·*c*_{i} / *d*_{i}. Hence, it is optimal to choose the good that minimizes *c*_{i} / *d*_{i}.

Breaking *x* into small ε portions and applying the previous argument, we can see that we should gradually use goods by increasing of *c*_{i} / *d*_{i} until the vendor agrees to sell. Note that goods with equal *c*_{i} / *d*_{i} can be taken in any order.

According to the considerations above, it is beneficial to know the order of goods sorted by *c*_{i} / *d*_{i}.

A key idea is that it is unnecessary to know the values of *c*_{i} / *d*_{i}, but only be able to compare them.

Our query capacity is very limited: a simple YES/NO answer, that we have to apply to precisely comparing numbers. A correct way to do this would be to obtain a configuration with with high precision, and then make alterations to it so that the balance is decided on *c*_{i} / *d*_{i} comparison.

Simply make all *a*_{i} equal and binary search on their common value. About 40-50 iterations should result in a practically precise double value (more on precision issues below).

Let us choose a small, but positive Δ. To compare fractions for *i*-th and *j*-th goods, alter the balanced configuration by performing *a*_{i} - = Δ·*c*_{j}, *a*_{j} + = Δ·*c*_{i}. The value of will be changed by the value of , which has the same sign as *c*_{i} / *d*_{i} - *c*_{j} / *d*_{j}. Note that comparison takes only one query (except for the equal fractions case which may be undecided as of now, more on that later).

Since we now know the order, we can binary search on the total volume of goods we're paying. Greedy considerations above tell us to distribute them greedily from the lowest *c*_{i} / *d*_{i} to the highest.

The resulting solution makes roughly queries, in practice this number is about 450 on the present constraints.

This pretty much concludes the idea description.

The only constraint is that we can't choose Δ to be too large since we may over/underflow *a*_{i}. We know that the common value of *a*_{i} in the balanced configuration will be at least 0.1 away from the borders. To keep the alteration within this distance we have to satisfy Δ *max*(*c*_{i}) ≤ 0.1, hence Δ ≤ 10^{ - 5} is pretty much fine.

Note that the value of will be away from *x* provided we are comparing distinct fractions, hence we are free from precision problems at this point.

This is a bad spot to be. One possible situation when this issue arises when you're using `std::sort`

to sort the fractions with the custom comparator that makes the queries itself. `std::sort`

likes to make additional comparisons to check certain properties of your comparator, such as transitivity. Not only that provides an overhead on the query number, but can also lead to RE if your comparator does not behave well on comparing equal objects: it must always return `false`

on equals.

The reason why our comparison is bad for this prupose is that the value of changes ever so slightly when add practically zero number to it, so that it can dance around *x* and returns random values on comparisons (note that there is no tolerance in `?`

query!).

One solution would be to make slightly larger than *x* so that not to suffer from precision fluctuations (warning: this can break most of the present analysis, do at your own risk).

Note that most sort algorithms are resilient to this kind of problem (e.g., merge or insertion).

Can you solve the problem in queries, where *A* is the maximal value of *c*_{i}, *d*_{i}?

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

Topics: maths, shortest paths in graphs.

Summary: even if you don't come up with a simple mathematical solution, graph algorithms save the day. Easy!

Solution:

We can construct a graph with vertices for each configuration (*x*, *y*, *d*), where (*x*, *y*) is the current point, and *d* is the direction last travelled (note that we only need to remember if the direction was horizontal or vertical). Assuming that we never leave the square with coordinates bounded with 100 by absolute value The graph has < 200 000 vertices and < 400 000 edges, hence we can find the shortest path with a simple BFS.

Denote Δ_{x} and Δ_{y} the absolute differences of *x* and *y* coordinates respectively.

.

Without loss of generality, suppose that Δ_{x} ≥ Δ_{y}. First, we cannot make less than moves. Indeed, we have to make at least Δ_{x} horizontal moves to get to the finish, and, because of alternation, at least Δ_{x} - 1 vertical steps. We also change the parity of sum of coordinates after each step, and that determines the parity of *y*-steps.

Second, this number of steps is enough. To see that, first travel to the point (Δ_{y}, Δ_{y}) in 2Δ_{y} steps with a repeated `UR`

step pattern, and then repeat the RURD pattern until you reach the target. One can check explicitly that the lower bound on the number of steps is reached exactly.

How to solve the problem if we are travelling in *k*-dimensional Manhattan, that is, the position is given by a *k*-tuple of integer coordinates, and we're allowed to change one coordinate at a time, and must change the "streets" (coordinates we change) after each step? Solve in time.

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

Topics: game theory, graphs, math.

Summary: frankly, I anticipated a lot more solutions on this problem. All ideas seemed basic to me, and the code is very easy. Still, it seems that cracking the whole thing was not that simple. Did you enjoy solving it? =)

Solution:

For the, say, Red player we must have *k*_{R} = *v*_{R} - *e*_{R}, where *v*_{R} is the number of red vertices, and *e*_{R} is the number of edges with both endpoints red.

Red player wants to maximize *k*_{R} - *k*_{B}, which is equal to (*v*_{R} - *e*_{R}) - (*v*_{B} - *e*_{B}) = (*v*_{R} - *v*_{B}) - (*e*_{R} - *e*_{B}). Note that *v*_{R} and *v*_{B} are independent of the players' actions, and . It follows that the equivalent game would be to minimize *e*_{R} - *e*_{B}.

Let us keep a counter on each edge. When Red player moves to a vertex, all counters of incident edges increase by 1, and when a Blue player moves, all incident counters decrease by 1.

On one hand, the is clearly (sum of degrees of Red's vertices) — (sum of degrees of Blue's vertices).

On the other hand, a red edge (with both endpoints red) has +2 on it, as a blue edge has -2. A neutral edge has 0 on it. It follows that the same total is equal to 2(*e*_{R} - *e*_{B}).

The above discussion implies that moving to a vertex of degree *d* effectively gives you *d* / 2 penalty against your score.

It is now clear that the optimal strategy is to **always move to a free vertex of the lowest degree, regardless of any previous actions**.

This is easily implemented into a clean *O*(*n*) solution.

How to play this game on a unicyclic graph (a connected graph with *n* vertices and *n* edges)? What can you say about complexity in the case of a general graph?

I will post the solutions to challenges at a later time, enjoy solving yourself for now. =)

I'll be glad to hear all your opinions in the comments. Thanks for participating!

Hi!

It is my pleasure to inform you that today, on June 4 at 15:00 MSK the third and final elimination round of the Yandex.Algorithm 2017 championship will take place. I'm equally pleased to tell that the problems of the round were prepared by me, Mikhail Tikhomirov. I worked for Yandex for three years, and had a great time in a friendly and professional team. Cheers to Yandex!

This round wouldn't take place if not for the work of these great people:

Lidia lperovskaya Perovskaya and her team who are responsible for the Yandex.Contest system,

Maxim Zlobober Akhmedov, previously a vigilant Codeforces coordinator, and currently a vigilant Yandex.Algorithm coordinator,

Mike MikeMirzayanov Mirzayanov and the Codeforces crew who support the Polygon problem preparation system,

and finally, all Yandex employees who took part in testing the problems of the round (sadly, the margin of this blog is too narrow to contain all their names).

The round will feature the standard scheme: 6 **randomly shuffled** problems for 100 minutes with TCM/Time ranking system. The last GP30 points will be distributed judging by the round results, and the final round advancers will be determined at last (find current scoreboard here). You still have the chance to advance even if you missed the previous rounds!

An editorial will be published in a separate blogpost after the round is concluded. We wish good luck to all participants, and hope you enjoy the problems!

**UPD**: the start is delayed by 15 minutes for technical reasons. Sorry for the inconvenience!

**UPD2**: the round is finished! Here be editorial.

Yesterday, on April 23 an Open Cup round — Grand Prix of Moscow Workshop was held. In fact, the same contest was held on April 17, the last day of Moscow Pre-Finals ACM ICPC Workshop.

The problems were prepared by the workshop programming committee: Mikhail Tikhomirov (Endagorion) and Gleb Evstropov (GlebsHP), as well as members of MIPT teams Jinotega: Ivan Smirnov (ifsmirnov), Artsem Zhuk (Arterm), Konstantin Semenov (zemen), and Cryptozoology: Alexander Ostanin (Kostroma), Alexander Golovanov (Golovanov399), Nikita Uvarov (I_hate_ACM). We hope you enjoyed solving our contest!

The results can be found on the Open Cup page. Our congratulations to teams SPb ITMO University 1 (Belonogov, Zban, Smykalov) and the veteran team SPb Havka-papvsto (Kunyavsky, Kopeliovich) on solving all 11 problems! Please not that since Java issues in Yandex.Contest are not fully resolved yet, the results are not final and Java submissions may be subject to rejudge.

Here is a link to PDF editorial for the problems, prepared by myself and GlebsHP. Please ask your questions and point out the mistakes in the comment section.

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Sorry for the wait! We'll be glad to answer your questions in the commens.

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

I hope you've enjoyed the problems! Please ask your questions and report flaws in the comments.

First insight is that two spells are always enough. Why? Let's freeze all leftbound penguins at point 10^{ - 9} and all rightbound penguins at point 10^{9}.

So the only problem is to determine when only one spell is enough. If that holds, there should exist a point which all penguins will cross at some moment. Let's put this point at *x*_{} + ~--- rightmost point among penguins' coordinates which run to the right. Now all rightbound penguins will cross this point. If there is a leftbound penguin which doesn't cross *x*_{} + then its coordinate *x*_{} - must be less than *x*_{} + . But in this case there are two penguins running away from each other~--- clearly one spell will not suffice.

So, the easiest and most effective solution is to find *x*_{} + ~--- the location of rightmost rightbound penguin, and *x*_{} - ~--- the location of leftmost leftbound penguin, and check if *x*_{} - < *x*_{} + . If that holds, the answer is 2, otherwise it's 1. This can be easily done in *O*(*n*). Other approaches include checking for all pairs of penguins if they run away from each other in *O*(*n*^{2}), or more effeciently using sorts in .

Let's divide all configurations by leftmost turned-on bulb. Suppose the leftmost turned-in bulb is *i*-th. If *i* + *k* - 1 ≤ *n*, then the bulbs *i* + 1, \ldots *i* + *k* - 1 can be turned on or off in any combinations, so the number of such configurations is 2^{k - 1}. If *i* + *k* - 1 > *n*, then the ``free'' bulbs are limited by the end of the line, and the number of configurations is 2^{n - i}. There is also one combination when all bulbs are off.

These quantities can be summed up in if one uses binary modulo exponentation of 2, or in *O*(*n*) if the powers of 2 are precomputed with DP. It can also be shown (by summing the geometric progression which you can try to do yourself) that the answer is always equal to (*n* - *k* + 2)2^{k - 1}, this number can be computed in .

Let's come up with a straightforward solution first. We will just simulate the battles and keep the current value of *M*. How many iterations we will have to make? And more importantly, how can we tell if the answer is - 1 or we just didn't do enough battles yet?

To answer that, let's keep track of values of *M* before all battles with the first opponent. If some value of *M* repeats twice, then the whole process is looped and the answer is - 1. On the other hand, if *M* > *A* (the largest possible value of *a*_{i}, that is, 10^{6}) we will surely win all battles. So the maximal number of iterations is *n*(*A* + 1) (since no value of *M* ≤ *A* can repeat twice).

This is still too much for straightforward simulation ( battles). How can we optimize that? Let us find *f*(*M*)~--- the number of first lost battle for each value of *M* at the start that does not exceed *A*. This can be done in *O*(*A*) for all *M*'s at the same time using the fact that *f*(*M*) does not decrease. Indeed, suppose we know *f*(*M*) and also *g*(*M*)~--- our power before battling the last opponent. If the starting power were *M* + 1, at this point our power would be *g*(*M*) + 1. If this is still not enough to win opponent *f*(*M*), then *f*(*M* + 1) = *f*(*M*), *g*(*M* + 1) = *g*(*M*) + 1. Otherwise, we proceed to following opponents updating *f*(*M* + 1) and *g*(*M* + 1) accordingly until we lose or win them all. Notice that the total number of increases of *f*(*M*) is at exactly *n*, thus the complexity is *O*(*n*).

Using values *f*(*M*) we can emulate the battles much more quickly: for given *M* find the first lost battle, add *f*(*M*) to the total number of battles, update *M* with *max*(0, *g*(*M*) - *a*_{M}), proceed until we win everyone or *M* repeats. This optimization leads to *O*(*n* + *A*) solution.

There is another tempting idea for this problem which turns out to be wrong. If you have trouble with WA3, consider this case:

```
4 2
0 5 0
6 0 3
7 0 6
8 0 4
```

Let's call a position *x* \emph{interesting} if *color*(*x*) ≠ *color*(*x* - 1). If we find two interesting positions *x* < *y* so that *color*(*x*) = ... = *color*(*y* - 1), then the answer is equal *y* - *x*.

How can we find a single interesting position? Suppose we have two arbitrary positions *a* < *b* and *color*(*a*) ≠ *color*(*b*). Then we can find an interesting position *x* with *a* < *x* ≤ *b* using binary search: let . If *color*(*a*) ≠ *color*(*c*) update *a* with *c*, otherwise update *b* with *c*. At some point *b* - *a* = 1 and we're done. Denote this resulting position as *f*(*a*, *b*).

Okay, how to find two positions of different colors first? Let *M* be the maximal possible value of *L*. Consider a segment of length, say, 2*M*. The colors inside this segment have to be distributed \emph{almost evenly}, so after trying several random cells we will find two different colors with high probability.

There are several possible options what to do after we have obtained two interesting positions *x* and *y*. We can use the fact that either the segment *x*, \ldots, *y* - 1 is same-colored, or it has at least 1 / 3 of the cells with *color*! = *color*(*x*), so we can try random cells until we find *z* with *color*(*z*) ≠ *color*(*x*), and then we can shrink the segment to either *x*, *f*(*x*, *z*) or *f*(*z*, *y*), *y*, whichever's shorter. Length of the segment shrinks at least two times after each iteration (in fact, it shrinks even faster).

Another approach is to note that *L* divides *y* - *x* for all interesting positions *x* and *y*. Thus we can obtain several interesting positions *f*(*a*, *b*) for random values of *a* and *b*, and find *G*~--- GCD of their differences. Clearly, . It can also be shown that *G* = *L* with high probability is the number of positions is, say, at least 50; it is a bit harder to analyze though, but the general idea is that while it's hard to determine the exact distribution of *f*(*a*, *b*), it is \emph{not that bad}, so it is improbable for many values of *f*(*a*, *b*) to be, say, multiples of 2*L* apart.

I want to describe another, much simpler solution by Chmel_Tolstiy. Let's find the smallest *k* such that *color*(2^{k}) ≠ *color*(0). It is easy to prove that there is exactly one change color between these two positions, so its position can be found with binary search as before. Do the same way in negative direction and find another closest color change, output the difference. This solution turned out to be most popular among contestants (but less popular among the testers).

Let's find out how to check if the answer is at most *D* and binary search on *D*.

Let's make an arbitrary vertex the root of the tree. Note that if the subtree of any vertex *v* contains even number of outposts then no paths can come out of the subtree (since their number must be even, but at most one path can pass through an edge). Similarly, if there is an odd number of outposts then one path must come out of the subtree. Consider all children of *v*: each of their subtrees will either yield a single path or nothing. We have to match the resulting paths between each other and choose at most one of them to yield to the parent. Naturally, our intention is to make the unmatched path as short as possible while making suring that in each pair of matched paths their total length does not exceed *D*. We can also note that the answer is never - 1 since we can always match the paths if we ignore their lengths.

Consider the case when we have to match an even number of paths. Let's say we have an array of even length *a*_{1}, \ldots, *a*_{2k}, and want to make pairs of its elements such that sum in each pair does not exceed *D*. It can be shown that the optimal way is to sort the array and then match *a*_{1} + *a*_{2k}, *a*_{2} + *a*_{2k - 1}, and so on. Indeed, consider that *a*_{1} is not matched with *a*_{2k} but with *a*_{x}, and *a*_{2k} is matched with *a*_{y}. Let's rematch them as *a*_{1} + *a*_{2k} and *a*_{x} + *a*_{y}. Since the array is sorted, *a*_{1} + *a*_{2k}, *a*_{x} + *a*_{y} ≤ *a*_{y} + *a*_{2k} and the maximum sum won't increase after rematching. Drop the elements *a*_{1} and *a*_{2k} and proceed until we obtain the matching *a*_{1} + *a*_{2k}, *a*_{2} + *a*_{2k - 1}, \ldots.

Now we want to match an odd number of paths while minimizing the unmatched path length. This can be done with binary search on unmatched length and checking if the rest of the paths can be matched using previous approach. Another approach is greedy: take the maximal element *x*, find maximal element *y* such that *x* + *y* ≤ *D*, erase them both. If there is no such *y*, then *x* must be unmatched. Finally, check if there is at most one unmatched element. All these approaches take time for a vertex with *d* children, but the real time depends hugely on the actual approach (say, using std::set or TreeSet is much slower than sorts and binary searches).

The total complexity is , where *A* is maximal possible answer value.

Consider all possible values of *a* and *b* such that . Let's arrange them in a table, roughly like this (second sample, O stands for possible value, . for impossible):

```
0 1 2
0 O O .
1 O . .
2 . . .
```

When can one determine the numbers? Consider the position (0, 1): the person with number 2 knows that the only possible pair is (0, 1), so he can answer it. In general, once there is only one possible value in some row or some column this value is removed on this day since one person can deduce the other number. So, after day 1, the table becomes (X stands for no longer possible value):

```
0 1 2
0 O X .
1 X . .
2 . . .
```

Now position (0, 0) can be solved on day 2 according to our rule. One can see that in the third sample the only solvable positions are (0, 2) and (2, 0).

It is tempting to look for a simple formula, but behaviour of how positions are resolved turns out to be complex (for example, try *X* = {5, 13, 20}). We should look for a way to simulate the process efficiently.

First, note that there will be at most 2(*A* + 1) resolved positions, where *A* is the maximal element of *X*. Indeed, each resolved position leaves a new empty row or a column. Thus, the process will terminate quite quickly, but the total number of possible initial positions is too large to choose resolved positions straightforwardly.

There are few possible optimization. For one, suppose we have the data structure with following operations: initialize with a set of numbers, remove a single number, once there is a single number in the set, find it. Let's store this kind of structure for each row and column, now the process can be simulated easily. The simplest way to implement this structure is to store a pair (sum of numbers, count of numbers). Moreover, all the structures can be initialized at once in *O*(*A*) time using prefix sums and prefix counts.

Another idea: if there are three consecutive numbers *x*_{i}, *x*_{i + 1}, *x*_{i + 2} with *x*_{i + 2} ≤ *x*_{i} + *x*_{i + 1} + 1, then all positions with *a* + *b* < *x*_{i} will be unsolvable. If we drop all *x*_{j} < *x*_{i}, the sum of the rest elements of *X* will be *O*(*A*), which allows for a simple simulation.

Cheers everyone.

Today, on June 13 at 10:00 MSK the third and final qualification round of Yandex.Algorithm 2016 tournament will take place. I am the author of all tasks in this round. I wish to thank Ivan Gassa Kazmenko, Oleg snarknews Khristenko, and espically Aleksey Chmel_Tolstiy Tolstikov and Maxim Zlobober Akhmedov for their immense contribution to problems preparation. I also thank Yandex employees who were involved in testing this round.

Best of luck!

**UPD**: the round is complete! Congratulations to Um_nik, who was the only one to solve all problems!

You can find the elimination standings here. Congratulations to 25 best participants!

Editorial here

I'm terribly sorry for the delay.

Please report any mistakes.

Author: Tigutor

You had to print all numbers of form *k*^{x} for non-negative integers *x* that lie with the range [*l*;*r*]. A simple cycle works: start with 1 = *k*^{0}, go over all powers that do not exceed *r* and print those which are at least *l*. One should be careful with 64-bit integer overflows: consider the test *l* = 1, *r* = 10^{18}, *k* = 10^{9}, the powers will be 1, 10^{9}, 10^{18}, and the next power is 10^{27}, which does not fit in a standard integer type.

Author, developer: ch_egor

You were asked to print the product of *n* large numbers, but it was guaranteed that at least *n* - 1 are beautiful. It's not hard to see that beautiful numbers are 0 and all powers of 10 (that is, 1 followed by arbitrary number of zeros). If there is at least one zero among the given numbers, the product is 0. Otherwise, consider the only non-beautiful number *x* (if all numbers are beautiful, consider *x* = 1). Multiplying *x* by 10^{t} appends *t* zeros to its decimal representation, so in this case we have to find the only non-beautiful number and print it with several additional zeros.

We tried to cut off all naive solutions that use built-in long numbers multiplication in Python or Java. However, with some additional tricks (e.g., ``divide-and-conquer'') this could pass all tests.

Author, developer: platypus179

Consider distances between the point *P* and all points of the polygon. Let *R* be the largest among all distances, and *r* be the smallest among all distances. The swept area is then a ring between circles of radii *R* and *r*, and the answer is equal to π (*R*^{2} - *r*^{2}).

Clearly, *R* is the largest distance between *P* and vertices of the polygon. However, *r* can be the distance between *P* and some point lying on the side of the polygon, therefore, *r* is the smallest distance between *P* and all sides of the polygon.

To find the shortest distance between a point *p* and a segment *s*, consider a straight line *l* containing the segment *s*. Clearly, the shortest distance between *p* and *l* is the length of the perpendicular segment. One should consider two cases: when the end of the perpendicular segment lies on the segment *s* (then the answer is the length of the perpendicular segment), or when it lies out of *s* (then the answer is the shortest distance to the ends of *s*).

Author: cdkrot

Developers: cdkrot, galilei2000, ch_egor

Let's save the original positions of skills and then sort the skills in non-increasing order (almost decreasing) by current level. We can always restore original order after.

Imagine that we have decided that we want to use the minimum level *X* and now we're choosing which skills we should bring to the maximum.

At first, let's rise all skills below *X* to level *X*, this will set some tail of array to *X*. But the original array was sorted, and this new change will not break the sort! So our array is still sorted.

Obviously, the skills we want to take to the maximum are the ones with highest current level. They are in the prefix of array. It is easy to show that any other selection is no better than this greedy one.

Now we have shown that the optimal strategy is to max out the skills in some prefix. Now let's solve the problem.

Let's iterate over prefix to max out, now on each iteration we need to know the highest minimum we can achieve, let's store the index of the first element outside the prefix such that it is possible to reach the minimum level ≥ *arr*_{index}.

It is easy to recalc this index, it slightly moves forward each turn and, after precalcing the sum of all array's tails, you can update it easily (just move it forward until the invariant above holds). And knowing this index is enough to calc the current highest possible minimum level (*min*(*A*, *arr*_{index} + ⌊ *sparemoney* / (*n* - *index*)⌋).

How to restore the answer? Actually, all you need to know is the count of maximums to take and minimum level to reach.

Author: cdkrot

Developers: cdkrot, MF2000, ch_egor

Surprisingly, the nice cuts can't be put randomly. Let's take a look on the first picture above (red lines represent nice cut points). But since the necklace is symmetrical relative to nice cuts, the cut points are also symmetrical relative to nice cuts, so there is one more cut (see picture two). Repeating this process, we will split the whole necklace into parts of the same size (picture three).

If the number of parts is even, then each part can be taken arbitrarily, but the neighbouring parts must be reverses of each other (e.g. "abc" and "cba"). This is an implication of the cuts being nice.

If the number of parts is odd, then each part is equal to each other and is a palindrome, this is an implication of the cuts being nice too.

Anyway, the number of characters in each part is equal, so amount of parts can't be greater than . Actually, it may be zero, or its divisor.

If the number of odd-sized colors is zero, then the sum is even and gcd is even, this way we can construct a building block containing exactly beads of

*i*-th color, (gcd being gcd of all counts), then build beads of*gcd*parts, where each part equal to building block, with neighbouring parts being reverses. Since*gcd*is even, everything is ok.If the number of odd-sized colors is one, then the sum is odd and gcd is odd. Building block have to be built as a palindrome containing beads of

*i*-th color, exactly*n*- 1 of colors will be even and one odd, put the odd one in center, others on sides (aabcbaa). Everything is ok.If num of odd counts is

*geq*2. Gcd is odd, all its divisors too, so our building block has to be palindrome. Let*k*denote the number of parts. A building block will contain beads of color*i*, at least two of these numbers are odd, it is impossible to build such a palindrome. The answer is zero.

Complexity: *O*(*sum*), just to output answer.

Bonus. How to solve problem, if you are allowed to discard any subset of beads before constructing necklace?

Bonus. Given a necklace scheme (like one you were asked to output), how to determine number of nice cuts, *O*(*sum*), no suffix structures or hashes?

Authors: ch_egor and others

Developer: cdkrot

Obviously, the answer is -1 iff two important cities are adjacent.

If there was a single query, can we answer it in *O*(*n*) time? Let's choose a root arbitrarily. We can note there is an optimal answer that erases two types of vertices: vertices that lie on a vertical path between two important vertices, or LCA of some pair of important vertices.

Let's do a subtree DP that counts the answer for the subtree of *v*, as well as if there is any important vertex still connected to *v* in the answer. How do we count it? If *v* is important, then we should disconnect it from any still-connected vertices from below by erasing these children which contain them. If *v* is not important, then we erase it iff there are more than one still-connected important vertices below. All calculations are straightforward here.

How do we process many queries now? There are many possible approaches here (for reference, look at the accepted solutions). The author's solution was as follows: if we have a query with *k* important vertices, then we can actually build an auxiliary tree with *O*(*k*) vertices and apply the linear DP solution to it with minor modifications.

How to construct the auxiliary tree? We should remember the observation about LCAs. Before we start, let us DFS the initial tree and store the preorder of the tree (also known as "sort by `tin`

"-order). A classical exercise: to generate all possible LCAs of all pairs among a subset of vertices, it suffices to consider LCAs of consecutive vertices in the preorder. After we find all the LCAs, it is fairly easy to construct the tree in *O*(*k*) time. Finally, apply the DP to the auxiliary tree. Note that important cities adjacent in the auxiliary tree are actually not adjacent (since we've handled that case before), so it is possible to disconnect them.

If we use the standard "binary shifts" approach to LCA, we answer the query in time, for a total complexity of .

Author, developer: Endagorion

The key observation: any way to cross out the word *w* looks roughly as follows:

```
..v<1.>>v.2<...
..>>>>^.>>>^...
```

That is, there can be following parts:

go back

*a*symbols in one row, then go forward*a*symbols in the other row (possibly*a*= 0)go forward with arbitrarily up and down shifts in a snake-like manner

go forward

*b*symbols in one row, then go back*b*in the other row (possibly*b*= 0)

Note that the "forward" direction can be either to the left or to the right. It is convenient that for *almost* any such way we can determine the "direction" as well as the places where different "parts" of the path (according to the above) start. To avoid ambiguity, we will forbid *a* = 1 or *b* = 1 (since such parts can be included into the "snake").

Fix the direction. We will count the DP *d*_{x, y, k} for the number of ways to cross out first *k* letters of *w* and finished at the cell (*x*, *y*) *while being inside the snake part of the way*. The transitions are fairly clear (since the snake part only moves forward). However, we have to manually handle the first and the last part. For each cell and each value of *k* we can determine if the "go-back-then-go-forward" maneuver with parameter *k* can be performed with the chosen cell as finish; this can be reduced to comparing of some substrings of field of rows and the word *w* (and its reversed copy). In a similar way, for any state we can check if we can append the final "go-forward-then-go-back" part of the path to finally obtain a full-fledged path.

This DP has *O*(*n*^{2}) states and transitions. However, there are still some questions left. How do we perform the substring comparisons? There is a whole arsenal of possible options: (carefully implemented) hashes, suffix structures, etc. Probably the simplest way is to use Z-function for a solution that does *O*(*n*^{2}) precalc and answers each substring query in *O*(1) time (can you see how to do it?).

Also, there are paths that we can consider more than once. More precisely, a path that consists only of the "go-forward-the-go-back" part will be counted twice (for both directions), thus we have to subtract such paths explicitly. Every other path is counted only once, thus we are done. (Note: this does not exactly work when *w* is short, say, 4 symbols or less. The simplest way is to implement straightforward brute-force for such cases.)

Tutorial of Codeforces Round #339 (Div. 1)

Tutorial of Codeforces Round #339 (Div. 2)

There's always a problem to fall asleep after a late night (early morning) match, also drinking coffee during competition doesn't exactly help with that. So, here comes a rough write-up of div1 problems.

As one can verify easily using prime factorization theorem, the LCM of a set of numbers is , where α_{p} is the maximal power of *p* which divides some element of the set. Let us find largest *p*^{t} ≤ *n* for every prime *p* ≤ *n*; there should be a number in [*n* + 1;*m*] that divides *p*^{t} as well. Thus, ; there is a case when the new number divides some greater power of *p*, but we're fine with that. Find the greatest lower constraint for all *p* ≤ *n*. Use the Eratosphene's sieve to find all the primes. An *O*(*n*) solution is possible.

Consider vertices from left to right. How many ways there are to place a new vertex along with an outcoming edge (if any)? There are *k* ways to place the vertex without an edge; if we choose the incoming vertex for the new edge, this excludes one color among possible options. Thus, if *x* vertices were already placed, there are exactly *k* + *x*(*k* - 1) ways to place a new vertex, possibly with an edge. The answer is simply the product *k*·(*k* + (*k* - 1))·(*k* + 2(*k* - 1))·.... It suffices to notices that *M* is rather small, and the product elements are looped modulo *M*, thus it is easy to find out how many times an element contributes to the product. Take care not to overflow int64. An solution is possible.

Connecting two vertices with a zero-weight edge is effectively the same as merging the vertices into one; we will further go with this interpretation.

Call the parts of the graph between the merged vertices the *havens* (or whatever); a haven can be a loop or a pair of paths joined together. A loop haven can be represented by a pair of numbers (*l*, *r*) — the numbers of merged points in the original enumeration. Denote *L*_{l, r} (*R*_{l, r}) the largest distance from a vertex of (*l*, *r*)-haven to the merged vertex *l* (*r*), *S*_{l, r} the largest distance between any two vertices of (*l*, *r*)-haven, and *D*_{l, r} the distance between *l* and *r* (after merging each of them). All these numbers can be computed in *O*(*n*^{3}) for all pairs (*l*, *r*) (use two pointers to compute *S*_{l, r}).

Suppose we have chosen pairs of vertices to merge; which pair of vertices can be farthest apart now? The farthest pair of vertices (*u*, *v*) can lie in the same haven, or in different havens. In the first case all pairs of vertices will be considered explicitly; in the second case the distance is equal to *L* + *D*_{1} + ... + *D*_{k} + *R*, where *L* is the distance from *u* to the closest merged vertex, *D*_{1}, ..., *D*_{k} are distances between consecutive merged vertices inside a single haven, and *R* is the distance from the last merged vertex to *v*.

Binary search the diameter *x*. Compute *dp*_{i, j} with the following meaning: suppose we merged *j* pairs of vertices with last pair to merge having index *i*, we also took care that in the processed part no pair of vertices is at distance larger than *x*; than *dp*_{i, j} is the largest value of *L* + *D*_{1} + ... + *D*_{k} such that the last merged vertex of *D*_{k} is the merged vertex *i*. Initialize *dp*_{i, 1} with the two-paths havens, after that consider all possible options for the next vertex *i*; consider pairs of points in the current haven using *S*_{l, r} and all the rest using the DP value. Finally, to find the answer use such *dp*_{i, k} that the last two-paths haven does not have its vertices too far apart, and also *dp*_{i, k} + *tail*_{i} ≤ *x*, where *tail*_{i} is the largest distance from *i* to any of the ends. That makes for an solution, also probably a highly optimized *O*(*n*^{4}) might pass.

Just a few quick notes about problems (not the full-sized editorial as usual).

Iterate over all possible lengths of top/floor *l*_{t} and walls *l*_{w} (note that they can be equal); reserve two planks of chosen lengths for each. If there are *a*_{i} planks of length *l*_{i} left, there should at least (be careful not to divide by zero of *l*_{w} = 1!) departments of width *l*_{i}. The number of inner walls is equal to the number of departments, except for the case when the total width of departments is equal to the width of the bookshelf (we don't need the last inner wall). Check if there are sufficient planks for inner walls, and also if the departments fit into the bookshelf; also, excessive inner walls should placed in the free space. That's an *O*(*n*^{3}) solution; finally, notice that the floor should be longer than all the shelves, thus it makes sense to try only the two largest types of planks for the floor. Finally, *O*(*n*^{2}).

The most failed problem of the contest. Most accepted solutions are for this problem, I guess, due to a) it was in the beginning of the problemset, and b) this type of problem occurs frequently on many contests. I apologize for the low quality of the problem.

The idea is as follows: the dividing line can be moved so that is nearly passes throw some two cities. Iterate over the pair of these 'border' cities, and find the total population on both sides of the line; choose the best option. To speed up, fix one border city and rotate the line around it. there are *O*(*n*) events when a changes side respective to the line; sort them by angle and process iteratively. That makes up for an solution. I tried to make sure no *O*(*n*^{3}) solutions pass, but it seems I failed even at that. =(

There is a straightforward *O*(*n*^{4}) DP solution which basically stores all the interesting info about the state of the game; it can be probably optimized to *O*(*n*^{3}). I will describe another, more thought-requiring solution.

Consider an inverse permutation of the deck; that is, if the *i*-th number of the deck is *p*_{i}, numbers *q*_{i} are determined by *q*_{pi} = *i*. The number 1 will be surely thrown out on the first discarded through the cards; the number will be discarded on the first pass if *q*_{2} > *q*_{1} or *q*_{2} > *q*_{3} > ... > *q*_{n}; and so on.

We see that on each pass through the cards maximal increasing prefix and maximal decreasing suffix of *q* will be discarded; on the next pass the new maximal monotonous prefix and suffix will be discarded and so on. Suppose there will be *m* passes through the deck, and the final number is *k*; this means that there are exactly *m* - 1 increases in *q* to the right of *k*, and exactly *m* - 1 drops (or, in other words, *k* - (*m* - 1) increases) to the left of *k*; thus the total number of increases will be *k* - 1 regardless of *m*. The problem reduced to a classic one: count the number of permutations of *n* number with exactly *k* - 1 increases. It can be done straightforwardly in *O*(*n*^{3}), or even faster using some ingenious formulas.

Coming up.

The information about the tree can be stored simply as a sequence of operations. The sizes of the tree after each operation will also be useful. The "+ *k*" is thus trivial.

Now to find the distance between two vertices. This can be divided into two tasks: finding depth (distance from the root) *d*(*v*) of the vertex *v* given its number, and determining depth of the LCA of two vertices; the distance is given by *d*(*x*) + *d*(*y*) - 2*d*(*lca*(*x*, *y*)).

If *v* = 1, the depth is clearly 0. Otherwise, the number of the subtree of the root which contains *v* is ⌊ (*v* - 1) / *s*, where *s* is the size of a single subtree. Similarly, the number of vertex *v* in the subtree in its original numeration is . We have reduced the problem to the similar one concerning the subtree; treat it recursively. The sequence of sizes provides all the necessary information; thus, the depth can be found in *O*(*h*), where *h* is the height of the tree.

To find LCA of *x* and *y*, proceed similarly; the root of the current tree if the LCA if one of *x* or *y* is the root, or they are contained in different subtrees. Thus, the depth of LCA can also be found in *O*(*h*).

Unfortunately, *h* can be rather large. However, there can be very few operations (less than 60) with *k* ≥ 2 as the total number of vertices is at most 10^{18}. We can store the operations with *k* = 1 in compressed form, as they just attach one edge to the root of tree. Finally, all the operations with little enhancement can be done in *O*(*h*'), where *h*' is the number of operations with *k* > 1.

If *a* = *c*, the answer is simply *min*(*b*, *d*) (the shortest sawtooth length).

Otherwise, suppose *a* > *c*. Consider the space between two sawtooths of (*c*, *d*)-saws; we may as well consider the (*a*, *b*)-saw wrapped up around the space. The ends of the sawtooths of (*a*, *b*)-saw form a modular sequence , which is the same set of ends as the periodical sequence with diffence ; thus the (*a*, *b*)-saw can be changed to the saw with difference but the same angle of sawtooths. Finally, we arrive at the previous situation with the common difference of ; the saw with the least steep angle of sawtooth will determine the maximal length. Thus, the answer is . Do not forget to use 64-bit integers for multiplication.

As usual, a challenge comes with every problem. I tried not to repeat the mistakes of my previous editorials and made sure that all challenges have a solution =) (except for the *italics* parts that are open questions, at least for me). Go ahead and discuss them in the comments! General questions about problems and clarification requests are welcomed too.

**UPD**: I added codes of my solutions for all the problems. I didn't try to make them readable, but I believe most part of them should be clear. Feel free to ask questions.

Let me first clarify the statement (I really wish I didn't have to do that but it seems many participants had trouble with the correct understanding). You had to erase exactly one substring from the given string so that the rest part would form the word `CODEFORCES`

. The (somewhat vague) wording `some substring`

in the English translation may be the case many people thought that many substrings can be erased; still, it is beyond my understanding how to interpret that as 'more than one substring'. Anyway, I'm sorry for the inconvenience.

Right, back to the problem. The most straightforward approach is to try over all substrings (i.e. all starting and ending positions) to erase them and check if the rest is the wanted word. When doing this, you have to be careful not to forget any corner cases, such as: erase few first letters, erase few last letters, erase a single letter, and so on. A popular question was if an empty substring may be erased or not. While it is not clarified explicitly in the statement, the question is irrelevant to the solution, for it is guaranteed in the statement that the initial string is not `CODEFORCES`

, so erasing nothing will not make us happy. From the technical point of view, you could erase a substring from the string using standard functions like `substr`

in C++ or similar, or do some bare-hands work and perform conditional iterating over all symbols. Depending on the implementation, this would be either *O*(*n*^{2}) or *O*(*n*^{3}) solution; both of these fit nicely.

One way of solving this in linear time is to compute the longest common prefix and suffix for the given string and the string `CODEFORCES`

. If their total length is at least 10 (the length of `CODEFORCES`

), it is possible to leave only some parts of the common prefix and suffix, thus the rest part (being a substring, of course) may be removed for good. If the total length is less than 10, no such way exists. This is clearly *O*(*n*) solution (rather *O*(*n*) for reading the input, and *O*(|*t*|) for comparisons where *t* is `CODEFORCES`

in our case).

**Sample solution**: 10973831

**Challenge (easy)**. A somewhat traditional question: how many (modulo some prime number) large Latin letter strings of length *n* have the property that a (non-empty) substring may be cut out to leave a given string *t*? Can you solve it in *O*(*n* + |*t*|^{2}) time? In *O*(*n* + |*t*|) time? Maybe even faster? =)

*n* is up to 10^{6}. We may note that there are only 2^{6} + 1 = 65 quasi-binary numbers not exceeding 10^{6}, so we could find them all and implement a DP solution that counts the optimal representation for all numbers up to *n*, or even a brute-force recursive solution (which is not guaranteed to pass, but has a good odds).

Are there more effective solutions? Sure enough. First of all, one can notice that the number of summands in a representation can not be less than *d* — the largest digit in decimal representation of *n*. That is true because upon adding a quasi-binary number to any number the largest digit may not increase by more than 1 (easy enough to prove using the standard algorithm for adding numbers). On the other hand, *d* quasi-binary numbers are always enough. To see that, construct a number *m* as follows: for every digit of *n* that is not 0, place 1 in the corresponding digit of *m*, and for all the other digits place 0. Clearly, *m* is quasi-binary. If we subtract *m* from *n*, all non-zero digits will decrease by 1 (clearly, no carrying will take place), thus the largest digit of *n* - *m* will be equal to *d* - 1. Proceeding this way, we end up with the representation of *n* as a sum of *d* quasi-binary numbers. This solution is good for every numeric base, and works in where *d* is the base.

**Sample solution**: 10973842

**Challenge (easy)**. Let us call a number *pseudo-binary* if its decimal representation contains at most two different digits (e.g., 1, 555, 23, 9099 are pseudo-binary, while 103, 908 and 12345 are not). Represent an integer *n* as a sum of pseudo-binary numbers; minimize the number of summands. *n* ≤ 10^{18}.

We want to make the maximum height as large as possible. Consider the part of the chain that was travelled between *d*_{i} and *d*_{i + 1}; we can arrange it in any valid way independently of any other parts of the chain, thus we consider all these parts separately. There also parts before *d*_{1} and after *d*_{n}, but it is fairly easy to analyze them: make them monotonously decreasing (respectively, increasing), as this maximizes the top point.

Without the loss of generality consider *d*_{i} = 0 and *d*_{i + 1} = *t* (they may be increased of decreased simultaneously without changing the answer), and *h*_{di} = *a*, *h*_{di + 1} = *b*. Clearly, in consistent data |*a* - *b*| ≤ *t*, so if this condition fails for a single pair of adjacent entries, we conclude the data is flawed.

If the condition holds, it is fairly easy to construct a valid way to move between the days under the |*h*_{i} - *h*_{i + 1}| ≤ 1 condition: increase or decrease the height while it differs from *b*, than stay on the same height. That does not make the optimal way, but at least we are sure that the data is not inconsistent.

How to construct the optimal arrangement? From the adjacent difference inequality if follows that for any *i* between 0 and *t* the inequalities *h*_{i} ≤ *a* + *i* and *h*_{i} ≤ *b* + (*t* - *i*) hold. Let *h*_{i} = *min*(*a* + *i*, *b* + (*t* - *i*)) on the [0; *t*] segment; clearly, every *h*_{i} accomodates the largest possible value, therefore the value of maximum is also the largest possible. It suffices to show that these *h*_{i} satisfy the difference condition. Basically, two cases should be considered: if for *h*_{i} = *a* + *i* and *h*_{i + 1} = *a* + *i* + 1, or *h*_{i} = *b* + (*t* - *i*) and *h*_{i + 1} = *b* + (*t* - *i* - 1), the statement is obvious. Else, *h*_{i} = *a* + *i* but *h*_{i} < *b* + (*t* - *i*) = *h*_{i + 1} + 1, and *h*_{i + 1} = *b* - (*t* - *i* - 1) but *h*_{i + 1} < *a* + (*i* + 1) = *h*_{i} + 1. Thus, |*h*_{i} - *h*_{i + 1}| < 1, and *h*_{i} = *h*_{i + 1}.

To find the maximum value of maximum height (I really struggle not to use 'maximum maximum') we may either use ternary search on the *h* function, or find the point where lines *a* + *i* and *b* + (*t* - *i*) intersect and try integer points besides the intersection. If we use this approach analytically, we arrive at the formula (*t* + *a* + *b*) / 2 (try to prove that yourself!).

**Sample solution**: 10973854

**Challenge (medium)**. Given the same data (that is, a subsequence *h*_{di} for a sequence *h*_{i}), determine how many (modulo a prime number) integer sequences of length *n* with the property |*h*_{i} - *h*_{i + 1}| ≤ 1 agree with the subsequence and have global maximum equal to *H*? Can you solve the problem in *O*(*n*^{2}) time? In time? *Maybe even faster?*

Instead of trying to find out where the piece may go, let's try to find out where it can *not* go. Initially mark all the moves as possible; if there is a field (*x*_{1}, *y*_{1}) containing a piece, and a field (*x*_{2}, *y*_{2}) not containing a piece and not being attacked, clearly a move (*x*_{2} - *x*_{1}, *y*_{2} - *y*_{1}) is not possible. Let us iterate over all pieces and over all non-attacked fields and mark the corresponding moves as impossible.

Suppose we let our piece make all the rest moves (that are not yet marked as impossible), and recreate the position with all the pieces in the same places. If a field was not attacked in the initial position, it will not be attacked in the newly-crafted position: indeed, we have carefully removed all the moves that could take a piece to this field. Thus, the only possible problem with the new position is that some field that was attacked before is not attacked now. But our set of moves is maximal in the sense that adding any other move to it will cause the position to be incorrect. Thus, if the new position doesn't coincide with the initial position, the reconstruction is impossible. Else, we have already obtained a correct set of moves. This solution has complexity of *O*(*n*^{4}) for iterating over all pieces and non-attacked fields. No optimizations were needed to make solution this pass.

**Sample solution**: 10973859

**Challenge (medium)**. Solve the same problem in time.

With such large constraints our only hope is the subtree dynamic programming. Let us analyze the situation and how the subtrees are involved.

Denote *w*(*v*) the number of leaves in the subtree of *v*. Suppose that a non-leaf vertex *v* has children *u*_{1}, ..., *u*_{k}, and the numbers to arrange in the leaves are 1, ..., *w*(*v*). We are not yet sure how to arrange the numbers but we assume for now that we know everything we need about the children's subtrees.

Okay, what is the maximal number we can achieve if the maximizing player moves first? Clearly, he will choose the subtree optimally for himself, and we are eager to help him. Thus, it makes sense to put all the maximal numbers in a single subtree; indeed, if any of the maximal numbers is not in the subtree where the first player will go, we swap it with some of the not-so-maximal numbers and make the situation even better. If we place *w*(*u*_{i}) maximal numbers (that is, *w*(*v*) - *w*(*u*_{i}) + 1, ..., *w*(*v*)) in the subtree of *w*(*u*_{i}), we must also arrange them optimally; this task is basically the same as arranging the numbers from 1 to *w*(*u*_{i}) in the subtree of *w*(*u*_{i}), but now the minimizing player goes first. Introduce the notation for the maximal possible result if the maximizing/minimizing (depending on the lower index) player starts. From the previous discussion we obtain . Thus, if we know for all children, the value of can be determined.

How does the situation change when the minimizing player goes first? Suppose that for each *i* we assign numbers *n*_{1, 1}, ..., *n*_{1, w(ui)} to the leaves of the subtree of *u*_{i} in some order; the numbers in the subtree of *u*_{i} will be arranged so that the result is maximal when the maximizing player starts in *u*_{i}. Suppose that numbers *n*_{i, j} are sorted by increasing of *j* for every *i*; the minimizing player will then choose the subtree *u*_{i} in such a way that is minimal. For every arrangement, the minimizing player can guarantee himself the result of at most . Indeed, if all the numbers are greater than *r*, all the numbers *n*_{i, j} for should also be greater than *r*; but there are numbers *n*_{i, j} that should be greater than *r*, while there are only *w*(*v*) - *r* possible numbers from 1 to *w*(*v*) to place; a contradiction (pigeonhole principle). On the other hand, the value of *r* is easily reachable: place all the numbers less than *r* as *n*_{i, j} with , and *r* as, say, *n*_{1, dpmax(u1)}; the first player will have to move to *u*_{1} to achieve *r*. Thus, .

The previous, rather formal argument can be intuitively restated as follows: suppose we put the numbers from 1 to *w*(*v*) in that order to different subtrees of *v*. Once a subtree of *u*_{i} contains *dp*_{max}(*u*_{i}) numbers, the minimizing player can go to *u*_{i} and grab the current result. It follows that we may safely put *dp*_{max}(*u*_{i}) - 1 numbers to the subtree of *u*(*i*) for each *i*, and the next number (exactly *r*) will be grabbed regardless of what we do (if we do not fail and let the minimizing player grab a smaller number).

That DP scheme makes for an *O*(*n*) solution, as processing the *k* children of each node is done in *O*(*k*) (provided their results are already there). As an easy exercise, think about how the optimal arrangement of number in the leaves can be constructed; try to make implementation as simple as possible.

**Sample solution**: 10973864

**Challenge (medium)**. Suppose that we are given numbers *n*, *a*, *b*, and we want to construct a tree with *n* leaves such that *dp*_{max}(*root*) = *a* and *dp*_{min}(*root*) = *b*. For which numbers *n*, *a*, *b* is this possible? (I'm sure you will like the answer for this one. =)) Can you propose an algorithm that constructs such a tree?

**The first approach**. For a given *k* and an element *v*, how do we count the number of children of *v* that violate the property? This is basically a range query 'how many numbers in the range are greater than *v*' (because, evidently, children of any element occupy a subsegment of the array); the answers for every *k* are exactly the sums of results for queries at all non-leaf vertices. Online data structures for this query type are rather involved; however, we may process the queries offline by decreasing *v*, with a structure that is able to support an array, change its elements and take sum over a range (e.g., Fenwick tree or segment tree). This can be done as follows: for every element of the initial array store 1 in the same place of the structure array if the element has already been processed, and 0 otherwise. Now, if we sum over the range for the element *v*, only processed elements will have impact on the sum, and the result of the query will be exactly the number of elements greater than *v*. After all the queries for *v*, we put 1 in the corresponding element so that queries for smaller elements would take it into account. That makes for an solution. Estimate *q*: notice that for a given *k* there are only non-leaf vertices, thus the total number of queries will be (harmonic sum estimation). To sum up, this solution works in time.

**Sample solution (first approach)**: 10973867

**The second approach**. Let us index the elements of the array starting from 0. It is easy to check that for a given *k* the parent of the element *a*_{v} is the element . One can show that there are only different elements that can be the parent of *a*_{v} for some *k*. Indeed, if , the index of the parent is less that , and all produce no more than different parents too. Moreover, each possible parent corresponds to a range of values of *k*. To show that, solve the equality for *k*. Transform: , *pk* ≤ *v* - 1 < (*p* + 1)*k*, , . For every *k* in the range above the property is either violated or not (that depends only on *a*_{v} and *a*_{p}); if it's violated we should add 1 to all the answers for *k*'s in the range. That can be done in *O*(1) offline using delta-encoding (storing differences between adjacent elements in the process and prefix-summing them in the end). There will be only queries to the delta array (as this is the number of different child-parent pairs for all *k*). This makes for a simple solution which barely uses any heavy algorithmic knowledge at all.

**Sample solution (second approach)**: 10973868

**Challenge 1 (medium)**. Denote *c*_{k} the minimal number of elements that should be changed (each to a value of your choice) so that the array becomes a valid *k*-ary heap. Can you find a single *c*_{k} (for a given *k*) in time? Can you find all *c*_{k} (for 1 ≤ *k* ≤ *n* - 1) at once in *O*(*n*^{2}) time? *Can you do better than these estimates?*

**Challenge 2 (hard)**. Solve the problem from Challenge 1 if an arbitrary rooted tree with numbers in vertices is given (that is, change the minimal number of elements so that no element is greater than its parent). Can you do it in *O*(*n*^{2})? In ? In ? (I'm pretty certain my approach should work, but I would be glad if anyone could check me on this one. That being said, I'm eagerly waiting for your comments.) *Not likely, but maybe you could do even better?*

First of all, we'll simplify the problem a bit. Note that after every command the values of *x* + *y* and *x* - *y* are altered by ± 1 independently. Suppose we have a one-dimensional problem: given a sequence of *x*'s and *t*'s, provide a looped program of length *l* with commands ± 1 which agrees with the data. If we are able to solve this problem for numbers *x*_{i} + *y*_{i} and *x*_{i} - *y*_{i} separately, we can combine the answers to obtain a correct program for the original problem; if one of the subproblems fails, no answer exists. (Most — if not all — participants who solved this problem during the contest did not use this trick and went straight ahead to the two-dimensional problem. While the idea is basically the same, I'm not going into details for their approach, but you can view the submitted codes of contestants for more info on this one.)

Ok, now to solve the one-dimensional problem. Let us change the command set from ± 1 to + 0 / + 1: set . If the division fails to produce an integer for some entry, we must conclude that the data is inconsistent (because *x*_{i} and *t*_{i} should have the same parity). Now it is clear to see that the operation - 1 becomes operation 0, and the operation + 1 stays as it is.

A program now is a string of length *l* that consists of 0's and 1's. Denote *s*_{i} the number of 1's among the first *i* commands, and *s* = *s*_{l} for simplicity. Evidently, an equation holds, because the full cycle is executed ⌊ *t*_{i} / *l*⌋ times, and after that more first commands. From this, we deduce .

Suppose that we know what *s* is equal to. Using this, we can compute all ; they are *fixed* from now on. One more important fixed value is *s*_{l} = *s*. In any correct program *s*_{i} ≤ *s*_{i + 1} ≤ *s*_{i} + 1, but not all values of *s*_{i} are known to us. When is it possible to fill out the rest of *s*_{i} to match a correct program? If *s*_{a} and *s*_{b} are adjacent entries that are fixed (that is, every *s*_{c} under *a* < *c* < *b* is not fixed), the inequality 0 ≤ *s*_{b} - *s*_{a} ≤ *b* - *a* must hold (*a* and *b* may coincide if for different *i* several values of coincide). Furthermore, if the inequality holds for every pair of adjacent fixed entries, a correct program can be restored easily: move over the fixed values, and place *s*_{b} - *s*_{a} 1's between positions *a* and *b* in any possible way, fill with 0's all the other positions in between.

The trouble is that we don't know *s* in advance. However, we know the positions and the order in which fixed values of *s*_{a} come! Sort them by non-decreasing of *a*. All fixed *s*_{a} can be expressed as linear functions of *s*; if we substitute these expressions in the 0 ≤ *s*_{b} - *s*_{a} ≤ *b* - *a*, from each pair of adjacent fixed values we obtain an inequality of general form 0 ≤ *p*·*s* + *q* ≤ *d*, where *p*, *q*, *d* are known values. If the obtained system of inequalities has a solution, we can get ourselves a valid *s* and restore the program as discussed above.

It suffices to notice that every inequality of the system has a set of solutions of general form *l* ≤ *s* ≤ *r* (if the set is not empty), where *l* and *r* should be calculated carefully depending on the sign of *p*. All the intervals should be intersected, and the resulting interval provides a range of valid values of *s*.

Overall, the solution works in , or even in *O*(*n* + *l*) if we use bucketing instead of sorting. Note that the *l* summand in the complexity is only there for the actual program reconstruction; if we were only to check the existence of a program, an *O*(*n*) solution would be possible.

**Sample solution**: 10973870

**Challenge (kinda hard)**. Under the same statement, how many (modulo a prime number) different programs agree with the given data? Assume that all elementary modulo operations (including division) take *O*(1) time. Can you solve this problem in *O*(*nl*)? In *O*(*n* + *l*)? *Maybe even better (in , for example?)*

The problem has several possible approaches.

**The first approach**. More popular one. Forget about *t* and *T* for a moment; we have to separate teachers into two groups so that no conflicting teachers are in the same group, and the number of students in each group can be chosen to satisfy all the teachers.

Consider a connected component via the edges which correspong to conflicting pairs. If the component is not bipartite, there is clearly no valid distribution. Else, the teachers in the component can be separated into two sets such that each set should be in the same group, and the groups for the sets should be different. The teachers in the same set will always go together in the same group, so we may as well make them into a single teacher whose interval is the intersection of all the intervals for the teachers we just compressed. Now, the graph is the set of disjoint edges (for simplicity, if a teacher does not conflict with anyone, connect him with a 'fake' teacher whose interval is [0;∞]).

Consider all possible distributions of students; they are given by a pair (*n*_{1}, *n*_{2}). Provided this distribution, in what cases a pair of conflicting teachers can be arranged correctly? If the teachers' segments are [*l*_{1}, *r*_{1}] and [*l*_{2}, *r*_{2}], either *l*_{1} ≤ *n*_{1} ≤ *r*_{1} and *l*_{2} ≤ *n*_{2} ≤ *r*_{2}, or *l*_{2} ≤ *n*_{1} ≤ *r*_{2} and *l*_{1} ≤ *n*_{2} ≤ *r*_{1} must hold. Consider a coordinate plane, where a point (*x*, *y*) corresponds to a possible distribution of students. For a pair of conflicting teachers the valid configurations lie in the union of two rectangles which are given by the inequalities above. Valid configurations that satisfy all pairs of teachers lie exactly in the intersection of all these figures. Thus, the problem transformed to a (kinda) geometrical one.

A classical approach to this kind of problems is to perform line-sweeping. Note that any 'union of two rectangles' figure (we'll shorten it to UOTR) is symmetrical with respect to the diagonal line *x* = *y*. It follows that for any *x* the intersection of the vertical line given by *x* with any UOTR is a subsegment of *y*'s. When *x* sweeps from left to right, for any UOTR there are *O*(1) events when a subsegment changes. Sort the events altogether and perform the sweeping while updating the sets of subsegments' left and right ends and the subsegments intersection (which is easy to find, given the sets). Once the intersection becomes non-empty, we obtain a pair (*x*, *y*) that satisfies all the pairs of teachers; to restore the distribution is now fairly easy (don't forget that every teacher may actually be a compressed set of teachers!).

Didn't we forget something? Right, there are bounds *t* and *T* to consider! Consider an adjacent set of events which occurs when *x* = *x*_{1} and *x* = *x*_{2} respectively. The intersection of subsegments for UOTRs obtained after the first event will stay the same while *x*_{1} ≤ *x* < *x*_{2}. Suppose the *y*'s subsegmen intersection is equal to [*l*;*r*]. If we stay within *x*_{1} ≤ *x* < *x*_{2}, for a satisfying pair of (*x*, *y*) the minimal value of *x* + *y* is equal to *x*_{1} + *l*, and the maximal value is *x*_{2} + *r* - 1. If this range does not intersect with [*t*;*T*], no answer is produced this turn. In the other case, choose *x* and *y* while satisfying all boundaries upon *x*, *y* and *x* + *y* (consider all cases the rectangle can intersect with a 45-angle diagonal strip). Thus, the requirement of *t* and *T* does not make our life much harder.

This solution can be implemented in using an efficient data structure like `std::set`

or any self-balancing BST for sets of subsegments' ends. The very same solution can be implemented in the flavour of *rectangles union problem* canonical solution: represent a query 'add 1 to all the points inside UORT' with queries 'add *x* to all the points inside a rectangle', and find a point with the value *m*.

**Sample solution (first approach)**: 10973887

**The second approach**. Less popular, and probably much more surprising.

Imagine that the values of *t* and *T* are small. Introduce the set of boolean variables *z*_{i, j} which correspond to the event '*n*_{i} does not exceed *j*' (*i* is either 1 or 2, *j* ranges from 0 to *T*). There are fairly obvious implication relations between them: . As *t* ≤ *n*_{1} + *n*_{2} ≤ *T*, we must also introduce implications (here *i*' is 1 or 2 not equal to *i*) because if *a* + *b* ≥ *t* and *a* ≤ *j*, *b* must be at least *t* - *j*, and for a similar reason. In this, *z*_{i, j} for *j* < 0 clearly must be considered automatically false, and *z*_{i, j} for *j* ≥ *T* must be considered automatically true (to avoid boundary fails).

The last thing to consider is the teachers. For every teacher introduce a binary variable *w*_{j} which corresponds to the event 'teacher *j* tutors the first group'. The implications and are pretty much self-explanating. A conflicting pair of teachers *j* and *k* is resolved in a straightforward way: , .

If a set of values for all the boolean variables described satisfies all the restrictions, a valid distribution can be restored explicitly: *n*_{1} and *n*_{2} are maximal so that *z*_{1, n1} and *z*_{2, n2} hold, and the teachers are distributed unequivocally by values of *w*_{j}. It suffices to notice that the boolean system is a 2-SAT instance, and can be solved in linear time. If we count carefully, we obtain that the whole solution has linear complexity as well: *O*(*n* + *m* + *T*).

Didn't we forget something? Right! The value of *T* may be too much to handle Ω(*T*) variables explicitly. To avoid that, one may notice that the set of possible values of *n*_{1} and *n*_{2} may be reduced to 0, *t*, *l*_{i}, *t* - *l*_{i}, *r*_{i}, *t* - *r*_{i}. We can prove that by starting from any valid values of *n*_{1} and *n*_{2} and trying to make them as small as possible; the listed values are the ones we may end up with. Thus, we can only use *O*(*n*) variables instead of Ω(*T*). The implications can be built similarily, but using lower/upper bound on the list of possible values instead of exact values (much care is advised!). Finally, this solution can be made to work in , with the logarithmic factor from all the sorting and lower/upperbounding.

**Sample solution (second approach)**: 10973881

**Challenge (easy, for a change)** Don't you think it's wrong that a group may be without a teacher altogether? Come up with an algorithm that finds a distribution that places at least one teacher in each group. The complexity should not become worse. *How about at least k teachers in each group?*

Whew, wasn't it a long run! I tried to be verbose and elaborate where it was possible, hope it was worth the wait. Let me know what you think of this write-up!

Tutorial of Codeforces Round #300

Hello, Codeforces!

On Sunday, April 26th at 19:00 MSK the 300'th regular Codeforces Round will take place.

I would like to congratulate all Codeforces members and administration on this remarkable milestone. The platform has grown hugely in size and quality since its foundation, has hosted lots of exciting competitions, and has been providing the opportunity to everyone to hone their problem solving and algorithmic mastery. For this we thank the Codeforces platform creator MikeMirzayanov and all the Codeforces crew. Keep up the incredible job, guys!

That being said, I'm excited to announce that the problems on the jubilee three-hundredth Codeforces Round will be set by me, Mikhail Tikhomirov (Endagorion). You may remember the past rounds with my problems: #99, #109, #265, #283, and (in part) #295. I thank the Codeforces problems coordinator Max Akhmedov (Zlobober) for helping me in preparing this round, and Maria Belova Delinur for translating the statements in English. Also, special gratitude to Vladislav Isenbaev (winger), Alex Fetisov (AlexFetisov) and Pavel Kunyavskiy (PavelKunyavskiy) for testing the problemset and help with preparation.

This round will be shared for both divisions and will last two hours and a half (as you can see at the Contests page). The round will feature several ( ≥ 6) problems, varying in difficulty and topics involved. I hope that everyone will find an interesting and satisfying problem just for themselves! The scoring will be announced later.

To add up to the excitement, there are 30 exclusive Codeforces T-shirts to compete for in this round! The top 15 participants will get their T-shirts right away; another 15 will be randomly distributed among those who place in the top 300. Even if you think your chances on being the very best are weak, there are still good odds you will get a treat! =)

That's it. Mark your calendars and come back to compete for the prizes and for the fun!

**UPD**: there will be **8** problems. The scoring is standard (i.e. not dynamic): **500-1000-1500-1500-2000-2500-3000-3000**.

**UPD2**. In order to choose people getting T-Shirts we will use the following python3.4 code that you can manually run in "custom invocation" tab on Codeforces. It uses an integer as a seed for random generator, this integer should be equal to the last submission number that happened during the contest.

import random
seed = int(input())
rnd = random.Random(seed)
# all contestants except top-15
contestants = list(range(16, 301))
rnd.shuffle(contestants)
tshirts = list(range(1, 16)) + contestants[:15]
for x in sorted(tshirts):
print(x)

**UPD3**: Thanks for participating!

The winners are:

The list of places getting the T-shirts are `1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 40 46 67 75 80 102 103 144 152 161 169 198 233 243 269`

. The lucky participants are as follows: bmerry, Egor, Petr, rng_58, scott_wu, TooSimple, eatmore, atetubou, qwerty787788, niyaznigmatul, gs12117, W4yneb0t, izrak, zxqfl, yeputons, kcm1700 & cubelover (sharing the 40-th place, so both get a T-shirt), piob, Leo_Yu, matrix & Nerevar (sharing the 75-th place), Haghani, ACube, DemiGuo, FerranAlet, Emarci15, hlwt, Salvare001, MiraculousCoder, FatalEagle, gchebanov & nwin (sharing the 243-rd place), and Solaris (please let me know about any mistakes). Congratulations!

**UPD4**: At long last, the editorial is up! Enjoy, and sorry for the waiting.

Announcement of Codeforces Round #300

Somehow I don't feel sleepy at all at 6am, which is kinda weird. I wonder if writing an editorial will help.

The standard trick is to use the linearity of expectation: for every substring count the probability that it consists of the same characters, and sums all these probabilities. There are *O*(*n*^{2}) substrings, which is a reasonable amount in the given limitations. However, iterating over all symbols in the substring yields *O*(*n*^{3}) solution, so we should optimize something.

My way was as follows: fix the beginning of the substring, and process all substrings with this beginning altogether. Count *q*_{c} — the probability that current substring consists only of characters *c*. If we append one symbol from the right, *q*_{c} changes in a simple way: if the symbol is a letter *x*, then all *q*_{c} with *c* ≠ *x* become zeros, while *q*_{x} does not change; else, if the symbol is question mark, every *q*_{c} gets multiplies by *p*_{c}. So, we process all substrings with fixed beginning in *O*(*mn*) (where *m* is the number of different symbols), for a *O*(*mn*^{2}) solution.

Do you have a more effective/simple solution for this problem?

When we open all the brackets, every number adds up with a plus or a minus sign by it. Which configurations are possible? It is not difficult to prove that all possible configurations are as follows: the first number is always a plus, the second is always a minus, while all other numbers with a plus sign form no more than two consecutive segments. So, we just have to find two subsegments of the array with the greatest total sum. There are lots of ways to do it in *O*(*n*), the most straightforward (IMO) being DP (how many elements are processed; the number of consecutive segments already closed; is a segment currently open). Simply recalculate the DP after every change in the array, for a solution of *O*(*n*^{2}) complexity.

What if there is only one entrance in the tree? The problem becomes a classic one: count the number of topological orderings of rooted tree with edges directed from the root. There is a simple subtree DP solution; also, a closed formula is available: , where *n* is the total number of vertices, *w*(*v*) is the number of vertices in the subtree of *v*.

Now, two entrances *s*_{1} and *s*_{2} are present. Consider vertices that lie on the path connecting *s*_{1} and *s*_{2} in a tree; every vertex of the path can be associated with a subtree consisting of vertices not on the path. The last vertex to cover will be either *s*_{1} or *s*_{2} (WLOG, assume it's *s*_{1}), the second-to-last will be either *s*_{2} or the neighbour of *s*_{1} in the path, etc. The observation is that at any moment there is a consecutive subsegment of the *s*_{1}-*s*_{2} path which is covered.

Count *dp*_{l, r} — the number of ways to cover the subsegment from *l*-th to *r*-th vertex in the path with all the hanging subtrees. The number of ways such that the *l*-th vertex is the last to cover is , where *ord*_{l} is the number of topological orderings of the subtree of *l*-th vertex (which can be calculated as described above), *t*_{l} is the size of this subtree, and *T*_{l, r} is the total number of vertices in the subtrees of *l*-th, ..., *r*-th vertices. The intuition behind this formula is that we independently deal with the segment [*l* + 1;*r*] and the *l*-th subtree, and the last vertex is always the *l*-th vertex of the path. The number of ways that cover *r*-th vertex in the last place is obtained symmetrically; *dp*_{l, r} is simply the sum of those two quantities. The base of DP is clearly *dp*_{l, l} = *ord*_{l}.

Clearly, this subsegment DP is calculated in *O*(*n*^{2}), with all the preliminaries being simple DFS'es and combinatorial primitives which also can be done in *O*(*n*^{2}).

We would like to thank the testers of this round's and Winter Computer Camp olympiad's problems: alger95, thefacetakt, adamant, dragonic, Who179, ASverdlov.

Make sure to comment if you find any mistakes.

**UPD**: I've just remembered to put up the usual challenges for the problems. So, here they go.

Idea: Endagorion

Preparation: Endagorion

To check that every letter is present in the string we can just make a boolean array of size 26 and for every letter set the corresponding variable to TRUE. In the end check that there are 26 TRUEs. That is an *O*(*n*) solution. Also don't forget to change all letters to lowercase (or all to uppercase).

To make all the letters lowercase, one could use standard functions, like `tolower`

in Python. Also, it is known that the letters from `a`

to `z`

have consecutive ASCII numbers, as well as `A`

to `Z`

; an ASCII number of symbol is `ord(c)`

in most languages. So, to get the number of a lowercase letter in the alphabet one can use `ord(c) - ord('a')`

in most languages, or simply `c - 'a'`

in C++ or C (because a `char`

in C/C++ can be treated as a number); to check if a letter is lowercase, the inequality `ord('a') <= ord(c) && ord(c) <= ord('z')`

should be checked.

**Challenge**: how many pangrams of length *n* are there? Strings that differ only in capitalization of some letters are considered distinct. Can you find the answer modulo some prime *p* in linear time?

Idea: Endagorion

Preparation: Endagorion

The simplest solution is simply doing a breadth-first search. Construct a graph with numbers as vertices and edges leading from one number to another if an operation can be made to change one number to the other. We may note that it is never reasonable to make the number larger than 2*m*, so under provided limitations the graph will contain at most 2·10^{4} vertices and 4·10^{4} edges, and the BFS should work real fast.

There is, however, an even faster solution. The problem can be reversed as follows: we should get the number *n* starting from *m* using the operations "add 1 to the number" and "divide the number by 2 if it is even".

Suppose that at some point we perform two operations of type 1 and then one operation of type 2; but in this case one operation of type 2 and one operation of type 1 would lead to the same result, and the sequence would contain less operations then before. That reasoning implies that in an optimal answer more than one consecutive operation of type 1 is possible only if no operations of type 2 follow, that is, the only situation where it makes sense is when *n* is smaller than *m* and we just need to make it large enough. Under this constraint, there is the only correct sequence of moves: if *n* is smaller than *m*, we just add 1 until they become equal; else we divide *n* by 2 if it is even, or add 1 and then divide by 2 if it is odd. The length of this sequence can be found in .

**Challenge**: suppose we have a generalized problem: we want to get *n* starting from *m* using two operations "subtract *a*" and "multiply by *b*". Generalize the solution to find the minimal number of moves to get from *n* to *m* in time if *a* and *b* are coprime. Can you do it if *a* and *b* may have common divisors greater than 1?

520C - DNA Alignment/521A - DNA Alignment

Idea: Endagorion

Preparation: Endagorion

What is ρ(*s*, *t*) equal to? For every character of *s* and every character of *t* there is a unique cyclic shift of *t* that superposes these characters (indeed, after 0, ..., *n* - 1 shifts the character in *t* occupies different positions, and one of them matches the one of the character of *s*); therefore, there exist *n* cyclic shifts of *s* and *t* that superpose these characters (the situation is symmetrical for every position of the character of *s*). It follows that the input in ρ from a single character *t*_{i} is equal to *n* × (the number of characters in *s* equal to *t*_{i}). Therefore, ρ(*s*, *t*) is maximal when every character of *t* occurs the maximal possible number of times in *s*. Simply count the number of occurences for every type of characters; the answer is *K*^{n}, where *K* is the number of character types that occur in *s* most frequently. This is an *O*(*n*) solution.

**Challenge**: we know that ρ_{max}(*s*) = *n*^{2}·*C*(*s*), where *C*(*s*) is the maximal number that any character occurs in *s*. How many strings *s* of length *n* with characters from an alphabet of size *k* have *C*(*s*) = *m*? Can you find an *O*(*kn*^{2}) solution? An solution? An solution? Maybe even better? (Hint: the modulo should be an *appropriately chosen* prime number for a fast solution =)).

Idea: savinov

Preparation: savinov, sokian, zemen

Basically, the first player should maximize the lexicographical order of numbers, and the second player should minimize it. Thus, at every move the first player should choose the largest available number, and the second should choose the minimal one.

First of all, how do we check if the cube can be removed? It is impossible only if there is some cube "supported" by it (i.e., it has coordinates (*x* - 1, *y* + 1), (*x*, *y* + 1), (*x* + 1, *y* + 1)) such that our cube is the only one supporting it. This can be checked explicitly. The large coordinates' limitations do not allow us to store a simply array for that, so we should use an associative array, like a `set`

in C++.

Now we should find the maximal/minimal number that can be removed. A simple linear search won't work fast enough, so we store another data structure containing all numbers available to remove; the structure should allow inserting, erasing and finding global minimum/maximum, so the `set`

C++ structure fits again.

When we've made our move, some cubes may have become available or unavailable to remove. However, there is an *O*(1) amount of cubes we have to recheck and possibly insert/erase from our structure: the cubes (*x* ± 1, *y*) and (*x* ± 2, *y*) may have become unavailable because some higher cube has become dangerous (that is, there is a single cube supporting it), and some of the cubes (*x* - 1, *y* - 1), (*x*, *y* - 1) and (*x* + 1, *y* - 1) may have become available because our cube was the only dangerous cube that it has been supporting. Anyway, a simple recheck for these cubes will handle all the cases.

This solution is if using the appropriate data structure.

**Challenge** (inspired by questions from jk_qq and AmrMahmoud): suppose that the players put the numbers from right to left, that is, from the least significant digit to the most significant. The first player still wants to maximize the resulting number, and the second wants to minimize it. If the original rules of taking cubes apply, finding the optimal strategy for the players seems intractable. Try to solve this problem in the case where all the cubes are stacked in several independent towers; that is, a cube may only be taken from the top of any tower.

520E - Pluses everywhere/521C - Pluses everywhere

Idea: Endagorion

Preparation: gchebanov, DPR-pavlin

Consider some way of placing all the pluses, and a single digit *d*_{i} (digits in the string are numbered starting from 0 from left to right). This digit gives input of *d*_{i}·10^{l} to the total sum, where *l* is the distance to the nearest plus from the right, or to the end of string if there are no pluses there. If we sum up these quantities for all digits and all ways of placing the pluses, we will obtain the answer.

For a given digit *d*_{i} and some fixed *l*, how many ways are there to place the pluses? First of all, consider the case when the part containing the digit *d*_{i} is not last, that is, *i* + *l* < *n* - 1. There are *n* - 1 gaps to place pluses in total; the constraint about *d*_{i} and the distance *l* means that after digits *d*_{i}, ..., *d*_{i + l - 1} there are no pluses, while after the digit *d*_{i + l} there should be a plus. That is, the string should look as follows:

Here a dot means a gap without a plus, and a question mark means that it's not important whether there is a plus or not. So, out of *n* - 1 possible gaps there are *l* + 1 gaps which states are defined, and there is one plus used in these gaps. That means that the other (*n* - 1) - (*l* + 1) = *n* - *l* - 2 gaps may contain *k* - 1 pluses in any possible way; that is, the number of such placements is . A similar reasoning implies that if the digit *d*_{i} is in the last part, that is, *i* + *l* = *n* - 1, the number of placements is .

To sum up, the total answer is equal to

Let us transform the sum:

To compute these sums, we will need to know all powers of 10 up to *n*-th (modulo 10^{9} + 7), along with the binomial coefficients. To compute the binomials, recall that , so it is enough to know all the numbers *k*! for *k* upto *n*, along with their modular inverses. Also we should use the prefix sums of *d*_{i}, that is, the array . The rest is simple evaluation of the above sums.

The total complexity is , because the common algorithms for modular inverses (that is, Ferma's little theorem exponentiation or solving a diophantine equation using the Euclid's algorithm) have theoritcal worst-case complexity of . However, one can utilize a neat trick for finding modular inverses for first *n* consecutive numbers in linear time for a total complexity of *O*(*n*); for the description of the method refer to this comment by Kaban-5 (not sure why it has a negative rating, I found this quite insightful; maybe anyone can give a proper source for this method?).

**Challenge**: now we want to find the sum of all expressions that are made by placing *k* pluses with *a* ≤ *k* ≤ *b*; that is, we want to find the sum of the answers for the original problem with *k* = *a*, ..., *b*; here *a* and *b* can be any integers with 0 ≤ *a* ≤ *b* ≤ *n* - 1. There is an obvious *O*(*n*^{2}) solution: just find the answers for all *k* separately. Can you find a linear solution?

Idea: Endagorion

Preparation: gchebanov

Suppose the only type of upgrades we have is multiplication. It doesn't even matter for the answer which particular skill we are going to multiply, so we just choose several upgrades with greatest values of *b*_{i}.

Now we have additions as well; set multiplications aside for a moment. It is clear that for every skill we should choose several largest additions (maybe none). Let us sort the additions for every skill by non-increasing; now we should choose several first upgrades for each type. Now, for some skill the (non-increasing) sorted row of *b*'s is *b*_{1}, ..., *b*_{l}, and the initial value of the skill is *a*. Now, as we have decided to take some prefix of *b*'s, we know that if we take the upgrade *b*_{i}, the value changes from *a* + *b*_{1} + ... + *b*_{i - 1} to *a* + *b*_{1} + ... + *b*_{i - 1} + *b*_{i}. That is, the ratio by which the value (and the whole product of values) is going to be multiplied by is the fraction . Now, with that ratio determined unambigiously for each addition upgrade, every addition has actually become a multiplication. =) So we have to compute the ratios for all additions (that is, we sort *b*'s for each skill separately and find the fractions), and then sort the multiplications and additions altogether by the ratio they affect the whole product with. Clearly, all multiplications should be used after all the additions are done; that is, to choose which upgrades we use we should do the ratio sorting, but the order of actual using of upgrades is: first do all the additions, then do all the multiplications.

Finally, let's deal with the assignment upgrades. Clearly, for each skill at most one assignment upgrade should be used, and if it used, it should the assignment upgrade with the largest *b* among all assignments for this skill. Also, if the assignment is used, it should be used before all the additions and multiplications for this skill. So, for each skill we should simply determine whether we use the largest assignment for this skill or not. However, if we use the assignment, the ratios for the additions of current skill become invalid as the starting value of *a* is altered.

To deal with this problem, imagine that we have first chosen some addition upgrades, and now we have to choose whether we use the assignment upgrade or not. If we do, the value of the skill changes from *a* + *b*_{1} + ... + *b*_{k} to *b* + *b*_{1} + ... + *b*_{k}. That is, the assignment here behaves pretty much the same way as the addition of *b* - *a*. The only difference is that once we have chosen to use the assignment, we should put it before all the additions.

That is, all largest assigments for each skill should be made into additions of *b* - *a* and processed along with all the other additions, which are, as we already know, going to become multiplications in the end. =)

Finally, the problem is reduced to sorting the ratios for all upgrades. Let us estimate the numbers in the fractions. The ratio for a multiplication is an integer up to 10^{6}; the ratio for an addition is a fraction of general form . As *k* can be up to 10^{5}, and *b*_{i} is up to 10^{6}, the numerator and denominator of such fraction can go up to 10^{11}. To compare fractions and we should compare the products *ad* and *bc*, which can go up to 10^{22} by our estimates. That, unfortunately, overflows built-in integer types in most languages. However, this problem can be solved by subtracting 1 from all ratios (which clearly does not change the order of ratios), so that the additions' ratios will look like . Now, the numerator is up to 10^{6}, the products in the comparison are up to 10^{17}, which fits in 64-bit integer type in any language.

**Challenge**: suppose that you have to compare two fractions and , where *a*, *b*, *c*, *d* may be up to 10^{18}. What way would you use to do that? Can you find a simple solution that does not involve long arithmetics, floating-point number or magic built-in integer types tricks (but may perform a non-constant number of operations)?

Idea: Endagorion

Preparation: Endagorion

We have to find two vertices in an undirected graph such that there exist three vertex- and edge-independent paths between them. This could easily be a flow problem if not for the large constraints.

First of all, we can notice that all the paths between vertices should lie in the same biconnected component of the graph. Indeed, for every simple cycle all of its edges should lie in the same biconnected component, and the three-paths system is a union of cycles. Thus, we can find all the biconnected components of the graph and try to solve the problem for each of them independently. The computing of biconnected components can be done in linear time; a neat algorithm for doing this is described in the Wikipedia article by the link above.

Now, we have a biconnected component and the same problem as before. First of all, find any cycle in this component (with a simple DFS); the only case of a biconnected component that does not contain a cycle is a single edge, which is of no interest. Suppose that no vertex of this cycle has an adjacent edge that doesn't lie in the cycle; this means the cycle is not connected to anything else in the component, so the component is this cycle itself, in which case there is clearly no solution.

Otherwise, find a vertex *v* with an adjacent edge *e* that doesn't lie in the cycle (denote it *c*). If we can find a path *p* starting with *e* that arrives at a cycle vertex *u* (different from *v*), then we can find three vertex-distinct paths between *v* and *u*: one path is *p*, and two others are halves of the initial cycle. To find *p*, start a DFS from the edge *e* that halts when it arrives to vertex of *c* (that is different from *v*) and recovers all the paths.

What if we find that no appropriate path *p* exists? Denote *C* the component traversed by the latter DFS. The DFS did not find any path between vertices of *C*\ {*v*} and *c*\ {*v*}, therefore every such path should pass through *v*. That means that upon deletion of *v*, the component *C*\ {*v*} becomes separated from all vertices of *c*\ {*v*}, which contradicts with the assumption that the component was biconnected. That reasoning proves that the DFS starting from *e* will always find the path *p* and find the answer if only a biconnected component was not a cycle nor a single edge.

Finally, we obtain that the only case when the answer is non-existent is when all the biconnected components are single edges or simple cycles, that is, the graph is a union of disconnected cactuses. Otherwise, a couple of DFS are sure to find three vertex-disjoint paths. This yields an *O*(*n* + *m*) solution; a few logarithmic factors for simplification here and there are also allowed.

**Challenge**: how many graphs *G* on *n* labeled vertices exist such that there exist two vertices of *G* connected by three disjoint paths? (Hint: we have already shown that it suffices to count the number of disjoint unions of *cacti*.) Find the answer modulo 10^{9} + 7. Can you come up with any polynomial-time solution? An *O*(*n*^{3}) solution? Maybe even better?

Tutorial of Codeforces Round #295 (Div. 2)

Tutorial of Codeforces Round #295 (Div. 1)

Hello, Codeforces!

On March, 2nd at 10:00 MSK Codeforces Round #295 will be held in both divisions.

The round will be held at the same time with Winter Computer Camp olympiad, the problemsets will be highly similar. The problems are by me (Endagorion) and Evgeny Savinov (savinov). The problems are prepared by members of the Winter Computer Camp technical committee: Georgy Chebanov (gchebanov), Filipp Rukhovich (DPR-pavlin), Alexander Mashrabov (map), Sergey Kiyan (sokian), Konstantin Semenov (zemen), Kinan Alsarmini (Sarkin).

Big thanks to Max Akhmedov (Zlobober) for his help with preparing the problems, Maria Belova (Delinur) for translating the statements in English, and Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon systems.

The scoring is standard for both divisions: **500-1000-1500-2000-2500**.

**Please note** that the Winter Computing Camp olympiad is scheduled to finish later than the Codeforces round. Thus, we ask you not to discuss the problems and solutions in the comments until 14:10 MSK. Also, viewing of other participants' solutions will be closed until that time. The editorial will also be published later.

**UPD**: you are free to discuss the problems now.

**UPD2**: the editorial is finally up! Sorry for the delay.

Also, grats to our Div.1 winners:

Special respect goes to Petr and rng_58 for solving the hardest problem E!

Announcement of Codeforces Round #295 (Div. 2)

Announcement of Codeforces Round #295 (Div. 1)

Each problem comes with a challenge — a bonus task somehow related to the problem; you may tackle at the challenges for fun and practice, also feel free to discuss them at the comments. =)

For every option of removing an element we run through the remaining elements and find the maximal difference between adjacent ones; print the smallest found answer. The solution has complexity *O*(*n*^{2}). It can be noticed that after removing an element the difficulty either stays the same or becomes equal to the difference between the neighbours of the removed element (whatever is larger); thus, the difficulty for every option of removing an element can be found in *O*(1), for the total complexity of *O*(*n*). Any of these solutions (or even less efficient ones) could pass the tests.

**Challenge**: suppose we now have to remove exactly *k* arbitrary elements (but the first and the last elements have to stay in their places). How small the maximal difference between adjacent elements can become? Solve this problem assuming the limitations are as follows: 1 ≤ *k* ≤ *n* - 2, *n* ≤ 10^{5}, *a*_{i} ≤ 10^{9}.

We observe that the order of operations is not important: we may first perform all the shifts, and after that all the additions. Note that after *n* shifts the sequence returns to its original state, therefore it is sufficient to consider only the options with less than *n* shifts. Also, after 10 times of adding 1 to all digits the sequence does not change; we may consider only options with less than 10 additions. Thus, there are overall 10*n* reasonable options for performing the operations; for every option perform the operations and find the smallest answer among all the options. As performing the operations for every option and comparing two answers to choose the best takes *O*(*n*) operations, this solution performs about 10*n*^{2} elementary operations. The multiple of 10 can be get rid of, if we note that after all shifts are made the best choice is to make the first digit equal to zero, and this leaves us but a single option for the number of additions. However, implementing this optimization is not necessary to get accepted.

**Challenge**: can you solve the problem in time? in *O*(*n*) time?

496C - Removing Columns/497A - Removing Columns

Let's look at the first column of the table. If its letters are not sorted alphabetically, then in any valid choice of removing some columns it has to be removed. However, if its letters are sorted, then for every valid choice that has this column removed it can be restored back to the table; it is clear that the new choice is valid (that is, the rows of the new table are sorted lexicographically) and the answer (that is, the number of removed columns) has just became smaller.

Consider all columns from left to right. We have already chosen which columns to remove among all the columns to the left of the current one; if leaving the current column in place breaks the lexicographical order of rows, then we have to remove it; otherwise, we may leave it in place to no harm. Arguing in the way of the previous paragraph we can prove that this greedy method yields an optimal (moreover, the only optimal) solution. The complexity is *O*(*n*^{2}).

**Challenge**: compute how many (say, modulo 10^{9} + 7) *n* × *m* tables are there for which the answer for this problem is *k*? The more efficient solution you come up with, the better.

496D - Tennis Game/497B - Tennis Game

Choose some *t*; now emulate how the match will go, ensure that the record is valid for this *t* and by the way find the corresponding value of *s*. Print all valid options for *s* and *t*. This solution works in *O*(*n*^{2}) time, which is not good enough, but we will try to optimize it.

Suppose the current set if finished and we have processed *k* serves by now. Let us process the next set as follows: find *t*-th 1 and *t*-th 2 after position *k*. If *t*-th 1 occurs earlier, then the first player wins the set, and the set concludes right after the *t*-th 1; the other case is handled symmetrically. If the match is not over yet, and in the rest of the record there are no *t* ones nor *t* twos, then the record is clearly invalid. This way, every single set in the record can be processed in time using binary search, or *O*(1) time using precomputed arrays of positions for each player.

Now observe that for any *t* a match of *n* serves can not contain more than *n* / *t* sets, as each set contains at least *t* serves. If we sum up the upper limits for the number of sets for each *t*, we obtain the total upper limit for the number of sets we may need to process: (which is the famous harmonic sum). Using one of the approaches discussed above, one obtains a solution with complexity of or ; each of these solutions fits the limit nicely.

Obviously, for every *t* there is no more than one valid choice for *s*; however, maybe a bit unexpected, for a given *s* there may exist more than one valid choice of *t*. The first test where this takes place is pretest 12. The statement requires that the pairs are printed lexicographically ordered; it is possible to make a mistake here and print the pairs with equal *s* by descending *t* (if we fill the array by increasing *t* and then simply reverse the array).

**Challenge**: while preparing this problem I discovered that it's quite hard to find a test such that the number of pairs in the answer is large; in the actual tests the maximal number is 128, which is the number of divisors of the number 83160. Can you beat this record? If you have a test with *n* ≤ 10^{5} that has larger number of pairs in the answer, feel free to brag in the comments; also don't hesitate to share any insights on how one could bound the maximal number analytically.

496E - Distributing Parts /497C - Distributing Parts

Sort all the parts and actors altogether by increasing lower bounds (if equal, actors precede parts); process all the enitities in this order. We maintain a set of actors which have already occured in the order; if we meet an entry for an actor, add it to the set. If we currently process a part, we have to assign it to an actor; from the current set of actors we have to choose one such that his *d*_{i} ≥ *b*_{j} (the *c*_{i} ≤ *a*_{j} constraint is provided by the fact that the *i*-th actor has occured earlier than the *j*-th part); if there are no such actors in the set, no answer can be obtained; if there are several actors satisftying this requirement, we should choose one with minimal *d*_{i} (intuitively, he will be less useful in the future). Assign the chosen actor with the current part and decrement his *k*_{i}; if *k*_{i} is now zero, the actor can not be used anymore, thus we remove him from the set.

To fit the limits we should implement the set of current actors as some efficient data structure (e.g., an std::set or a treap). The resulting complexity is .

**Challenge**: suppose that now there are *q*_{j} copies of the *j*-th part (1 ≤ *q*_{j} ≤ 10^{9}), and each copy must be separately assigned with an actor in a valid way. Can you solve this new problem with all the old constraints (as the actual distribution now has too much entries, it is sufficient to check whether an answer exists)?

When a collision happens, a vertex of one polygon lands on a side of the other polygon. Consider a reference system such that the polygon *A* is not moving. In this system the polygon *B* preserves its orientation (that is, does not rotate), and each of its vertices moves on some circle. Intersect all the circles for vertices of *B* with all the sides of *A*; if any of them intersect, then some vertex of *B* collides with a side of *A*. Symmetrically, take a reference system associated with *B* and check whether some vertex of *A* collides with a side of *B*. The constraints for the points' coordinates are small enough for a solution with absolute precision to be possible (using built-in integer types).

Another approach (which is, in fact, basically the same) is such: suppose there is a collision in a reference system associated with *A*. Then the following equality for vectors holds: *x* + *y* = *z*; here *z* is a vector that starts at *P* and ends somewhere on the bound of *A*, *x* is a vector that starts at *Q* and ends somewhere on the bound of *B*, *y* is a vector that starts at *P* and ends somewhere on the circle centered at *P* that passes through *Q*. Rewrite the equality as *y* = *z* - *x*; now observe that the set of all possible values of *z* - *x* forms the Minkowski sum of *A* and reflection of *B* (up to some shift), and the set of all possible values of *y* is a circle with known parameters. The Minkowski sum can be represented as a union of *nm* parallelograms, each of which is the Minkowski sum of a pair of sides of different polygons; finally, intersect all parallelograms with the circle.

Both solutions have complexity *O*(*nm*). As noted above, it is possible to solve the problem using integer arithemetics (that is, with absolute precision); however, the fact that the points' coordinates are small lets most of the solutions with floating point arithmetics pass. It was tempting to write an approximate numerical solution; we struggled hard not to let such solutions pass, and eventually none of them did. =)

Many participants had troubles with pretest 8. It looks as follows (the left spiral revolves around the left point, and the right spiral revolves around the right point):

**Challenge**: suppose we want a solution that uses floating point arithmetics to fail. In order to do that, we want to construct a test such that the polygons don't collide but pass really close to each other. How small a (positive) distance we can achieve, given the same constraints for the number of points and the points' coordinates?

Consider some string; how does one count the number of its distinct subsequences? Let us append symbols to the string consequently and each time count the number of subsequences that were not present before. Let's append a symbol *c* to a string *s*; in the string *s* + *c* there are as many subsequences that end in *c* as there were subsequences in *s* overall. Add all these subsequences to the number of subsequnces of *s*; now each subsequence is counted once, except for the subsequences that end in *c* but were already present in *s* before; these are counted twice. Thus, the total number of subsequences in the new string is twice the total number of subsequences in the old string minus the number of subsequences in the old string which end in *c*.

This leads us to the following solution: for each symbol *c* store how many subsequences end in *c*, denote *cnt*_{c}. Append symbol *c*; now *cnt*_{c} becomes equal to the sum of all *cnt*'s plus one (for the empty subsequence), and all the other *cnt*'s do not change.

For example, consider the first few symbols of the Thue-Morse sequence:

ε — (0, 0)

0 — (

**0 + 0 + 1 = 1**, 0)01 — (1,

**1 + 0 + 1 = 2**)011 — (1,

**1 + 2 + 1 = 4**)0110 — (

**1 + 4 + 1 = 6**, 4)...

Let us put the values of *cnt* in the coordinates of a vector, and also append a coordinate which is always equal to 1. It is now clear that appending a symbol to the string alters the vector as a multiplication by some matrix. Let us assign a matrix for each symbol, and also for each string as a product of matrices for the symbols of the strings in that order.

Now, consider the prefix of the sequence *a*_{i} of length *k*^{m}. Divide it into *k* parts of length *k*^{m - 1}; *x*-th (0-based) of these parts can be obtained from the 0-th one by adding *x* modulo *k* to all elements of the part. Let us count the matrices (see above) for the prefixes of length *k*^{m}, and also for all strings that are obtained by adding *x* to all of the prefixes' elements; denote such matrix *A*_{m, x}.

It is easy to see that if *m* > 0, then . This formula allows us to count *A*_{m, x} for all and all *x* from 0 to *k* - 1 in time. Now, upon having all *A*_{m, x} we can multiply some of them in the right order to obtain the matrix for the prefix of the sequence *a*_{i} of length *n*.

Unfortunately, this is not quite enough as the solution doesn't fit the time limit yet. Here is one way to speed up sufficiently: note that the product in the formula can be divided as shown: *A*_{m - 1, x}... *A*_{m - 1, k - 1} × *A*_{m - 1, 0}... *A*_{m - 1, x - 1} (if *x* = 0, take the second part to be empty). Count all the "prefixes" and "suffixes" products of the set *A*_{m, x}: *P*_{m, x} = *A*_{m, 0}... *A*_{m, x - 1}, *S*_{m, x} = *A*_{m, x}... *A*_{m, k - 1}. Now *A*_{m, x} = *S*_{m - 1, x}*P*_{m - 1, x}. Thus, the computation of *A*_{m, x} for all *x* and a given *m* can be done as computing all *P*_{m - 1, x}, *S*_{m - 1, x} using *O*(*k*) matrix multiplications, and each *A*_{m, x} is now can be found using one matrix multiplication. Finally, the solution now works in time, which fits the limits by a margin.

**Challenge**: solve the problem for *k* ≤ 100.

Tutorial of Codeforces Round #283 (Div. 2)

Hi, Codeforces.

Today, on December 17 at 19:30 MSK regular, 283-rd Codeforces round will take place. Problems are authored by me, Mikhail Tikhomirov. Maxim Akhmedov (Zlobober) helped me with discussing and preparing the problemset, Maria Belova (Delinur) translated problem statements in English, and Georgy Chebanov (gchebanov), Alexander Mashrabov (map) and Niyaz Nigmatullin (niyaznigmatul) tested the round and helped us with finding bugs and mistakes; let's give them a round of applause!

The round will be for both divisions. The scoring is standard (not dynamic); score distribution is as follows:

**Div. 1: 750-1250-1250-2000-2500**

**Div. 2: 500-1000-1750-2250-2250**

This is going to be my fourth round at Codeforces. I really hope it will go as good as three before it. =) Wish you all the best of luck!

**UPD**: the round is over, thanks for participating!

Grats to the winners:

**Div. 1**:

**Div. 2**:

Editorial is here ( **UPD**: now in English!).

Announcement of Codeforces Round #283 (Div. 2)

Announcement of Codeforces Round #283 (Div. 1)

A new long challenge is up at Al Zimmerman's Programming Contests -- Delacorte Numbers. Find the description here. Neat prizes are announced for two best participants. You must register in order to compete.

The problem seems really cool, so I encourage you to try it, especially if you like TopCoder Marathon Matches or something like that.

I'll upload my example solutions and will post links to them as soon as it becomes possible.

Some of the problems editorials contain an additional challenge which is apparently harder to comprehend than the original problem. Feel free to share and discuss your ideas in the comments. =)

If we add 1 to a number, its binary representation changes in a simple way: all the least significant 1's change to 0's, and the single following 0 changes to 1. It suffices to find the length of largest suffix which contains only 1's, suppose its length is *l*. Then the answer is *l* + 1 except for the case when all the string consists of 1, when the answer is *l*.

It is amusing that div1E problem is concerned with addition of 1 to a binary integer as well. =)

Optimal strategy is as follows: for every segment of consecutive 1's open the first letter in segment, scroll until the last letter in segment, if there are more unread letters left, return to list.

It is easy to show that we can not do any better: observe the moment we read the last letter from some segment of consecutive 1's. There are no adjacent unread letters now, so we either have to scroll to some read letter or return to list of letters, either way we make an operation which does not result in reading an unread letter, so every segment (except for the last) must yield at least one such operation.

If string *s* contains a non-trivial palindromic substring *w*, then it must contain palindromic substring of length 2 or 3 (for instance, center of *w*). Therefore the string is tolerable iff no adjacent symbols or symbols at distance 1 are equal.

Now for the lexicographically next tolerable string *t*. *t* is greater than *s*, so they have common prefix of some size (maybe zero) and the next symbol is greater in *t* than in *s*. This symbol should be as right as possible to obtain minimal possible *t*. For some position *i* we can try to increment *s*_{i} and ensure it's not equal to *s*_{i - 1} or *s*_{i - 2}. If we find some way to do this, the suffix can always be filled correctly if only *p* ≥ 3, as at most two symbols are forbidden at every moment. Every symbol from suffix should be as small as possible not to make conflicts. So, a greedy procedure or some kind of clever brute-force can be implemented to solve the problem in *O*(*n*). Cases *p* = 1 or 2 are easy, as only strings of length at most 1, and at most 2 respectively fit.

This is an application on general approach to generate next lexicographical something: try to increment rightmost position so that suffix can be filled up in some way, then fill the suffix in least possible way.

As pointed out in Russian discussion, this problem is a simplified version of the problem from some previous round: 196D - The Next Good String. We were not aware of this and apologize for the misfortune. Luckily, no copied solutions from that problem were spotted. If you enjoyed this simple version, you may want to try the harder one know. =)

There are several ways to solve this problem. We'll describe the most straightforward one: we can generate all possible permutations of coordinates of every point and for every combination check whether given point configuration form a cube. However, number of configurations can go up to (3!)^{8} > 10^{6}, so checking should work quite fast.

One way to check if the points form a cube is such: find minimal distance between all pairs of points, it should be equal to the side length *l*. Every vertex should have exactly three other points at distance *l*, and all three edges should be pairwise perpendicular. If these condition are met at every point, then configuration is a cube as there is no way to construct another configuration with these properties. This procedure performs roughly 8^{2} operations for every check, which is fast enough. There are even more efficient ways of cube checking exploiting various properties of cube.

There are various optimizations to ensure you fit into time limit. For instance, applying the same permutation to coordinates of all points keeps every property of the cube, therefore we can fix order of coordinates for one point and permute all other. This single trick speeds up the algorithm 6 times, which allows some less efficient programs to be accepted.

**A challenge**: apparently, checking may be done as follows: find the length side *l*, then count number of pairs on distance *l*, , . A cube must contain exactly 12 pairs of first kind, 12 pairs of second kind and 4 pairs of third kind. Can you prove that this condition is sufficient for configuration to form a cube? Is it true if we allow points to have non-integer coordinates? Can you propose an even easier algorithm for checking?

It is quite diffcult to store the whole string after each query as its length grows exponentially and queries may change it dramatically. The good advice is: if you can't come up with a solution for a problem, try solving it from the other end. =)

Suppose we know for some sequence of queries that digit *d* will turn into string *t*_{d} for every digit. Then string *s* = *d*_{1}... *d*_{n} will turn into *t*_{d1} + ... + *t*_{dn} (+ for concatenation). Denote *v*(*s*) numeric value of *s*. Then *v*(*s*) can be expressed as *v*(*t*_{dn}) + 10^{|dn|}(*v*(*t*_{dn - 1}) + 10^{|dn - 1|}(...)). So *v*(*s*) can be computed if we know *m*_{d} = *v*(*t*_{d}) and *s*_{d} = 10^{|td|} for all *d*. As we need answer modulo *P* = 10^{9} + 7 we can store these numbers modulo *P*.

Now prepend some new query *d*_{i} → *t*_{i} to given sequence. How will *m*_{d} and *s*_{d} change? Clearly, for all *d* ≠ *d*_{i} these numbers won't change, and for *d*_{i} they can be computed according to the rule above. This recounting is done in *O*(|*t*_{i}|) time. After adding all queries, find answer for *s* using the same procedure in *O*(|*s*|) time. Finally, our time complexity is . The code for this problem pretty much consists of the above formula, so implementation is as easy as it gets once you grasp the idea. =)

Optimized simple solutions which just replaced substrings could manage to pass pretests. Sorry for that.

**A challenge**: this problem has a natural modification when you have to give an answer after each query. Using algorithm described above it can be solved offline in *O*(*n*^{2}) time. Can we do better than this? What if we are limited to answer online?

This problem required some skill at probabilities handling, but other than that it's quite simple too.

Denote number of earned coins as *X*, and number of earned coins from selling items of type *i* as *X*_{i}. Clearly *X* = *X*_{1} + ... + *X*_{k}, and *EX* = *EX*_{1} + ... + *EX*_{k} (here *EX* is expectation of *X*). As all types have equal probability of appearance, all *X*_{i} are equal, so *EX* = *kEX*_{1}. Now to find *EX*_{1}.

If we look only at the items of one type, say, 1, items generation looks like this: with probability we get nothing, and with probability we get out item with level distributed as usual. Denote *d*_{n, t} expectation of earned money after killing *n* monsters if we have an item of level *t* at the start. Clearly, *d*_{0, t} = 0 (we have no opportunity to earn any money), and , which is equal to = . To get the answer note that *EX*_{1} = *d*_{n, 1}. The sad note is that this DP has Ω(*n*^{2}) states, which is too much for .

Maybe if we cut off some extremely-low-probability cases we can do better? For instance, it is clear that probability of upgrading an item descreases with its level, so apparently it does not get very high. We know that expected number of tries before first happening of event with probability *p* in a series of similar independent events is 1 / *p*. Therefore, expected number of monsters we have to kill to get item of level *T* is . So, in common case our level can get up to about , which does not exceed 500 in our limitations. We would want to set such bound *B* that ignoring cases with *t* > *B* would not influence our answer too much. That can be done with rigorous bounding of variance of *T* and applying some bounding theorem, or with an empirical method: if we increase the bound and the answer doesn't visibly change, then this bound is fine. It turns out *B* ≥ 700 is good enough for achieving demanded precision. Thus solution with complexity is obtained (here we assert that , and constant *C* is buried in the big O).

**A challenge**: suppose we have the same rules of killing monsters and obtaining items, but now we are free to choose whether to sell a new item or an old one. We act so that to maximize our number of coins in the end. What is the expected number of coins if we act optimally?

Now it is sometimes more profitable to sell a powerful item, but sometimes it isn't. How fast a solution can you come up with?

This seems to be a simple graph exercise, but the problem is with enormous weights of paths which we need to count and compare with absolute precision to get Dijkstra working. How do we do that?

The fact that every edge weight is a power of two gives an idea that we can store binary representation of path value as it doesn't change much after appending one edge. However, storing representations explicitly for all vertices is too costly: the total number of 1's in them can reach Ω(*nd*) (*d* is for maximal *x*_{i}), which doesn't fit into memory even with bit compression woodoo magic.

An advanced data structure is needed here which is efficient in both time and memory. The good choice is a persistent segment tree storing bit representation. Persistent segment tree is pretty much like the usual segment tree, except that when we want to change the state of some node we instead create a new node with links to children of old node. This way we have some sort of ''version control'' over tree: every old node is present and available for requests as its subtree can never change. Moreover, all queries are still processed in time, but can create up to new nodes.

What queries do we need? Adding 2^{x} to binary number can be implemented as finding nearest most significant 0 to *x*-th bit, setting it to 1 and assigning 0's to all the positions in between. Usual segment tree with lazy propagation can do it, so persistent tree is able to do it as well.

Comparing two numbers can be done as follows: find the most singificant bit which differs in two numbers, then number with 0 in this bit is smaller; if no bits differ, then numbers are clearly equal. That can be done in if we store hashes of some sort in every node and perform a parallel binary search on both trees. Time and memory limits were very generous so you could store as many different hashes as you wanted to avoid collisions.

That concludes the general idea. Now we use this implementation of numbers as a black-box for Dijkstra algorithm. Every operation on numbers is now slowed by a factor of , so our solution has complexity. However, great caution is needed to achieve a practical solution.

First of all, in clueless implementation comparison of two "numbers" may require additional memory as we must perform "push" operation as we descend. memory is too much to fit even in our generous ML. There are plenty of ways to avoid this, for instance, if we want to push the value from node to children, we actually know that the whole segment consists of equal values and can answer the query right away.

I would like to describe a clever trick which optimizes both time and memory greatly and also simplifies implementation. It allows to get rid of lazy propagation completely. Here it comes: initially build two trees containing only 0's and only 1's respectively. Now suppose we want to assign some value (0, for instance) on a segment and some tree node completely lies inside of query segment. Instead of creating a new node with a propagation mark, we can replace the node with corresponding node from tree filled with 0. This way only new nodes are created on every query (which is impossible to achieve with any kind of propagation which would require at least ), and also nodes need to store less information and become lighter this way. Also, no "push" procedure is required now.

No challenges for this problem as it is challenging enough itself. =) Implementing this problem is a great exercise for anyone who wants to become familiar with complicated structures and their applications, so solving it in the archive is advisable.

That's pretty much it. If there are still questions, you may ask them in the comments. Thanks for reading!

Tutorial of Codeforces Round #265 (Div. 1)

Tutorial of Codeforces Round #265 (Div. 2)

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/20/2018 11:39:06 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|