Endagorion's blog

By Endagorion, history, 7 months ago, translation, In English,

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!

Read more »

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

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By Endagorion, history, 10 months ago, In English,

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!

Read more »

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

By Endagorion, history, 15 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

Tutorial of VK Cup 2018 - Round 3
Tutorial of VK Cup 2018 - Round 3
  • Vote: I like it
  • +83
  • Vote: I do not like it

By Endagorion, history, 16 months ago, translation, In English,

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!

Read more »

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

By Endagorion, history, 21 month(s) ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By Endagorion, 22 months ago, In English,

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!

  1. cubelover
  2. moejy0viiiiiv
  3. ainta
  4. zigui
  5. fateice

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

UPD2: the English editorial is here.

Read more »

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

By Endagorion, history, 22 months ago, In English,

A huge breakthrough in approximation algorithms was announced recently as asymmetric travelling salesman problem was shown to allow a constant approximation scheme. See discussion in an article by R.J. Lipton. One of the co-authors was Jakub dj3500 Tarnawski. It always pleases me to see competitive programmers achieving heights beyond CP, in academia and "real-life" problems (recall that OpenAI's bot recently beat human players at 1v1 Dota2, with meret and Psyho in the developers team). Congratulations on an outstanding achievement, Jakub!

Read more »

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

By Endagorion, history, 23 months ago, In English,

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.

Read more »

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

By Endagorion, history, 23 months ago, translation, In English,

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!

Read more »

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

By Endagorion, history, 2 years ago, In Russian,

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

UPD: screencast of today's DGCJ round.

Read more »

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

By Endagorion, history, 2 years ago, In English,

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!

Problem A. Shifts

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.

Can you solve the problem in this case?
What is the difference when we have only right shifts?
Challenge (hard/research):

Problem B. Number as a gift

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.

There are several cases...
In some of these cases the rest is easy to find...
While in others we have to involve further...
How to proceed?
The complexity is...
Still WA?
Challenge (easy):

Problem C. Recursive Generator

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?

Assume that it is...
Can we make this into a criterion for k = 1?
What about extending this to any k?
How to check is the sequence has no k-contradictions?
Challenge (easy/exercise):

Problem D. Trading

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.


Can we solve the problem if we know the vendor's values of d?
What to do if we do not know d_i's?

This pretty much concludes the idea description.

Still, there are many nasty details...
Challenge (medium):

Problem E. Manhattan Walk

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!


Looks standard, right?
I'm lazy, can I do better?
Challenge (easy, I gueess):

Problem F. Tree Game

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? =)


Phase 1!
Phase 2!
Phase 3!
Challenge (nasty):

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

Read more »

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

By Endagorion, history, 2 years ago, translation, In English,


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.

Read more »

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

By Endagorion, history, 2 years ago, In English,

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.

Read more »

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

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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


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

Read more »

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

By Endagorion, history, 3 years ago, In English,

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

Problem A

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

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(n2), or more effeciently using sorts in .

Problem B

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 2k - 1. If i + k - 1 > n, then the ``free'' bulbs are limited by the end of the line, and the number of configurations is 2n - 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)2k - 1, this number can be computed in .

Problem C

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 ai, that is, 106) 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) - aM), 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

Problem D

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, 2M. 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 2L apart.

I want to describe another, much simpler solution by Chmel_Tolstiy. Let's find the smallest k such that color(2k) ≠ 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).

Problem E

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 a1, \ldots, a2k, 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 a1 + a2k, a2 + a2k - 1, and so on. Indeed, consider that a1 is not matched with a2k but with ax, and a2k is matched with ay. Let's rematch them as a1 + a2k and ax + ay. Since the array is sorted, a1 + a2k, ax + ay ≤ ay + a2k and the maximum sum won't increase after rematching. Drop the elements a1 and a2k and proceed until we obtain the matching a1 + a2k, a2 + a2k - 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.

Problem F

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 xi, xi + 1, xi + 2 with xi + 2 ≤ xi + xi + 1 + 1, then all positions with a + b < xi will be unsolvable. If we drop all xj < xi, the sum of the rest elements of X will be O(A), which allows for a simple simulation.

Read more »

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

By Endagorion, history, 3 years ago, translation, In English,

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

Read more »

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

By Endagorion, history, 4 years ago, In English,

I'm terribly sorry for the delay.

Please report any mistakes.

614A - Link/Cut Tree

Author: Tigutor

Developers: Tigutor, ch_egor

