Zlobober's blog

By Zlobober, 5 months ago, translation, In English,

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

731A - Night at the Museum

Problem author: egor-belikov, developer: timgaripov

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

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

731B - Coupons and Discounts

Problem author: olympiad jury, developer: platypus179

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

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

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

Such a solution works in O(n).

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

731C - Socks

Problem author: egor-belikov, developer: wilwell

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

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

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

Such a solution works in .

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

731D - 80-th Level Archeology

Problem author: olympiad jury, developer: Flyrise

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

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

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

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

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

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

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

731E - Funny Game

Problem author: _meshanya_, developer: ipavlov

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

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

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

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

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

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

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

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

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

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

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

731F - Video Cards

Problem author: olympiad jury, developer: gritukan

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

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

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

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

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

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

Read more »

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

By Zlobober, 5 months ago, translation, In English,

Hi everybody!

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

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

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

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

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

Congratulations to contest winners:

  1. DmitryBelikov
  2. ljsss
  3. kehKeLenge
  4. dilsonguim
  5. AC_is_ZQC

Read more »

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

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

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

Enter contest.

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

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

Problem editorial

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

Hi everybody!

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



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

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

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

See you tomorrow!

UPD:

Congratulations to the winners!

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

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


Read more »

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

By Zlobober, history, 9 months ago, translation, In English,

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

Russian editorial

English editorial

Read more »

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

By Zlobober, 9 months ago, In English,

Hi everybody!

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

Good luck and have fun!

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

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

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

UPD3: Congratulations to winners:

  1. TooDifficuIt
  2. eatmore
  3. rng_58
  4. jcvb
  5. KAN

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

Read more »

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

By Zlobober, history, 11 months ago, In English,

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

Good luck!

Read more »

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

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

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

Read more »

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

By Zlobober, 13 months ago, translation, In English,

Hi everybody!

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

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

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

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

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

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

Read more »

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

By Zlobober, history, 13 months ago, In English,

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

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

Read more »

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

By Zlobober, history, 14 months ago, In English,

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

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

Good luck to everybody!

UPD: UP! The round is in 30 minutes.

Read more »

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

By Zlobober, 14 months ago, In English,

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

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

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

Let's discuss problems here.

Read more »

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

By Zlobober, 14 months ago, In Russian,

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

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

Read more »

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

By Zlobober, 17 months ago, translation, In English,

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

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

Read more »

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

By Zlobober, 17 months ago, In English,

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

Div2 easy

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

Div2 medium

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

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

Div2 hard

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

Div1 easy

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

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

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

Div1 medium

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

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

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

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

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

Div1 hard

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

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

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

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

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

Read more »

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

By Zlobober, 18 months ago, translation, In English,

Hi everybody!

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

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


Endagorion looks like this.

Read more »

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

By Zlobober, 18 months ago, In English,

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

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

My variant and its minor variation are:

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

Read more »

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

By Zlobober, history, 20 months ago, translation, In English,

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

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

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

Read more »

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

By Zlobober, history, 20 months ago, translation, In English,

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

562A - Logistical Questions

(in mirror: 566C - Logistical Questions)

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

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

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

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

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

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

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

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

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

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

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

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

Finally, we got a solution in .

562B - Clique in the Divisibility Graph

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

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

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

562C - Restoring Map

(in mirror: 566E - Restoring Map)

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

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

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

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

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

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

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

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

562D - Restructuring Company

(in mirror: 566D - Restructuring Company)

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

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

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

So we get a solution in time.

562E - Max and Min

(in mirror: 566G - Max and Min)

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

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

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

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

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

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

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

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

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

562F - Matching Names

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

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

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

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

562G - Replicating Processes

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

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

Kitten to take your attention :)

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

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

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

Read more »

Tutorial of VK Cup 2015 - Finals
 
 
 
 
  • Vote: I like it  
  • +100
  • Vote: I do not like it  

By Zlobober, 20 months ago, translation, In English,

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

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

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

Good luck and have fun on our Online Mirror!

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

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

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

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

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

UPD6: Online mirror has ended! Congratulations to winners:

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

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

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

Rating will be updated shortly.

