### Zlobober's blog

By Zlobober, 7 weeks ago, translation, ,

Hi everybody!

Today at 21:00 UTC there will be Yandex.Algorithm 2017 Marathon Round.

You have two days for creating an efficient solution for the optimizational problem we have prepared for you. You may submit for the whole 48 hours of the contest.

This round is the first one among the four elimination rounds. Don't miss!

UPD Testing on final testset will happen tomorrow. Thank you for participation!

•
• +69
•

By Zlobober, 2 months ago, translation, ,

Hi,

Midnight tonight (UTC +3) starts the Yandex.Algorithm 2017 Qualification Round. Round lasts for two days in a virtual mode. The contest itself is 100 minutes long. You may start your participation in any moment of time between 21:00 UTC of Friday and 20:59 UTC of Sunday, inclusive.

In order to participate in a competition, you have to complete your registration. It will remain open for everybody until the end of the qualification round.

Those who already successfully submitted at least one problem in a warm-up round are already qualified to the elimination round of the competition. For everybody else in order to be qualified it is necessary to successfully submit at least one problem in a qualification round.

The link to the contest will appear on the site of a competition shortly before the round start time.

### Enter the contest!

Let us remind you that discussion of problem statements and solutions is prohibited until 22:40 UTC of Sunday (the latest possible contest end time for a participant). After that you may discuss problems and solutions in comments of this post or the editorial that will appear after the end of competition.

Good luck!

UPD: There is about 6 hours left to register and participate. Don't miss!

•
• +170
•

By Zlobober, 2 months ago, translation, ,

Problemset was formed by Oleg snarknews Khristenko.

### Problem A. Arithmetics Problem

In this problem your task was to implement exactly what is mentioned in this statement — iterate over all integers starting from 1 looking for the integer that is not a divisor of n and output it. Despite the fact n may be pretty large, this works really fast because in the constraints of the problem the answer is no more than 23 (least common multiplier of all integers between 1 and 23 is 5354228880 that is already bigger than n).

This was one of the simplest problem of the contest, but still, many contestants were hurrying too much and got WA 4 on the first minutes of the contest because they were iterating up to n, but not to infinity. Such a solution doesn't work for n = 1 and n = 2. What a pity it must be to make such a bug when submitting the problem blindly :)

Solution (py2)

### Problem B. Building a Quadrilateral

As well as the problem A, this problem was pretty easy. You had to remember the criteria of a quadrilateral being circumscribed: quadrilateral is circumscribed if and only if sums of its opposite sides are equal. So, the correct solution looks like: consider all three possibilities to divide four input numbers into two pairs (ai, aj) and (ak, al) and check that ai + aj = ak + al. In particular, there is no need to manually check that these four segments may even be combined into any quadrilateral because this immediately follows from the equation above.

Solution (py2)

### Problem C. Cyclops and Lenses

This is a greedy problem. Let's say that cyclops form a pair if they wear lenses from the same lense pair. Obviously, we want to maximize the number of cyclop pairs.

Consider a cyclop with smallest li, let this value be x. Obviously, it may be paired only with cyclop with either the same value of lj = x, with lj = x + 1, or with lj = x + 2. Let's present a sketch of a proof of the following fact. It is true that cyclop i should be paired with a cyclop with minimum lj among the remaining ones, lj - li ≤ 2.

Let's prove that if we have a cyclop with lj = x, then in some optimum answer cyclop i will form a pair with cyclop j.

If cyclop i is unpaired then simply form a pair of (i, j). This doesn't change the number of pairs or increases it by 1.

If i is already paired with some cyclop k (lk - li ≤ 2), and cyclop j is paired with cyclop t, it is always correct to repair them as follows: i with j and k with t.

You may similarly prove the general statement.

So, we got a simple greedy algorithm (much simpler than its strict proof!): we iterate over cyclops in an ascending order of their li and try to pair each cyclop with a following one if it is possible. In case of failure we buy a pair of lenses only for i-th cyclop and move to the next cyclop, otherwise we buy a pair of lenses for two of them and move forward. This solution works in time of sorting all the integers in the input.

Solution (py2)

### Problem D. Two transformations

First of all, replace each number in the input with its remainder modulo 2. Consider the special case of n = 1 manually.

Note that we have n - 2 operations, such that all of them look like inverting three adjacent elements except the two special operations that look like inverting first two or last two elements.

Obviously, the order of operation applying doesn't matter, so, each operation should be applied no more than once. Suppose that we are trying to make all number even, i.e. zeroes. Consider two cases: either we use the operation of inverting first two elements or not. If we decided to use it, invert x1 and x2.

Now all operations are of the form "invert all numbers xi, xi + 1, xi + 2 (in case it exists)" over all i between 1 and n - 1. Note that it is now uniquely determined if we are going to use each next operation: indeed, if x1 = 1, then we will definitely use the first operation, otherwise we won't. Invert x1, x2, x3 if needed, then, by looking on x2 we uniquely determine if we need to use the second operation, and so on.

In such manner we will make all elements of the sequence except, possibly, last one, be equal to zero. If the last element is not zero, then the decision we made at the beginning (about using operation over x1 and x2) was wrong, and it is impossible to achieve the desired situation in it. Otherwise, since we performed uniquely on each step, we also know the minimum number of operations required for the case we fixed at the beginning.

Find the overall answer as the minimum of answers over those two cases.

Solve similarly for making all numbers odd. The complexity of a presented solution is O(n).

Solution (с++)

### Problem E. Points and Circles