You had to print all numbers of form kx for non-negative integers x that lie with the range [l;r]. A simple cycle works: start with 1 = k0, 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 = 1018, k = 109, the powers will be 1, 109, 1018, and the next power is 1027, which does not fit in a standard integer type.

614B - Программа Гены

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 10t 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.

613A - Петя и снегоуборочная машина

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 π (R2 - r2).

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

613B - Навыки

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  ≥ arrindex.

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, arrindex + ⌊ 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.

613C - Бусы

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 geq2. 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?

613D - Королевство и его города

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 .

613E - Любитель кроссвордов

Author, developer: Endagorion

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


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 dx, 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(n2) 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(n2) 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.)

Read more »

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

By Endagorion, history, 4 years ago, In Russian,

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

250 — MissingLCM

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

450 — ColorfulLineGraphs

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

1000 — BridgeBuilding

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

Call the parts of the graph between the merged vertices the havens (or whatever); a haven can be a loop or a pair of paths joined together. A loop haven can be represented by a pair of numbers (l, r) — the numbers of merged points in the original enumeration. Denote Ll, r (Rl, r) the largest distance from a vertex of (l, r)-haven to the merged vertex l (r), Sl, r the largest distance between any two vertices of (l, r)-haven, and Dl, r the distance between l and r (after merging each of them). All these numbers can be computed in O(n3) for all pairs (l, r) (use two pointers to compute Sl, r).

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

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

Read more »

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

By Endagorion, 4 years ago, In Russian,

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

A — Buildind a Bookshelf

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

B — Flatland Division

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

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

C — Solitaire Simplified

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

Consider an inverse permutation of the deck; that is, if the i-th number of the deck is pi, numbers qi are determined by qpi = i. The number 1 will be surely thrown out on the first discarded through the cards; the number will be discarded on the first pass if q2 > q1 or q2 > q3 > ... > qn; and so on.

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

D — Xor

Coming up.

E — Tree Growing

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

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

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

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

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

F — To Saw Or Not To Saw

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

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

Read more »

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

By Endagorion, 4 years ago, In English,

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.

538A - Cutting Banner

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(n2) or O(n3) 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? =)

538B - Quasi Binary

n is up to 106. We may note that there are only 26 + 1 = 65 quasi-binary numbers not exceeding 106, 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 ≤ 1018.

538C - Tourist's Notes

We want to make the maximum height as large as possible. Consider the part of the chain that was travelled between di and di + 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 d1 and after dn, 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 di = 0 and di + 1 = t (they may be increased of decreased simultaneously without changing the answer), and hdi = a, hdi + 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 |hi - hi + 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 hi ≤ a + i and hi ≤ b + (t - i) hold. Let hi = min(a + i, b + (t - i)) on the [0; t] segment; clearly, every hi accomodates the largest possible value, therefore the value of maximum is also the largest possible. It suffices to show that these hi satisfy the difference condition. Basically, two cases should be considered: if for hi = a + i and hi + 1 = a + i + 1, or hi = b + (t - i) and hi + 1 = b + (t - i - 1), the statement is obvious. Else, hi = a + i but hi < b + (t - i) = hi + 1 + 1, and hi + 1 = b - (t - i - 1) but hi + 1 < a + (i + 1) = hi + 1. Thus, |hi - hi + 1| < 1, and hi = hi + 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 hdi for a sequence hi), determine how many (modulo a prime number) integer sequences of length n with the property |hi - hi + 1| ≤ 1 agree with the subsequence and have global maximum equal to H? Can you solve the problem in O(n2) time? In time? Maybe even faster?

538D - Weird Chess

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 (x1, y1) containing a piece, and a field (x2, y2) not containing a piece and not being attacked, clearly a move (x2 - x1, y2 - y1) 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(n4) 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.

538E - Demiurges Play Again

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 u1, ..., uk, 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(ui) maximal numbers (that is, w(v) - w(ui) + 1, ..., w(v)) in the subtree of w(ui), we must also arrange them optimally; this task is basically the same as arranging the numbers from 1 to w(ui) in the subtree of w(ui), 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 n1, 1, ..., n1, w(ui) to the leaves of the subtree of ui in some order; the numbers in the subtree of ui will be arranged so that the result is maximal when the maximizing player starts in ui. Suppose that numbers ni, j are sorted by increasing of j for every i; the minimizing player will then choose the subtree ui 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 ni, j for should also be greater than r; but there are numbers ni, 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 ni, j with , and r as, say, n1, dpmax(u1); the first player will have to move to u1 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 ui contains dpmax(ui) numbers, the minimizing player can go to ui and grab the current result. It follows that we may safely put dpmax(ui) - 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 dpmax(root) = a and dpmin(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?

538F - A Heap of Heaps

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 av is the element . One can show that there are only different elements that can be the parent of av 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 av and ap); 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 ck 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 ck (for a given k) in time? Can you find all ck (for 1 ≤ k ≤ n - 1) at once in O(n2) 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(n2)? 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?