UPD7: Editorial!

Read more »

Announcement of VK Cup 2015 - Finals
 
 
 
 
  • Vote: I like it  
  • +195
  • Vote: I do not like it  

By Zlobober, 20 months ago, translation, In English,

Hi everybody!

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

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

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

Read more »

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

By Zlobober, history, 21 month(s) ago, In English,

Round #309 was first moved from Monday to Tuesday, and now it is moved to Wednesday because of our technical reasons and schedule of other online contests. Don't be confused with that. Stay tuned!

Read more »

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

By Zlobober, history, 21 month(s) ago, In English,

Google Code Jam Distributed Round starts in 15 minutes. It's a brand new format of contest, top-10 will advance to its own onsite final round in Seattle.

Let's discuss problems here after round finishes.

GL & HF everybody!

Read more »

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

By Zlobober, history, 21 month(s) ago, translation, In English,

Today at 14:00 UTC there will be the third round of Google Code Jam. Top-25 contestants will be invited to the final round in the Seattle.

Good luck to everybody!

Read more »

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

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

Introduction

Checker is a program that should be written when task allows more than one correct solution. Although it seems that it is very easy to write checker, there are lots of important technical details that are easy to forget if you don't use a special library like testlib.h.

A common convention is that a checker should be a program taking three command-line arguments: the testdata filename, the participant output filename and the jury answer filename. Checker should read the contents of the input, output and answer, decide whether participant answer is correct (and optimal being compared to the jury's answer if there can be unoptimal answer in this task) and return one of several pre-defined verdicts:

Verdict testlib macro meaning
Ok _ok The output is correct, follows the output format and represents an optimal answer (if applicable in this problem).
Wrong Answer _wa The output is wrong or incorrect.
Presentation Error _pe The output doesn't follow output format specification of the task. Although, on Codeforces this verdict is being replaced by Wrong Answer since it's usually hard to distinguish Presentation Error and Wrong Answer
Partially Correct _pc(score) If there is a partial scoring in the task, this verdict should be used in situation when solution is partially correct or to give solution some number of points. Here score should be an integer between 0 and 200 where 0 represents the lowest mark (no points) and 200 represents the highest mark (maximum possible number of points)
Fail _fail This verdict means that checker has encountered a critical internal error or that the jury's answer is incorrect or that contestant found the more optimal answer than jury. This verdict means that something wrong has happened and it requires a special investigation from jury.

Usually the verdict returned by checker is indicated by the return code of its executable, but it may possibly be transfered to the testing system by many other ways: by creating a special xml-file with checker outcome, by writing to stdout or somehow else. When using testlib.h for writing a checker all those system-dependent ways are combined in a single expression quitf(VERDICT, "comment", ...).

Simplest checker example

Problem statement: You are given two integers a and b ( - 1000 ≤ a, b ≤ 1000). Find their sum and output it.

Let's write a checker for this problem. It will be very simple:

#include "testlib.h"

int main(int argc, char* argv[]) {
    // This command initializes checker environment.
    registerTestlibCmd(argc, argv);
    // Now there are three global variables specifying testlib streams:
    // inf - stream with the testdata.
    // ouf - stream with the contestant output.
    // ans - stream with the jury answer.
    // All those streams provide the similar interface for reading data.

    // This function reads a single integer from the participant output that 
    // should be between -2000 and 2000. If it doesn't belong to the specified
    // range, checker finishes with verdict _pe and comment saying that [sum of numbers]
    // is outside of the specified range.
    int pans = ouf.readInt(-2000, 2000, "sum of numbers");
    
    // This function reads a single integer from the jury output. Here we suppose
    // that jury's answer is correct and we do not need to additionally verify it.
    int jans = ans.readInt(); // We suppose that jury's answer is correct
    
    if (pans == jans)
        quitf(_ok, "The sum is correct."); // This finishes checker with verdit OK.
    else
        // quitf handles a comment like printf, i. e. you may use specifiers like
        // %d, %s etc in the comment.
        quitf(_wa, "The sum is wrong: expected = %d, found = %d", jans, pans);
}

Available methods

There are lots of methods useful for writing checkers.

Method Description
stream.readXXX All methods of form readXXX (like readInt, readLong, readDouble, readToken etc) are common for all testlib uses: checkers, validators and interactors. TODO: put all such methods on the separate page.
void quit(TResult verdict, string message);
void quit(TResult verdict, const char* message);
void quitf(TResult verdict, const char* message, ...);
Finishes the checker with a given verdict and comment.
void quitif(bool condition, TResult verdict, const char* message, ...); if condition is true then performs quitf(verdict, message, ...)
void ensuref(bool condition, const char* message, ...); An equivalent of assert. Checks that condition is true, otherwise finishes with _fail verdict. Useful for debugging checkers.

TODO: finish this list.

readAns paradigm

Suppose you have a task that asks contestant to find a complex composite answer that is not just a single number. Example:

Problem statement You are given a connected undirected weighted graph witn n vertices and m edges. Find a simple path between vertex s and vertex t (s ≠ t) of maximum weight and output it. Samples (input and output format is clarified in square brackets):

Sample input Sample output
4 5 [n, m]
1 2 4 [edges]
2 4 2
1 4 4
1 3 5
3 4 3
1 4 [s, t]
3 [number of vertices in path]
1 3 4 [path]

Here is an example of bad checker implementation for this task.

Bad checker implementation

#include "testlib.h"
#include <map>
#include <vector>
using namespace std;

map<pair<int, int>, int> edges;

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
    int n = inf.readInt(); // no need to additionally call readSpace() or readEoln() since
    int m = inf.readInt(); // there is no need to validate input file in the checker
    for (int i = 0; i < m; i++) {
        int a = inf.readInt();
        int b = inf.readInt();
        int w = inf.readInt();
        edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
    }
    int s = inf.readInt();
    int t = inf.readInt();

    // reading jury answer
    int jvalue = 0;
    vector<int> jpath;
    int jlen = ans.readInt();
    for (int i = 0; i < jlen; i++) {
        jpath.push_back(ans.readInt());
    }
    for (int i = 0; i < jlen - 1; i++) {
        jvalue += edges[make_pair(jpath[i], jpath[i + 1])];
    }
    
    // reading participant answer
    int pvalue = 0;
    vector<int> ppath;
    vector<bool> used(n, false);
    int plen = ouf.readInt(2, n, "number of vertices"); // path should at least contain s and t
    for (int i = 0; i < plen; i++) {
        int v = ouf.readInt(1, n, format("path[%d]", i + 1).c_str());
        if (used[v - 1]) // checking that no vertex is used twice
            quitf(_wa, "vertex %d was used twice", v);
        used[v - 1] = true;
        ppath.push_back(v);
    }
    // checking that path is actually between s and t
    if (ppath.front() != s) 
        quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s, ppath.front());
    if (ppath.back() != t)
        quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t, ppath.back());
    // checking that each pair of adjacent vertices in the path is indeed connected by an edge
    for (int i = 0; i < plen - 1; i++) {
        if (edges.find(make_pair(ppath[i], ppath[i + 1])) == edges.end())
            quitf(_wa, "there is no edge (%d, %d) in the graph", ppath[i], ppath[i + 1]);
        pvalue += edges[make_pair(ppath[i], ppath[i + 1])];
    }
    
    if (jvalue != pvalue)
        quitf(_wa, "jury has answer %d, participant has answer %d", jvalue, pvalue);
    else
        quitf(_ok, "answer = %d", pvalue);
}

