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(n²), 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: vintage_Vlad_Makeev

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?