Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Endagorion's blog

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

Heya! I'm going to stream my performance during ICPC Challenge 2020 on my Youtube channel. I'm not great at marathon-style but I'll see what I can do.

I know this is a competition with prizes which you generally can not stream, but ICPC people seem to be okay with this (in fact this wasn't my idea in the first place), so there you go. I still feel a bit weird about this, so I won't try to explain anything I do (help yourself and try to read my code if you want lol). To make it a little less boring, I'm down to talk to everyone in the chat. Drop by and say hello! Unless you want to focus on the competition of course.

Also check out the official Day Zero stream. GL&HF!

Read more »

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

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

Thank you for waiting! I hope you've enjoyed the problems. Let me know what you think in the comments!

UPD: I almost forgot but here are some notes, as well as challenges for all problems. For a lot of them I don't have a solution and would be happy to hear your ideas.

Tutorial is loading...
Challenge (awful)
Tutorial is loading...
Challenge (?)
Notes
Tutorial is loading...
Challenge (probably doable)
Tutorial is loading...
Challenge (?)
Tutorial is loading...
Challenge (???)
Notes
Tutorial is loading...
Challenge (probably doable)
Tutorial is loading...
Challenge (?)
Notes
Tutorial is loading...
Challenge (running out of ideas)

Read more »

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

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

Hi!

On Jun/18/2020 17:45 (Moscow time) we will host Codeforces Global Round 8.

It is the second round of a 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2020:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2020 supported the global rounds initiative!

Problems for this round are set by me. Thanks a lot to the coordinator 300iq and testers thenymphsofdelphi, Lewin, Golovanov399, Osama_Alkhodairy, gamegame, dorijanlendvaj, HenriqueBrito, kocko, ruban, Origenes, Ilya-bar, rahulkhairwar. Their feedback was a huge help and affected the problemset greatly.

The round will have eight problems and will last 150 minutes.

Scoring distribution: 500 — 1000 — 1500 — 1750 — 2500 — 3000 — 3500 — 3000+1500

Good luck, and see you on the scoreboard!

UPD: the round has concluded, congratulations to the winners:

  1. ecnerwala
  2. tourist
  3. Marcin_smu
  4. Petr
  5. Radewoosh
  6. Um_nik
  7. maroonrk
  8. eatmore
  9. snuke
  10. KAN

Check current Codeforces Global series standings here (courtesy of aropan).

You can find the editorial here.

Stay tuned for prizes announcement!

Read more »

Announcement of Codeforces Global Round 8
 
 
 
 
  • Vote: I like it
  • +1315
  • Vote: I do not like it

By Endagorion, history, 5 weeks ago, translation, In English,

How is self-isolation treating you? I recently found this channel with a guy solving Sudoku-like puzzles. Had a lot of fun trying to solve puzzles for myself, and then watching the pro do it ten times faster while explaining everything. That reminded me I didn't upload to my Youtube for a while, and gave a good impression of how things look from the other side.

So here's me solving an old AtCoder Regular Contest for practice. From my experience I can recommend trying to solve problems yourself before watching me do it. Wasn't in particular hurry this time, trying to explain my thoughts as good as I can. Let me know what you think, and enjoy!

Read more »

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

By Endagorion, history, 8 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...
Tutorial is loading...

Read more »

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

By Endagorion, 8 months ago, translation, In English,

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

Congrats to the winners!

Technocup edition:

  1. cookiedoth
  2. MaximOboznyi
  3. AlFlen
  4. Chereshnya_
  5. DANDROZAVR

Div. 1 round:

  1. Benq
  2. wxhtxdy
  3. tourist
  4. Um_nik
  5. TLE

Div. 2 round:

  1. BBumblebee
  2. twytch19
  3. zhongyuwei
  4. kpink
  5. 1LLUS0RY

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


Scoring distribution:

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

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

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


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

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

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

Have fun!

Read more »

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

By Endagorion, history, 18 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

By Endagorion, history, 18 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 Codealittle Contest-1
 
 
 
 
  • Vote: I like it
  • +26
  • Vote: I do not like it

By Endagorion, history, 21 month(s) 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, 2 years 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
 
 
 
 
  • Vote: I like it
  • +83
  • Vote: I do not like it

By Endagorion, history, 2 years 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, 3 years 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, 3 years 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, 3 years 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, 3 years 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, 3 years 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, 3 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?
Finally...
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.

Solution:

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!

Solution:

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

Solution:

Phase 1!
Phase 2!
Phase 3!
Assemble?
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, 3 years ago, translation, In English,

Hi!

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

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

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

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

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

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

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

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

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

UPD2: the round is finished! Here be editorial.

Read more »

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

By Endagorion, history, 3 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

By Endagorion, history, 3 years 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 »

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

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

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, 4 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(n 2), 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 2 k - 1. If i + k - 1 > n, then the ``free'' bulbs are limited by the end of the line, and the number of configurations is 2 n - i. There is also one combination when all bulbs are off.

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

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 a i, 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) - a M), proceed until we win everyone or M repeats. This optimization leads to O(n + A) solution.

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

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

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(2 k) ≠ color(0). It is easy to prove that there is exactly one change color between these two positions, so its position can be found with binary search as before. Do the same way in negative direction and find another closest color change, output the difference. This solution turned out to be most popular among contestants (but less popular among the testers).

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 a 1, \ldots, a 2k, and want to make pairs of its elements such that sum in each pair does not exceed D. It can be shown that the optimal way is to sort the array and then match a 1 + a 2k, a 2 + a 2k - 1, and so on. Indeed, consider that a 1 is not matched with a 2k but with a x, and a 2k is matched with a y. Let's rematch them as a 1 + a 2k and a x + a y. Since the array is sorted, a 1 + a 2k, a x + a y ≤ a y + a 2k and the maximum sum won't increase after rematching. Drop the elements a 1 and a 2k and proceed until we obtain the matching a 1 + a 2k, a 2 + a 2k - 1, \ldots.

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

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

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

Read more »

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

By Endagorion, history, 4 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 - Gena's Code

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 - Peter and Snow Blower

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

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

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 - Kingdom and its Cities

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 - Puzzle Lover

Author, developer: Endagorion

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

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

That is, there can be following parts:

  • go back a symbols in one row, then go forward a symbols in the other row (possibly a = 0)

  • go forward with arbitrarily up and down shifts in a snake-like manner

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

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

Fix the direction. We will count the DP 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(n 2) states and transitions. However, there are still some questions left. How do we perform the substring comparisons? There is a whole arsenal of possible options: (carefully implemented) hashes, suffix structures, etc. Probably the simplest way is to use Z-function for a solution that does O(n 2) precalc and answers each substring query in O(1) time (can you see how to do it?).

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

Read more »

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