This problem allows two approaches. One is to implement exactly what is required in the statement, namely: you fix three white points i, j and k, check that they are not collinear, build their circumference and explicitly count all the points inside it. Such a solution runs in time of O(w3r) and should be implemented carefully (in particular, it's good idea to consider only triplets (i, j, k) such that i < j < k, reducing the solution space by factor of about 6). Also, it is a good knowledge how to effectively check the point for belonging to a circle that uses only integral arithmetics of 4-th order int respect to the magnitude of input coordinates. It may be shown that the point p = (px, py) lies inside the circumference of points a = (ax, ay), b = (bx, by), c = (cx, cy) if and only if the sign of determinant

is same as the sign of determinant

Geometric interpretation

Such a solution requires only the integral calculations, it is absolutely precise and pretty efficient.

This problem also allows a solution in time of using the geometric inversion transformation, but we will not discuss it since it's running time is about the same as the running time of a solution above.

Solution (с++, O(n^4))
Solution (с++, O(n^3 log n))

### Problem F. Cable management

This problem may be reduced to a minimum cost problem.

We will try to build a network, such that each path from source to sink corresponds to some possible scenario of a certain patchcord usage. Recall that each patchcord appears at some moment of time (requiring cn money from us), after that it periodically uses on some days i, breaks, and after that it must either be repaired by a company (in this case it moves to the day i + tf in cost of cf), or be repaired by Byteasar (in this case it moves to the day i + ts in cost of cs), or it may finally be thrown away up to the end of conference.

Let's interpret it in the following manner: consider the network that has the source s, the sink t, and also n pairs of vertices (1 + , 1 - ), (2 + , 2 - ), ... (n + , n - ) corresponding to each of the day of the conference. The idea behind assigning each day to two vertices will be clarified later.

Let there be an edge from source s to the vertex i -  of cost cn and capacity . Unit flow through this edge corresponds to a single bought patchcord.

Let there be an edge from vertex i +  to the vertex i -  of capacity ri and cost  - A where A — is some positive amount. The unit flow through such an edge corresponds to a single patchcord used in day i. Let's call such edges important.

Hence, all patchcords getting to the vertices of kind i -  are broken patchcords that require repairing.

Let there be an edge from vertex i -  to the sink t of capacity and cost 0. Unit flow through this edge corresponds to throwing out one patchcord.

Let there be an edge from vertex i -  to vertex (i + tf) +  of capacity and cost cf. Unit flow through such an edge corresponds to repairing of one patchcord using the company.

Similarly, let there be an edge from vertex i -  to the vertex (i + ts) +  of capacity and cost cs. Unit flow through such an edge corresponds to one patchcord repaired by Byteasar.

Finally, let there be an edge from vertex i +  to the vertex (i + 1) +  of capacity and cost 0 Unit flow through such an edge corresponds to an unbroken patchcord that was not used during the day i.

Any feasible flow in such a network corresponds to some set of patchcords and a strategy of their usage, but this set of patchcord may not be satisfying the requirements for the amount of patchcords per each day. We are interested only in those flows that saturate all the important edges.

Let's use a standard trick -- let's find the minimum cost flow, assigning all important edges a very small negative capacity beforehand. In the other words, let A be equal to a very large positive number. Then the final cost of a flow will be equal to  - A·satcnt + opcost where satcnt is the number of saturated important edges, and opcost is a cost of buying/repairing all the broken patchcords.

Let's find the flow of minimum cost in this network (note that it is not the same as the maximum flow of minimum cost). It's easy to see that such a flow maximizes the number of saturated important edges, and in case of a tie it minimizes the total expenses in a chosen plan.

So, we have a solution that has the running time of running a min-cost-flow algorithm in a network without negative cycles. Algorithm of repeated finding the shortest augmenting path using Ford-Bellman's algorithm works without any issues in constraints of the problem.

Solution (с++)

•
• +54
•

By Zlobober, 2 months ago, translation, ,

Hi,

Today at 13:00 UTC there will be a Warmup Round of Yandex.Algorithm 2017. This is a great possibility for you to get familiar with TCM/Time contest format, and also to pass to the elimination round of the competition by successfully submitting at least one problem.

In order to participate in the competition, you have to register, the registration will remain open for the next week.

The link to the round will appear on the site of the competition shortly before the start of the round.

Good luck!

### Enter the contest!

UPD: Round is over, thanks for the participation! Congratulations to four participants who successfully solved all problems:

All participants with at least one successful submission pass to the elimination round of the competition.

UPD2: Contest editorial.

•
• +76
•

By Zlobober, 3 months ago, translation, ,

We are announcing the annual Yandex.Algorithm 2017 championship! This is a great opportunity to compete with the strongest programmers of the world, win a fancy T-shirt, visit Yandex office or even receive some serious money prize.

•
• +296
•

By Zlobober, 8 months ago, translation, ,

I'm sorry for a delay with publishing the editorial.

## 731A - Night at the Museum

Problem author: egor-belikov, developer: timgaripov

In this problem you have to implement exactly what is written in the statement, i. e. you should find minimum number of rotations from letter `a` to the first letter in the input, then to the second one and so on. The only useful knowledge that may simplify the solution is that the distance between points x and y on the circle of length l (26 in our case) is min(|x - y|, l - |x - y|).

This solution works in O(|s|), and, of course, fits in time limit.

## 731B - Coupons and Discounts

Problem author: olympiad jury, developer: platypus179

In a correct answer we may guarantee that for any two consecutive days we use no more than one coupon for bying pizzas in these days. Indeed, if we have two coupons for buying pizzas in days i and i + 1, replace these coupons for two discounts, one for each of the days i and i + 1.

Consider the first day. According to the fact above, we may uniquely find the number of coupons for buying pizzas in 1 and 2 days we are going to use: it's either 0, if there is going to be an even number of pizzas in the first day, or 1 otherwise. The remaining pizzas in the first day will be bought by using discounts. If we use 1 coupon, then we may subtract 1 from the number of pizzas in the second day, and in both cases consider the second day and repeat the same actions.

If at some moment we have the odd number of pizzas and we don't need any pizzas in the following day, then it is impossible to buy all pizzas using only coupons and discounts, and we may output "`NO`". If it didn't happen, then we were able to buy everything using only coupons and discounts.

Such a solution works in O(n).

Question: Prove that the answer is "`YES`" if and only if any maximal contiguous segment without zeroes in the input sequence has the even sum.

## 731C - Socks

Problem author: egor-belikov, developer: wilwell

When solving this problem, it is convenient to use graph interpretation of the problem. Consider the graph, whose vertices correspond to the socks and edges connect those socks that Arseniy wears on some day. By the statement, we have to make that any two vertices connected by an edge have the same color. It actually means that any connected component should share the same color.

For each connected component let's find out which color should we choose for it. In order to recolor the minimum possible number of vertices, we should leave the maximum number of vertices with their original color. It means that the optimum color is the color shared by the most number of vertices in this connected component.

So, we have the following solution: consider all connected components, in each component choose the most popular color and add the difference between the component size and the number of vertices of this color. In order to find the most popular color you may, for example, write all colors in an array, sort it and find the longest contiguous segment of colors.

Such a solution works in .

Question: How to implement this solution so that it works in O(n + m)?

## 731D - 80-th Level Archeology

Problem author: olympiad jury, developer: Flyrise

Denote as x the number of alphabet cyclic shifts we will perform. Our goal is to formulate the statement of lexicographical order in terms of x.

Note that x may be considered as an integer between 0 and c - 1, i. e., as a residue modulo c. Let's also consider all characters as values between 0 до c - 1 as we may subtract 1 from the value of each character.

Consider two consecutive words in the given list. There are two possibilities corresponding two cases in the definition of lexicographical order:

The first case is when there exists such a position that these words differ in this position and coincide before this position. Suppose that first word has value of a on this position, and second word has the value of b. Then these words will follow in lexicographical order if and only if . It's easy to see that if we consider all residues modulo c as a circle, then this inequality defines an arc of possible x's on this circle. So, this pair of contiguous words produces the following statement "x belongs to some arc on the circle".

The second case is when there is no such a position, i. e. one word is a prefix of another. If the first word is a prefix of second one then these words always follow in lexicographical order irrespective to the choice of x. In the other case (second word is a proper prefix of the first word) we can't do anything with these to words since they will never follow in a lexicographical order, so we should print  - 1.

Now we have to find a point on the circle belonging to the given set of arcs. Suppose we have k arcs. Consider a line segment from 0 to c - 1 instead of a circle; each arc will transform to either one or two its subsegments.

Now we have to find out if there exists a point covered by exactly k segments. It may be done in different ways, for example you may add 1 on each of this segment by using some data structure, or you may add 1 to the left endpoint of each segment and  - 1 to the point after the right endpoint of each segment, and consider prefix sums (an off-line way to handle range addition queries). Or you may write down all endpoints of all segments, sort them by a coordinate and iterate over them from left to right, keeping the number of open segments. If at some moment you have exactly k open segments, then the answer is "`YES`".

## 731E - Funny Game

Problem author: _meshanya_, developer: ipavlov

First of all, comment on such type of games. In CS the game where two players are willing to maximize the difference between their own score and the score of their opponent is called a "zero-sum game". A useful knowledge is that problems for such a kind of games are usually solved using dynamic programming.

Note that at any moment the first sticker contains the sum of numbers on some prefix of an original sequence. This means that the state of a game is defined by a single number i: the length of an original sequence prefix that were summed into a single number.

Let's make two observations. First of all, for any state i the turn that current player will perform doesn't depend on scores of both players. Indeed, at any moment we may forget about the scores of both players since they add the constant factor to the resulting score difference, so we may virtually discard both players current scores. So, all we need to know about state i is what difference there will be between the current player score and his opponent score if the game would have started from the state i with zero scores.

Second observation is that the turn chosen by a player from the state i and the final difference of scores at the end does not depend from which player is currently making a turn (Petr or Gennady), i. e. the game is symmetric.

Denote as D[i] the difference between the first player score and the second player score if the game would have started from the state i with zero scores.

It is a convenient way to think about this game as if there were no separate scores of two players, but only a single balance value (difference) between them, and the first player is adding some numbers to the balance at his turn аnd second player subtracts some numbers from the balance. In such formulation D[i] is a balance change at the end of the game if the current player is willing to maximize it and he is currently in the state i. The answer for a problem will be, as one can see, D[1]. Note that if the current player would be willing to minimize balance, then the final balance change from the state i would be  - D[i] because the game is symmetric.

Let's calculate all D[i] using dynamic programming. At the end of the game, i. e. in the state n the value D[n] is equal to zero because the players won't be making any turns, and so the balance won't change.

Consider some state i. Suppose current player will take all the stickers up to the j-th (here j-th means the index in the original sequence). In such case he will change balance by S[j] (where S[j] is the sum of first j numbers in an original sequence), and game will move to the state j. After that his opponent will change the balance by  - D[j] (note that the balance change value is added with an opposite sign since the opponent will be playing from this state).

So, the final balance change when making such a turn will be S[j] - D[j]. In the DP definition we play for a player that is willing to maximize the balance, so .

Such a formula produces a solution in O(n2), but one may find that that it's enough to keep the maximum value of S[j] - D[j] on suffix j > i, recalculating it in O(1) when moving from i to i - 1. So, we have the solution that works in O(n).

Question: Which data type should be used for D[i] (and for the answer, in particular)?

## 731F - Video Cards

Problem author: olympiad jury, developer: gritukan

First observation is that if we fix the leading video card power x, we may take all the video cards of power at least x, as each of them brings the positive power value. So, we may sort all the cards in the ascending power order and then we will always choose some suffix of cards in such an order.

The final total power equals to . Note that under the summation there is a number that is divisible by x and that is no larger than 200 000 at the same time. It means that there are no more than different terms in this sum. Let's calculate the value of a sum spending the operations proportional to the number of different terms in it.

To do it we need to find out for each of the values x, 2x, 3x, ..., how many video cards will have exactly such power at the end. It's easy: final power kx corresponds to those video cards, which originally had the power between kx and (k + 1)x - 1. Their number can be found out in O(1) if we build an array C[i] storing the number of video cards of each power and calculate prefix sums on it.

It means that we got a solution that performs about operations. It's useful to know that the sum inside brackets is called a harmonic series, and that its sum is very close to the natural logarithm of the number of terms (up to a constant factor in limit).

It means that we got a solution in complexity of where m is the maximum power of a single video card.

Question: One may try to submit a solution assuming that the optimum power is always one of the first, let's say, 100 unique video cards in an ascending power order. How to build a test where the optimum power lies between 1/4 and 3/4 of a sorted power list, i. e. a counter-test for such a solution?

•
• +63
•

By Zlobober, 8 months ago, translation, ,

Hi everybody!

Tomorrow at 09:35 UTC there will be Codeforces Round #376 that is dedicated for the second division. At the same time there will be a Moscow School Team Olympiad, and, as a nice tradition, we bring you a CodeForces round based on its problems. Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants, but, as usual, we invite first division to participate unofficially in this round.

Problems were prepared by timgaripov, platypus179, wilwell, Flyrise, ipavlov and gritukan under my control. We would like to thank members of jury of the Team Olympiad: Endagorion, Helen Andreeva and GlebsHP, who also works as a coordinator from the CodeForces side. Also we are very grateful to MikeMirzayanov for a Polygon system that makes problem preparation and coordination of many involved people much simpler, and for a great CodeForces community that we are all part of.

We suggest you 6 problems for 2 hours. Good luck!

UPD The contest is over, results are final, thanks for participating! The editorial will be published later

UPD2 I'm sorry for an editorial delay. It's finally available here.

Congratulations to contest winners:

•
• +226
•

By Zlobober, 11 months ago, translation, ,

UPD2: Tomorrow (July 31st, Sunday) at UTC 10:00 there will be an online mirror of Yandex.Algorithm final round.

Everybody are invited to participate! You may discuss problems in comments after the contest ends.

UPD3: The online mirror has finished! Congratulations to ImBarD aka Vercingetorix for taking the first place.

Problem editorial

===================================================

Hi everybody!

We're glad to remind you that tomorrow, July 29th, at 9:00 AM UTC there will be the Final Round of Yandex.Algorithm 2016 in Minsk. List of finalists and elimination stage results are available on Yandex.Algorithm website.

You can watch follow the news on final round at Yandex.Algorithm website. Want to solve final round problems? On Sunday, July 31st, at 10:00 AM UTC there will be a mirror of the competition. Everybody can participate in it, solve the same problems as finalists and try his or her best on the finals' problemset.

The final round has been prepared by authors of previous stages of Yandex.Algorithm: Endagorion, Romka, Chmel_Tolstiy, GlebsHP, snarknews, Gassa and your humble servant. We believe that problems are various and interesting.

In this post after the cut I'll write some comments about what happens in the contest trying not to spoil any important details (we don't want to provde help or to ruin contest for any of the participants, isn't it?).

See you tomorrow!

UPD:

Congratulations to the winners!

1. Egor winning 300 thousands of rubles.
2. W4yneb0t winning 150 thousands of rubles.
3. rng_58 winning 90 thousands of rubles.

Final results are available here. The competition is finished, everybody are invited to participate an online mirror on Sunday!

•
• +189
•

By Zlobober, history, 12 months ago, translation, ,

Unfortunately Codeforces fails to show formulas in an editorial and I can't even press on "Preview" button :( While it doesn't work as intended, I put a bit ugly pdf-version of an editorial here. Unfortunately without model solution sources yet.

Russian editorial

English editorial

•
• +35
•

By Zlobober, 12 months ago, ,

Hi everybody!

I'm glad to invite you to the Yandex Algorithm Round 2 that will happen tomorrow at 21:00 Moscow Time. This round is prepared by me with a great help of GlebsHP. I want to say thanks to Chmel_Tolstiy, snarknews and Gassa for their support during the preparation and to all of the Yandex developers that tested this round.

Good luck and have fun!

Link to the contest will be posted here as soon as I manage to find it by myself :)