Here are the main two issues that appear in this checker.

  1. It believes that the jury's answer is absolutely correct. In case when jury's answer is unoptimal and contestant have really found the better answer, he will get the verdict WA that is not fair. There is a special verdict Fail exactly for this situation.
  2. It contains the duplicating code for extracting the answer value for jury and contestant. In this case extracting the value is just one "for" cycle but for a harder task it may be a very complicated subroutine, and as usual, using the duplicated code makes twice harder to fix it, rewrite it or change it when output format changes.

In fact, reading an answer value is a subroutine that works exactly the same for contestant and jury. That's why it is usually being put into a separate function receiving the input stream as a parameter.

Good checker implementation

#include "testlib.h"
#include <map>
#include <vector>
using namespace std;

map<pair<int, int>, int> edges;
int n, m, s, t;

// This function receives stream as an argument, reads an answer from it,
// checks its correctness (i. e. that it is indeed a correct path from s to t in the graph),
// calculates its value and returns it. If the path is incorrect, it stops the execution
// with _wa outcome if stream = ouf (contestant) or with _fail outcome if stream = ans (jury).
int readAns(InStream& stream) {
// reading participant answer
    int value = 0;
    vector<int> path;
    vector<bool> used(n, false);
    int len = stream.readInt(2, n, "number of vertices"); // path should at least contain s and t
    for (int i = 0; i < len; i++) {
        int v = stream.readInt(1, n, format("path[%d]", i + 1).c_str());
        if (used[v - 1]) { // checking that no vertex is used twice
            // stream.quitf works as quitf but it modifies the verdict according
            // to what stream it is being invoked from. If stream == ouf then
            // it works exactly like quitf, otherwise if stream == ans then
            // any verdict will work like _fail (because it's bad when jury's answer is incorrect)
            stream.quitf(_wa, "vertex %d was used twice", v);
        }
        used[v - 1] = true;
        path.push_back(v);
    }
    // checking that path is actually between s and t
    if (path.front() != s) 
        stream.quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s, path.front());
    if (path.back() != t)
        stream.quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t, path.back());
    // checking that each pair of adjacent vertices in the path is indeed connected by an edge
    for (int i = 0; i < len - 1; i++) {
        if (edges.find(make_pair(path[i], path[i + 1])) == edges.end())
            stream.quitf(_wa, "there is no edge (%d, %d) in the graph", path[i], path[i + 1]);
        value += edges[make_pair(path[i], path[i + 1])];
    }
    return value;
}

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
    n = inf.readInt(); // no need to additionally call readSpace() or readEoln() since
    m = inf.readInt(); // there is no need to validate input file in the checker
    for (int i = 0; i < m; i++) {
        int a = inf.readInt();
        int b = inf.readInt();
        int w = inf.readInt();
        edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
    }
    int s = inf.readInt();
    int t = inf.readInt();

    int jans = readAns(ans);
    int pans = readAns(ouf);
    if (jans > pans)
        quitf(_wa, "jury has the better answer: jans = %d, pans = %d\n", jans, pans);
    else if (jans == pans)
        quitf(_ok, "answer = %d\n", pans);
    else // (jans < pans)
        quitf(_fail, ":( participant has the better answer: jans = %d, pans = %d\n", jans, pans);
}