538G - Berserk Robot

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 xi + yi and xi - yi 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 xi and ti 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 si the number of 1's among the first i commands, and s = sl for simplicity. Evidently, an equation holds, because the full cycle is executed ti / 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 sl = s. In any correct program si ≤ si + 1 ≤ si + 1, but not all values of si are known to us. When is it possible to fill out the rest of si to match a correct program? If sa and sb are adjacent entries that are fixed (that is, every sc under a < c < b is not fixed), the inequality 0 ≤ sb - sa ≤ 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 sb - sa 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 sa come! Sort them by non-decreasing of a. All fixed sa can be expressed as linear functions of s; if we substitute these expressions in the 0 ≤ sb - sa ≤ 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?)

538H - Summer Dichotomy

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 (n1, n2). Provided this distribution, in what cases a pair of conflicting teachers can be arranged correctly? If the teachers' segments are [l1, r1] and [l2, r2], either l1 ≤ n1 ≤ r1 and l2 ≤ n2 ≤ r2, or l2 ≤ n1 ≤ r2 and l1 ≤ n2 ≤ r1 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 = x1 and x = x2 respectively. The intersection of subsegments for UOTRs obtained after the first event will stay the same while x1 ≤ x < x2. Suppose the y's subsegmen intersection is equal to [l;r]. If we stay within x1 ≤ x < x2, for a satisfying pair of (x, y) the minimal value of x + y is equal to x1 + l, and the maximal value is x2 + 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 zi, j which correspond to the event 'ni 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 ≤ n1 + n2 ≤ 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, zi, j for j < 0 clearly must be considered automatically false, and zi, 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 wj 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: n1 and n2 are maximal so that z1, n1 and z2, n2 hold, and the teachers are distributed unequivocally by values of wj. 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 n1 and n2 may be reduced to 0, t, li, t - li, ri, t - ri. We can prove that by starting from any valid values of n1 and n2 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!

Read more »

Tutorial of Codeforces Round #300
  • Vote: I like it
  • +312
  • Vote: I do not like it

By Endagorion, 4 years ago, In English,

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:

  1. bmerry
  2. Egor
  3. Petr
  4. rng_58
  5. scott_wu
  6. TooSimple
  7. eatmore
  8. atetubou
  9. qwerty787788
  10. niyaznigmatul

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.

Read more »

Announcement of Codeforces Round #300
  • Vote: I like it
  • +1212
  • Vote: I do not like it

By Endagorion, 4 years ago, In Russian,

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

SquareScores (250)

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

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

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

SuccessiveSubstraction (450)

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

TwoEntrances (850)

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

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

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

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

Read more »

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

By Endagorion, 4 years ago, In English,

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

Make sure to comment if you find any mistakes.

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

520A - Pangram

Idea: Endagorion

Preparation: Endagorion

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

To make all the letters lowercase, one could use standard functions, like tolower in Python. Also, it is known that the letters from a to z have consecutive ASCII numbers, as well as A to Z; an ASCII number of symbol is ord(c) in most languages. So, to get the number of a lowercase letter in the alphabet one can use ord(c) - ord('a') in most languages, or simply c - 'a' in C++ or C (because a char in C/C++ can be treated as a number); to check if a letter is lowercase, the inequality ord('a') <= ord(c) && ord(c) <= ord('z') should be checked.

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

520B - Two Buttons

Idea: Endagorion

Preparation: Endagorion

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

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

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

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

520C - DNA Alignment/521A - DNA Alignment

Idea: Endagorion

Preparation: Endagorion

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

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

520D - Cubes/521B - Cubes

Idea: savinov

Preparation: savinov, sokian, zemen

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

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

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

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

This solution is if using the appropriate data structure.

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

520E - Pluses everywhere/521C - Pluses everywhere

Idea: Endagorion

Preparation: gchebanov, DPR-pavlin

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

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

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

To sum up, the total answer is equal to

Let us transform the sum:

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

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

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

521D - Shop

Idea: Endagorion

Preparation: gchebanov

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

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

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

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

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

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

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

521E - Cycling City

Idea: Endagorion

Preparation: Endagorion

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

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

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

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

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

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

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

Read more »

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