UPD: the link to the contest is located here: https://contest.yandex.com/algorithm2016/contest/2540/enter/

UPD2: Thanks everybody for the participation, I hope you enjoyed the round! Results will be available shortly. I'd like to publish an editorial, but it fails to compile on Codeforces and I'm trying to fix this issue.

UPD3: Congratulations to winners:

The preliminary pdf-version of an editorial is posted: http://codeforces.com/blog/entry/45354. Continuing the nice tradition of providing an editorial with questions related to the problems, I invite you to think about them/

•
• +188
•

By Zlobober, history, 14 months ago, ,

Hi everybody! FYI, 1st Qualification Round of RCC starts in less than an hour. I still don't see any kind of announcement on CF, so let it be here.

Good luck!

•
• +52
•

By Zlobober, history, 15 months ago, translation, ,

Opencup: GP of Baltics has just finished. We are curious, what are the normal solutions for A, B and F?

•
• +44
•

By Zlobober, 16 months ago, translation, ,

Hi everybody!

Glad to tell you that tomorrow on 9:05 UTC there will be Codeforces Round #345. The round is formed of the first day of X Moscow Open Olympiad problemset with several additional problems created for this round. This round is brought to you by the scientific committee of Moscow Programming Olympiads controlled by GlebsHP, romanandreev and your humble servant, and also with a great help of fcspartakm who helped us make a complete problemset of our problems.

