Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

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

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 168 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 154 |

10 | McDic | 153 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Technocup 2020 - Elimination Round 2

**We are aware about the issues with rating in Division 2. MikeMirzayanov is on it and will fix everything soon.**

Congrats to the winners!

Technocup edition:

Div. 1 round:

Div. 2 round:

Analysis can be found here (if it doesn't show the analysis, just wait for a little bit).

**Scoring distribution**:

elimination round: 500-750+750-1500-2000-2750-3250-3750

division 2: 500-750+750-1500-2000-2750-3250

division 1: 500-1000-1750-2250-2750-3250Hi Codeforces!

This weekend, on Oct/26/2019 14:05 (Moscow time) we will hold Codeforces Round 596. It is based on problems of Technocup 2020 Elimination Round 2 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fit into this category, please register at Technocup 2020 website and take part in the Elimination Round 2.

Div. 1 and Div.2 editions are **open and rated for everyone.** As usual the statements will be provided **in English and in Russian**. Register and enjoy the contests!

Have fun!

Announcement of Technocup 2020 - Elimination Round 2

A few people expressed interest in me answering some questions regarding competitive programming/problemsetting/related stuff. Since I have a bit of free time during these holidays, let's try this. I'll choose a few most interesting questions from comments under this post and try to answer them in a single video.

Ideally a question should not be to broad ("please give us some tips and tricks" is probably too broad) and possible to answer within a few minutes. I probably won't answer a question if it was asked a lot of times here on CF/quora/someplace else. Let's go!

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Technocup 2019 - Elimination Round 4

On Oct/04/2018 10:05 (Moscow time), the Codeforces Round #513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2) will start. This is a special round for the Hello Barcelona Programming Bootcamp, in collaboration with Moscow Workshops ICPC. **It is rated for all participants, everybody can register on it regardless of a rating.**

Hello Barcelona Programming Bootcamp is sponsored by VTB and Indeed Tokyo, with the addition of team sponsors Phaze Ventures, Spark Labs and REMY Robotics.

VTB, the largest international bank based in Eastern Europe, continues to be an official partner of the Hello Programming Bootcamp series, adding further quality to the 3rd edition of the Hello Barcelona Programming Bootcamp by bringing their own participants, as well as by supporting top teams from around the world.

Indeed Tokyo is Japan's branch of the #1 employment website in the world, giving job seekers free access to millions of jobs from thousands of company websites and job boards. As they sponsor for the second year in a row, Indeed continues to offer the best job opportunities to the boot camp participants.

Wish good luck to all the participants!

There will be **8** problems, common for both division. Score distribution: `500 750 1250 1500 1750 2250 2750 3000`

.

The problems are prepared by me, Arterm and GlebsHP, with assistance from 300iq, ifsmirnov and gritukan. Have fun!

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of VK Cup 2018 - Round 3

Hello everyone! Today, on March 13 at 9pm MSK the second qualification round of Yandex.Algorithm 2018 tournament will take place. You can get to the contest page from the Algorithm site.

The problems are by me, Mikhail Tikhomirov. I am grateful to Gleb GlebsHP Evstropov for his help with problems preparation, and also ifsmirnov, halyavin, kuzmichev_dima, scorpion for testing the problems.

Good luck, see you at the competition!

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!

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)

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2020 14:01:26 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|