Notice that by using this paradigm we also check the jury answer for being correct. Checkers written in such form are usually shorter and easier to understand and fix. It is also applicable when task output is NO/(YES+certificate).

Notes, advices and common mistakes

  • Use readAns paradigm. It really makes easier to understand and work with your checker.
  • Always use optional arguments for methods like readInt(), readLong() etc. If you forget to check range for some variable, your checker may work incorrectly or even face runtime-error that will result in Check Failed in testing system.

Bad:

// ....
int k = ouf.readInt();
vector<int> lst;
for (int i = 0; i < k; i++)       // This will behave similarly for k = 0 as well as for k = -5.
    lst.push_back(ouf.readInt()); // But we don't want to accept list of length -5, don't we?
// ....
int pos = ouf.readInt();
int x = A[pos]; // 100% place for runtime-error. There will surely be a contestant who will output
                // -42, 2147483456 or some other garbage instead of correct value.
// ....

Good:

// ....
int k = ouf.readInt(0, n); // Now negative values of k will cause PE.
vector<int> lst;
for (int i = 0; i < k; i++)
    lst.push_back(ouf.readInt());
// ....
int pos = ouf.readInt(0, (int)A.size() - 1); // That's how we prevent index out of range.
int x = A[pos]; 
// ....
  • Use optional comments in readXXX methods. With them it is much easier to understand where did checker stop its execution (if not you don't specify it, the comment will be like "integer doesn't belong to range [23, 45]" and it's not clear what integer caused such behavior). Also write informative comments in quitf calls; remember that your comments will be probably available to the contestants after the competition (or even during the competition like while hacking on Codeforces).

Read more »

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

By Zlobober, 23 months ago, translation, In English,

542A - Place Your Ad Here

Let's fix the TV channel window and look for a commerical having the largest intersection with it. There are four types of commercials: lying inside the window, overlapping the window and partially intersecting the window from the left and from the right.

It's easy to determine if there is overlapping commercial: it's enough to sort commercials in increasing order of the left end and then while iterating over them from left to right, keep the minimum value of a right end of a commercial. If when we pass the window j and see that current value of the maximum right end is no less than bj then there exists a commercial overlapping our window and the value is equal to the (ri - lici.

Among all commercials that lie inside our window we need the longest one. It can be done by similar but a bit harder manner. Let's use sweepline method. While passing through the end of the commercial ri, let's assign in some data structure (like segment tree) the value ri - li in point li. While passing through the end of a window, let's calculate answer for it as a maximum on segment [aj, bj]. By doing this, we consider all commercials inside the window.

We can process partially intersecting commercials in the similar way. While passing the right end of the commercial ri let's put the value ri in the point li in our data structure. While passing through the right end of a window bj let's calculate the answer for it as a maximum on the segment [aj, bj] minus aj.

Among all answers for all commercials we need to choose the largest one. So we have the solution in .

Challenge. What if there are weights not only on windows, but on commercials also, and those weights are multiplied with the intersection length? You can solve this task in and get a virtual medal!

542B - Duck Hunt

First of all, let's say that ducks stay still and the one that moves is the hunter. Let's define the value F[x][s] as the minimum number of ducks among having the right end no further than x, that we can't shot if the last shot was in the point s. In particular, the value F[x][s] includes all ducks located inside the segment [s + 1, x]. Values F[x][s] for s > x let's consider as undefined.

Let's look on F[x] as on a function of s. This function is defined on all s from 0 to x inclusive. The key idea is in investigating how F[x + 1][·] differs from F[x][·].

Let's first suppose that in point x + 1 there is no end of the duck. Then in definition of F[x + 1][·] we consider the same set of the ducks as for the definition f F[x][·]. That means that all values F[x][s] for s ≤ x are the same for F[x + 1]. Let's understand what happens with F[x + 1][x + 1]. It's easy to see that the shot in point x + 1 can't kill any of the ducks that end no further than x + 1 (since we just supposed that there are no ducks ending in exactly x + 1). So, F[x + 1][x + 1] = min F[x + 1][0... x + 1 - r] = min F[x][0... x + 1 - r].

Now let's suppose that in point x + 1 the duck [l, x + 1] ends. In this case we can say that all values of F[x + 1][0... l - 1] should be increased by 1 (since at the moment of shot in point s < l the duck [l, x + 1] can't be killed yet). From the other hand, all values F[x + 1][l... x + 1] remain the same since the last shot kills the newly added duck.

Now let's understand how to implement all this stuff. Function F[x][·] is piecewise constant, so it can be stored in a Cartesian tree as a sequence of pairs (beginning of segment, value on segment). Such storage allows us to easily add 1 on prefix and take minimum on prefix of a function.

Now let's think that F[x][·] is defined on all posistive values but the values F[x][s] for s > x do not satisfy the definition of F[x][s] above. In other words, let's just suppose that the lats segment in structure F[x] is infinite in right direction.

Let's sweep with the variable x. The function F[x + 1][·] changes in comparsion to F[x][·] very rarely For example, the value F[x + 1][x + 1] is almost always the same as F[x][x + 1] (that is equal to F[x][x] as said above). Indeed, if we suppose that there is no duck ending in x + 1 then F[x][x] = min(F[x][0... x - r]) and F[x + 1][x + 1] = min(F[x + 1][0... x + 1 - r]) = min(F[x][0... x + 1 - r]) ≤ min(F[x][0... x - r]). So, there is an interesting event only if value F[x][x - r + 1] is smaller than the whole prefix before it. On the other hand, the value min(F[x][0... x - r]) can't increase more than n times by 1 (each time when we pass through the right end of the duck) and so, it also can't decrease more then n times (since it is a non-negative value).

So, the events "we passed through the right end of the duck" and "we should non-trivially calculate F[x][x]" are in total linear. Each of them can be processed in O(1) operation with Cartesian tree, that gives as totally an solution. Whooray!

542C - Idempotent functions

In order to solve this task it's good to understand how does the graph corresponding the function from {1, ..., n} to itself looks. Let's consider a graph on vertices 1, ..., n with edges from vertex i to the vertex f(i). Such graph always looks like a set of cycles with several trees leading to that cycles. How should the graph look like for function to be the idempotent? It's easy to see that in such graph all cycles should be of length 1 and all vertex that are not cycles of length 1 (i. e. all not fixed points) should immediatly lead to some fixed point.

So, we should satisfy two conditions. First, all cycles should become of length 1 — in order to do that k should be divisible by lcm(c1, c2, ..., cm) where ci are the lengths of all cycles. Second, all vertices not lying on cycles should become leading to the vertices lying on cycles. In other words, k should be no less than the distance from any vertex x to the cycle it goes into (or, that the same, the length of pre-period in the sequence f(x), f(f(x)), f(f(f(x))), ...).

So, are task is about finding the smallest number k divisible by A that is no less than B, it is not hard at all.

Challenge. What is the maximum possible answer for this task? (Answer: first second)

542D - Superhero's Job

First step is to understand the properties of a Joker function. It's important property is that it is multiplicative: J(ab) = J(a)J(b) for (a, b) = 1, so we can write the value of function knowing the factorization of an argument: J(p1k1p2k2... pmkm) = J(p1k1)J(p2k2)... J(pmkm) = (p1k1 + 1)(p2k2 + 1)... (pmkm + 1). Let's use this knowledge in order to solve the task with dynamic programming.

Let's denote as P the set of prime p such that the multiple including it may appear in A = J(x). There are not that many such primes: each divisor d of number A can correspond no more than one such prime, namely, the one whose power the number d - 1 is (if it is a prime power at all). Let's calculate the set P and also remember for each prime number p in it in which powers k the value (pk + 1) divides A.

Now we can calculate value D[p][d] that is equal to the number of ways to get a divisor d of a number A as a product of brackets of first p primes in set P. Such value can be caluclated by using dynamic programming in time where is the number of divisors of A (as it was shown above that ). So, overall complexity of the solution is .

Challenge. How the behaves when A increases? What is the maximum values of over all A ≤ 1012? (The answer: . Nice estimate that is not an exact asymptotic, though, is that )

Challenge. What is the maximum answer in this task? If you are able to create a test with answer larger than million, a great respect from me!

542E - Playing on Graph

First, if the original graph isn't bipartite then the answer is (-1). Indeed, any odd cycle, while being contracted by the pair of vertices, always produces an odd cycle of smaller size, so at some point we will get a triangle that blocks us from doing anything.

From the other way, each bipartite component can be contracted in order to get a chain whose length is a diameter of the component. Suppose that the pair of vertices (a, b) is a diamater of some connected component. Then, by contracting all vertices located on the same distance from a we can achieve the chain we want.

The last step is that the answer fror the original graph is the sum of the answers for all the connected components since we can attach all of them together. So, the answer is the sum of diameters of all connected components if all of them are bipartite, otherwise answer is -1. Solution has the complexity O(E + VE) (The first summand is checking for being bipartite, the second one is calculation diameters by running BFS from each vertex).

542F - Quest

This task can be solved in lot of ways. The most straightforward is DP. The task can be seen in the following way. We want some set of vertices as leaves and for each potential leaf we know the upper bound for its depth and its cost.

Let's sweep over the tree from down to up. Let's calculate the value D[h][c] that is the maximum possible cost that we can achieve if we stay on the level h and have c vertices on it. For transition let's fix how many leaves of the deepness exactly h we will take (it's easy to see that among them we should task several greatest). Suppose we will take k of them. Then from this state we can move to D[h - 1][⌈(c + k) / 2⌉]. The answer will be located in D[0][1] because when we are on the level 0 we should have the only vertex that is the root of the tree.

The complexity of such solution is O(n2T).

Challenge Improve the solution above to and then to

Read more »

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