The round will be conducted under the standard Codeforces rules, you will be given 5 problems for 2 hours. Yes, this round is rated :)

Note that because of holding the main onsite round system testing and upsolving will be available no earlier than 12:35 UTC. Also we would like to ask you to not discuss problems in comments during the time between the end of the round and the end of the onsite competition. All comments with discussions will be removed and the most active violators will be punished. Thanks for your understanding.

UPD Sorry, the round start was moved to 9:25 UTC. It is not easy to run onsite round and Codeforces Round simultaneously!

UPD2 You may discuss the solutions! System testing will be run shortly.

UPD3 The editorial has finally appeared: http://codeforces.com/blog/entry/43677 Sorry for the delay!

•
• +443
•

By Zlobober, history, 16 months ago, ,

Hacker Cup Final round is starting in 5 minutes. List of finalists: http://codeforces.com/blog/entry/23177

You can (probably) find the standings somewhere at http://facebook.com/hackercup

•
• +97
•

By Zlobober, history, 17 months ago, ,

Today (January 30th) at 10:00 AM PST / 21:00 MSK there will be the last online round for FHC. Don't miss the round!

As you remember, top-25 contestants will go to the onsite round in London.

Good luck to everybody!

UPD: UP! The round is in 30 minutes.

•
• +124
•

By Zlobober, 17 months ago, ,

Tomorrow (January 23rd) at 10:00 AM PST / 21:00 MSK there will be a second round of Facebook Hacker Cup. Don't miss!

I still don't know how to get to the dashboard from the official page (http://facebook.com/hackercup) through the links. Can somebody of the officials that spend time on CodeForces teach me how do I get there in deterministic manner? Maybe a video tutorial? Or maybe you can just make design compatible with human put the big link to it somewhere on the main page? After all, it is the most important link people want to see on the competition page :(

For those having the same headache with getting there, a link to the list of all rounds: link.

Let's discuss problems here.

•
• +153
•

By Zlobober, 17 months ago, ,

Пару дней назад завершился заочный этап Открытой олимпиады по программированию, результаты уже известны, и вы можете порадоваться собственным результатам в тестирующей системе. Тем временем, мы решили восстановить славную традицию Московских Олимпиад публиковать текстовый разбор задач, в результате чего вашим покорным слугой был составлен следующий документ: Разбор!

Обсуждение решений задач и вопросы к жюри можно продолжить в комментариях к этому посту.

•
• +43
•

By Zlobober, 20 months ago, translation, ,

GP of Ekateinburg has just finished. Let's discuss problems here. How to solve H?

(Russian version of the post contains my anger about statements).

•
• +248
•

By Zlobober, 20 months ago, ,

Hi everybody! It was my first experience of writing problems for TopCoder SRM, hope you liked it. I was a writer of Easy and Medium task in both divisions, subscriber was an author of both Hard tasks. In div1 they were harder than usual, but I hope you still liked them.

#### Div2 easy

This task was just about implementing exactly what is described in the statement. Looks like Python has a built-in support of set comparison. Usually coders using Python have a disadvantage, but in this task it looks more like an advantage :) There are built-in functions for sets in C++ and Java too, I recommend to learn about them even if you successfully submitted this problem.

#### Div2 medium

Knowing strings a and b, we can build a reverse mapping q[d] = c, that maps the encoded letter d to it's original corresponding letter c. For letters that do not appear in b, we remember that we don't know their pre-image. After that, we just apply our mapping q to a string y. If some of letters doesn't have a pre-image, we should return "", otherwise we return q(y).

There is an only special case that appears in sample tests: if we know pre-images of all letters except one, we may still uniquely understand what is its pre-image: it is the only letter that doesn't appear in string a.

#### Div2 hard

This task is an easier version of Div1-hard. In this version it was enough to write a BFS on a graph of all possible states. In this task the state is a set of all already people. Each set can be represented as a binary masks no larger than 218 = 262144 that is small enough to fit in TL.

#### Div1 easy

A first solution coming to a head works in : all we need is to just simulate the process. Suppose we are now standing in number n, the last hour was h, it means that we need to find a first divisor of n or n - 1 larger than f and perform n +  +  or n –  depending on whose (n or n - 1) divisor appears first. Although, one can build a test where number of steps is ~2000, it makes this solution pretty hard to fit in time limit, one of such tests is a last sample test.

The key observation is that when we change our number, we don't need to find divisors of a new number from scratch. The well-known divisor finding algorithm consists of two stages: first we consider all divisors smaller than , then all divisors larger than . If we were on the first stage, then we just need to continue iteration from the same place for a new number. If we are on the second stage, we also continue iterating the second stage with a new number. This works in since our number can't infinitely increase (it can be shown that it can't move further than 2n, actually it doesn't move further than 100).

The other solution was to cache the divisors for all values of n that happen during the execution.

#### Div1 medium

The first observation is that an almost-Eulerian graph can be obtained from a unique Eulerian graph. Indeed, if we have an almost-Eulerian graph G that is not Eulerian, then there exists the only pair of vertices u and v that have an odd degree, the only possible original Eulerian graph G' is (here means inverting the specific edge, adding it or removing it). If G is Eulerian itself, then we obviously can't invert some edge keeping it being Eulerian.

This means that if there are En Eulerian graphs, then there are exactly almost-Eulerian graphs: each Eulerian graph G produces itself and all possible as almost-Eulerian graphs.

Now we need to calculate number of Eulerian graphs on n vertices, En. It's well-known that the graph is Eulerian iff it is connected and all its vertices have even degree. The good idea is to first calculate Dn, the number of graphs with all even degrees. If we succeed in it, we can then calculate En by using inclusion-exclusion principle on Dn.

How many even graphs on n vertices are there? The simplest way to understand that is to remove some vertex from it (let's say, a vertex 1) and notice that the graph on remaining vertices 2, ..., n may contain an arbitrary set of edges. Indeed, if there are some odd vertices among them, then when we return vertex 1 back to the graph, we have to connect it to all odd vertices among 2, ..., n. After that all 2, ..., n become even vertices, and 1 itself also becomes even due to handshake lemma. So, the answer is since there may be any possible set of edges between vertices 2, ..., n and all edges from 1 to the rest of the graph may be uniquely determined.

Now how to calculate En. We know that En = Dn - Rn where Rn is number of disconnected even graphs. Suppose that the connected component that contains vertex number 1 consists of k vertices (obviously, 1 ≤ k ≤ n - 1). Then there are ways to choose k - 1 vertices in this connected component from n - 1 remaining vertices, also there are Ek ways to organize a connected component that has all even degrees and there are Dn - k ways to organize an even graph on the rest of the vertices (note that it may possibly be disconnected if there were 3 or more components in the original graph, that's why we use Dn - k but not En - k here). So, there is a recursive formula: that leads us to an O(n2) DP solution.

#### Div1 hard

I'll describe an approach for this problem very briefly.

What we actually need in this task is to understand how the described process works. We can describe the process in following way. The detective acts almost like a Prim's algorithm: in each step he adds one of the maximal edges between the already visited set and the rest of the vertices in the graph. The only thing that we may adjust is an order of choosing the edges with the equal cost.

At any moment the visited vertices form some part of a maximum spanning tree. Suppose we want to get to vertex x in minimum number of steps. Consider the resulting path between 0 and x. It is a well-known fact that the minimum edge on this number is uniquely defined and is equal to a maximum possible minimum edge among all paths from 0 to x. Suppose the value of this edge is equal to d. We can calculate d by running a Floyd algorithm modification for metric d(u, v) =  minimum on path between u and v, that is needed to be maximized.

There are edges of two kinds on a path from 0 to x: those who are equal to d and those who are larger than d. In any situation we prefer larger edges, so when we touch a vertex with some outgoing edges larger than d, we will greedily first visit all those edges. So, let's contract all components connected by edges larger than d.

After contracting all we need is to find a shortest path from 0 to x remembering that each time we visit a vertex, we have to add a size of its connected component described above.

•
• +103
•

By Zlobober, 21 month(s) ago, translation, ,

Hi everybody!

Hope you liked our Revolution of Colors and Titles. Maybe you even have took part in a contest in new status. The last round have set an incredible record: 8000 participants! And I'm glad to tell you that there was no single technical issue during the round time! Consider the 15-minute delay as a part of our evil plan for setting up a new record :)

I'm glad to tell that Codeforces team is able not only to tune colors and formulas, but also to work on new features for you. You may see on contests page that there is a list of authors for each of the rounds! Moreover, in profile of a person there is now an entry called "problemsetting" that allows you to see the list of all contests in whose preparation a person took a part.

Endagorion looks like this.

•
• +673
•

By Zlobober, 21 month(s) ago, ,

With Revolution of Colors and Titles the new color was introduced (somehow similar to TopCoder's target), the color for legendary coders that now looks like the first letter being black.

Under my browser and operating system (Chrome and Linux Mint) that looks, IMHO, more like a style defect, rather like a nice effect:

My variant and its minor variation are:

What do you think? Feel free to comment or to provide your own vision how the best-coders-ever should look like! The main requirement is to not lose the unique CodeForces style.

•
• +145
•

By Zlobober, history, 23 months ago, translation, ,

The VK Cup championship has just finished. It gave us a great opportunity to try new contest format when contestants participate in teams consisting of two people. While setting up online rounds, finals and finals mirror, we found out many nuances and tricky things that should be considered while running such special contests, but in order to came up with a full picture we need some kind of a feedback from the community.

That's why Codeforces team wants to ask a community to share some thoughts regarding what was done right, what was done wrong, what could be improved and what should be added. Do not hesitate to tell us about your experience or to give some advices regarding such unusual contest format, we would like to hear any reasonable thoughts.

We want any kind of feedback for online rounds, for onsite finals from finalists and for finals mirror that happened yesterday.

•
• +51
•

By Zlobober, history, 23 months ago, translation, ,

Thanks everybody for participating. Tasks follow in the order of the original contest (the mirror order is given in the brackets).

## 562A - Logistical Questions

(in mirror: 566C - Logistical Questions)

Let's think about formal statement of the problem. We are given a tricky definition of a distance on the tre: ρ(a, b) = dist(a, b)1.5. Each vertex has its weight wi. We need to choose a place x for a competition such that the sum of distances from all vertices of the tree with their weights is minimum possible: f(x) = w1ρ(1, x) + w2ρ(x, 2) + ... + wnρ(x, n).

Let's understand how function f(x) works. Allow yourself to put point x not only in vertices of the tree, but also in any point inside each edge by naturally expanding the distance definition (for example, the middle of the edge of length 4 km is located 2 km from both ends of this edge).

Fact 1. For any path in the tree the function ρ(i, x) is convex. Actually, the function dist(i, x) plot on each path [a, b] looks like the plot of a function abs(x): it first decreases linearly to the minimum: the closes to i point on a segment [a, b], and then increases linearly. Taking a composition with a convex increasing function t1.5, as we can see, we get the convex function on any path in the tree. Here by function on the path we understand usual function of a real variable x that is identified with its location on path x: dist(a, x). So, each of the summands in the definition of f(x) is convex on any path in the tree, so f(x) is also convex on any path in the tree.

Let's call convex functions on any path in the tree convex on tree. Let's formulate few facts about convex functions on trees.

Fact 2. A convex function on tree can't have two different local minimums. Indeed, otherwise the path between those minimums contradicts the property of being convex on any path in the tree.

So, any convex function f(x) on the tree has the only local minimum that coincides with its global minimum.

Fact 3. From each vertex v there exists no more than one edge in which direction the function f decreases. Indeed, otherwise the path connecting two edges of function decrease would contradict the definition of a convex function in a point v.

Let's call such edge that function decreases along this edge to be a gradient of function f in point x. By using facts 2 and 3 we see that in each vertex there is either a uniquely defined gradient or the vertex is a global minimum.

Suppose we are able to efficiently find a gradient direction by using some algorithm for a given vertex v. If our tree was a bamboo then the task would be a usual convex function minimization that is efficiently solved by a binary search, i. e. dichotomy. We need some equivalent of a dichotomy for a tree. What is it?

Let's use centroid decmoposition! Indeed, let's take a tree center (i. e. such vertex that sizes of all its subtrees are no larger than n / 2). By using fact 3 we may consider the gradient of f in the center of the tree. First of all, there may be no gradient in this point meaning that we already found an optimum. Otherwise we know that global minimum is located in a subtree in direction of gradient, so all remaining subtrees and the center can be excluded from our consideration. So, by running one gradient calculation we reduced the number of vertices in a considered part of a tree twice.

So, in runs of gradient calculation we almost solved the problem. Let's understand where exactly the answer is located. Note that the global optimum will most probably be located inside some edge. It is easy to see that the optimum vertex will be one of the vertices incident to that edge, or more specifically, one of the last two considered vertices by our algorithms. Which exactly can be determined by calculating the exact answer for them and choosing the most optimal among them.

Now let's calculate the gradient direction in a vertex v. Fix a subtree ui of a vertex v. Consider a derivative of all summands from that subtree when we move into that subtree. Denote this derivative as deri. Then, as we can see, the derivative of f(x) while moving from x = v in direction of subtree ui is  - der1 - der2 - ... - deri - 1 + deri - deri + 1 - ... - derk where k is a degree of vertex v. So, by running one DFS from vertex v we may calculate all values deri, and so we may find a gradient direction by applying the formula above and considering a direction with negative derivative.

Finally, we got a solution in .

## 562B - Clique in the Divisibility Graph

(in mirror: 566F - Clique in the Divisibility Graph)

Order numbers in the sought clique in ascending order. Note that set X = {x1, ..., xk} is a clique iff for (1 ≤ i ≤ k - 1). So, it's easy to formulate a dynamic programming problem: D[x] is equal to the length of a longest suitable increasing subsequence ending in a number x. The calculation formula: for all x in set A.

If DP is written in "forward" direction then it's easy to estimate the complexity of a solution. In the worst case we'll process transitions.

## 562C - Restoring Map

(in mirror: 566E - Restoring Map)

Let's call a neighborhood of a vertex — the set consisting of it and all vertices near to it. So, we know the set of all neighborhoods of all vertices in some arbitrary order, and also each neighborhood is shuffled in an arbitrary order.

Let's call the tree vertex to be internal if it is not a tree leaf. Similarly, let's call a tree edge to be internal if it connects two internal vertices. An nice observation is that if two neighborhoods intersect exactly by two elements a and b then a and b have to be connected with an edge, in particular the edge (a, b) is internal. Conversely, any internal edge (a, b) may be represented as an intersection of some two neighborhoods С and D of some two vertices c and d such that there is a path c – a – b – d in the tree. In such manner we may find all internal edges by considering pairwise intersections of all neighborhoods. This can be done in about n3 / 2 operations naively, or in 32 times faster, by using bitsets technique.

Note that knowing all internal edges we may determine all internal vertices except the only case of a star graph (i. e. the graph consisting of a vertex with several other vertices attached to it). The case of a star should be considered separately.

Now we know the set of all leaves, all internal vertices and a tree structure on all internal vertices. The only thing that remained is to determine for each leaf, to what internal vertex is should be attached. This can be done in following manner. Consider a leaf l. Consider all neighborhoods containing it. Consider a minimal neighborhood among them; it can be shown that it is exactly the neighborhood L corresponding to a leaf l itself. Consider all internal vertices in L. There can be no less than two of them.

If there are three of them or more then we can uniquely determine to which of them l should be attached — it should be such vertex from them that has a degree inside L larger than 1. If there are exactly two internal vertices in L (let's say, a and b), then determining the attach point for l is a bit harder.

Statement: l should be attached to that vertex among a, b, that has an internal degree exactly 1. Indeed, if l was attached to a vertex with internal degree larger than 1, we would have considered this case before.

If both of vertices a and b have internal degree — 1 then our graph looks like a dumbbell (an edge (a, b) and all remaining vertices attached either to a or to b). Such case should also be considered separately.

The solution for two special cases remains for a reader as an easy exercise.

## 562D - Restructuring Company

(in mirror: 566D - Restructuring Company)

This problem allows a lot of solution with different time asymptotic. Let's describe a solution in .

Let's first consider a problem with only a queries of second and third type. It can be solved in a following manner. Consider a line consisting of all employees from 1 to n. An observation: any department looks like a contiguous segment of workers. Let's keep those segments in any logarithmic data structure like a balanced binary search tree (std::set or TreeSet). When merging departments from x to y, just extract all segments that are in the range [x, y] and merge them. For answering a query of the third type just check if employees x and y belong to the same segment. In such manner we get a solution of an easier problem in per query.

When adding the queries of a first type we in fact allow some segments to correspond to the same department. Let's add a DSU for handling equivalence classes of segments. Now the query of the first type is just using merge inside DSU for departments which x and y belong to. Also for queries of the second type it's important not to forget to call merge from all extracted segments.

So we get a solution in time.

## 562E - Max and Min

(in mirror: 566G - Max and Min)

Consider a following geometrical interpretation. Both Max and Min have a set of vectors from the first plane quadrant and a point (x, y). During his turn Max may add any of his vectors to a point (x, y), and Min — may subtract any of his vectors. Min wants point (x, y) to be strictly in the third quadrant, Max tries to prevent his from doing it. Denote Max vectors as Mxi and Min vectors as Mnj.

Consider a following obvious sufficient condition for Max to win. Consider some non-negative direction in a plane, i. e. such vector (a, b) that a, b ≥ 0 and at least one of numbers a, b is not a zero. Then if among Max vectors there is such vector Mxi, that it's not shorter than any of Min vectors Mnj along the direction (a, b) then Max can surely win. Here by the length of vector v along a direction (a, b) we mean a scalar product of vector v and vector (a, b).

Indeed, let Max always use that vector Mxi. Then during the turns of Max and Min point (x, y) is shifted by a vector Mxi - Mnj for some j, so its overall shift along the vector (a, b) is equal to ((Mxi - Mnj), (a, b)) = (Mxi, (a, b)) - (Mnj, (a, b)) ≥ 0. By observing that initially the scalar produt ((x, y), (a, b)) = ax + by > 0 we see that at any moment ax + by will be strictly positive. This means that Min won't be able at any moment to make x and y both be negative (since it would mean that ax + by < 0).

Now let's formulate some kind of converse statement. Suppose Max vector Mxi lies strictly inside the triangle formed by Min vectors Mnj and Mnk. In particular, vector Mxi endpoint can't lie on a segment [Mnj, Mnk], but it may be collinear one of vectors Mnj and Mnk.

Note that since Mxi lies strictly inside the triangle formed by vectors Mnj and Mnk it can be extended to a vector Mx'i, whose endpoint lies on a segment [Mnj, Mnk]. By using linear dependence of Mx'i and Mnj, Mnk we have that Mx'i = (p / r)Mnj + (q / r)Mnk, where p + q = r and p, q, r — integer non-negative numbers. This is equivalent to a formula rMx'i = pMnj + qMnk. This means that if per each r turns of Max in Mxi we will respond with p turns of Min in Mnj and q turns of Min in Mnk, then the total shift will be equal to  - pMnj - qMnk + rMxi =  - rMx'i + rMxi =  - r(Mx'i - Mxi), that is the vector with strictly negative components. So, we are able to block that Max turn, i. e. it does not give any advantage to Max.

The natural wish is to create a convex hull of all Min turns and to consider all Max turns in respect to it. If Max turn lies inside the convex hull of Min turns, then by using the previous fact this turn is meaningless to Max. Otherwise, there are two possibilities.

First, this turn may intersect the hull but go out of it somewhere; in this case this Max turn is no shorter than all Min turns in some non-negative direction (more specifically, in its own direction), so Max wins.

On the other hand, Max vector lies to aside from the Min turns convex hull. Let's suppose the vector Mxi lies to the left of the Min turns. This case requires a special analysis. Consider the topmost of the Min vectors Mnj. If Mxi is no lower than Mxj, then by using the first fact Max is able to win by using only this vector. Otherwise the difference Mni - Mxj is a vector with strictly negative components, by using which we are able to block that Max vector.

So, the full version of a criteria for Min being a winner looks like the following. Consider a convex hull of Min turns and expand it to the left of the topmost point and to the bottom of the rightmost point. If all Max turns lie strictly inside the formed figure then Min wins, otherwise Max wins.

## 562F - Matching Names

(в трансляции: 566A - Matching Names)

Form a trie from all names and pseudonyms. Mark with red all vertices corresponding to names, and with blue all vertices corresponding to the pseudonyms (a single vertex may be marked several times, possibly with different colors). Note that if we match a name a and a pseudonym b, then the quality of such match is lcp(a, b) = 1 / 2(2 * lcp(a, b)) = 1 / 2(|a| + |b| - (|a| - lcp(a, b)) - (|b| - lcp(a, b))), that is equal to a constant 1 / 2(|a| + |b|), with subtracted half of a length of a path between a and b over the trie. So, what we need is to connect all red vertices with blue vertices with paths of a minimum possible total length.

This can be done with a following greedy procedure: if we have a vertex v with x red vertices and y blue vertices in its subtree then we must match min(x, y) red vertices of its subtree to min(x, y) blue vertices of its subtree and leave the remaining max(x, y) - min(x, y) ref or blue vertices to the level higher. The correctness of such algorithm may be easily shown by the next idea. Give each edge of each path a direction from a red vertex to a blue. If some edge recieves two different directions after this procedure, we may cross-change two paths through it so that their total length is reduced by two.

So, we get a solution in O(sumlen) where sumlen is a total length of all names and pseudonyms.

## 562G - Replicating Processes

(в трансляции: 566B - Replicating Processes)

==== UNTRANSLATED SECTION, PLEASE WAIT A FEW MINUTES... ====

Kitten to take your attention :)

This problem may be solved by simulating the replication process. Let's keep a list of all replications that may be applied by the current step. Apply an arbitrary replication, after that update a list by adding/removing all suitable or now unsuitable replications touching all affected on current step servers. The list of replications may be kept in a "double-linked list" data structure, that allows to add and remove elements to/from the set and to extract an arbitrary element of the set in O(1).

The proof of correctness of such algorithm is not hard and is left as an exercies (maybe it will appear here later).

We got a solution in O(n) operation (though, the constant hidden by O-notation is pretty large; the input size is already 12n numbers and the solution itself hides a constant 36 or higher).

Tutorial of VK Cup 2015 - Finals

•
• +100
•

By Zlobober, 23 months ago, translation, ,

The registrations before 00:00 have been deleted, because the form didn't support teams. Please, register again if your registration has been affected.

VK Cup 2015 Final Round has ended two days ago. It's very likely that you've seen our previous posts. The last event to happen is online mirror of the final round. It will be held on Thursday, July 30th, at 19:00 Moscow time. Individual contestants as well as teams consisting of two people may participate in this round. Round duration is three hours, problems will be shuffled in comparison with to the original order. Both division participants may take part, but we want to warn 2nd division contestants that problemset may be hard for them. This round is a rated Codeforces round.

Finally, we want to thank all people that made this Championship. Following VK developers, Codeforces team members and the other people suggested their help to us while creating and preparing problems: PavelKunyavskiy, burunduk3, Dmitry_Egorov, Dembel, dark_ai, MikeMirzayanov, Zlobober, MaximShipko, kuviman, Nickolas, Errichto, sankear и malcolm. We want to thank the people that helped us very much by testing our rounds and giving great advices: winger и AlexFetisov. Also we want to say thank you to all VK members that helped us to run the onsite Finals: burunduk3, burunduk2, KOTEHOK and many others. Thank to all of them!

Good luck and have fun on our Online Mirror!

UPD: Note that during the round the team is allowed to use only one computer. This means that you may code/use console/succeed in solving problems in any other manner by using only one computer at time. The only thing that is allowed from two computers is reading the statements.

UPD2: Since this is a team contest, specially for your convenience we publish the encryped zip-archive with pdf-statements of problems: vkcup2015-mirror-statements.zip. When round starts, we'll publish a password for it.

UPD3: The round will use the dynamic scoring with 250 points step.

UPD4: Due to technical reasons the round starts at 19:20 Moscow time.

UPD5: Password for statements archive: vkcup4ever. Good luck!

UPD6: Online mirror has ended! Congratulations to winners:

1. rng_58
2. Zenith: I_love_Hoang_Yen, langtrunghieu
3. OrOrZZZ!: zld3794955, KFDong
4. Petr team: Petr, ilyakor
5. jcvb_matthew99: matthew99, jcvb

Also, my personal respects for a team "Petr team: Petr, ilyakor" for only solution for a problem Е in this mirror, user rng_58 and a team "Excited: WJMZBMR, TooSimple" for two correct solutions for problem С.

Congratulations to a user rng_58 that showed that a single contestant can compete with teams consisting of two people!

Rating will be updated shortly.

UPD7: Editorial!

Announcement of VK Cup 2015 - Finals

•
• +195
•

By Zlobober, 23 months ago, translation, ,

Hi everybody!

Yesterday, on July 24th, we started VK Cup 2015 Finals! During the day all participants of the competition successfully went to the St. Petersburg, those who got here earlier enjoyed a great trip over the roofs of this beautiful city. And now we are waiting for a practice round that will happen in a few hours, giving participants an option to test their contest environment and do their best while solving several usual (and not only usual) problems. After the lunch, contestants will compete in the first round of the Finals that is called CodeGame Coding, where they have to write the strategy for a battle wizard.

During today and tomorrow not all of the Codeforces features will be available. On this weekend you may take a rest from writing contests and enjoy the results of the one of the biggest competitions of 2015.

The results of the practice round will be available for spectators by this link. Stay tuned!