139A - Petr and Book

If the total number of pages doesn't exceed the number of pages for Monday, the answer is Monday. Otherwise we can substract the Monday number from total and go on to Tuesday. If Tuesday isn't enough, we subtract and continue to Wednesday, and so on. We are sure that no more than N weeks will pass, as at least one page is read every week. Complexity - O(N).

139B - Wallpaper

Unluckily, the translated statement was quite tough even tougher to understand than the original statement.

Say we fixed the roll type and the room. The only possible way to cut the roll is to cut it into vertical stripes with length equal to room's height (though it was said we can cut it any way we want, there were some conditions to fulfill, namely there could be no joints other than vertical). So we find the total width of stripes we can cut our roll into as the (length of the roll / height of the room) (rounded down) * (width of the roll). If the roll length is smaller than room height, we obviously can not use this type of rolls (though the statement said there must exist at least one type we can use). The number of rolls is (perimeter of the wall rooms) / (total stripes width) (rounded up).

Then we just try all types for every room and sum the minimal costs. Complexity - O(MN).

139C - Literature Lesson

138A - Literature Lesson

The hardest part is to check whether two lines rhyme or not.

We have to check the suffixes starting in K-th vowels from the ends for equality. Notice that if a line has less then K vowels, it can NOT be part of any rhyme (even with the identical string).

To check this we can use two pointers running from two ends simultaneously, or use some built-in functions for taking substrings (like s.substr(...) in C++).

Now, let us take three boolean variables: aabb, abab and abba. Each one says if every quatrain we have seen before satisfies the corresponding type of rhyme. To support them, for each new quatrain we must check for rhyming every pair of lines it and change variables if needed.

If at the end of the poem all variables are set to TRUE, then the type is aaaa. If all of them are FALSE's, then the answer is NO. Otherwise exactly on of them is TRUE, and answer is clear. 

Complexity - O(S), where S is the sum of all lines' sizes.

139D - Digits Permutations

138B - Digits Permutations

It turned out to be surprisingly hard, possibly because of lots of cases to think of.

How to determine the number of zeros at the end of the sum of two numbers? First we skip all the positions from the end where both numbers have zeros. If on the next position the sum of digits is not 10, that's it. If it is, we go on while the sum of digits is 9.

Now we take two transitions of digits in N. Let's fix the number of common zeros at the end of both transitions. If, moreover, we fix the digits that sum up to 10 at the next positions, we can find the maximal number of zeros to get with the remaining digits as min(a₀, b₉) + ... + min(a₉, b₀), where a₀, ..., a₉ are the quantities of every remaining digit in the first transition after taking out the last zeroes and the digit for the 10-sum, and b₀, ..., b₉ are the same numbers for second transition (initially these quantities are equal to quantities of digits in N).

So, if we store a₀, ..., a₉ and b₀, ..., b₉, and then run through the numbers of common zeros at the end and the 10-sum digits, we determine the maximal zeros number (and configuration giving that answer) in O(10 * 10 * N) = O(N) time. Getting the transitions now is easy - we build them from right to left according to the saved answer.

The most common mistake was to think that maximal number of zeros at the end gives the maximal answer. It was disproved by 4-th pretest - 1099. As we can see, the optimal configuration is 1901 + 1099, giving three zeros, which cannot be achieved by placing both zeros at the ends.

139E - Mushroom Gnomes - 2

138C - Mushroom Gnomes - 2

First of all - the answer is the sum for all mushrooms of the probabilities of not being destroyed multiplied by that mushroom's power. That is a simple property of random variables' means.

So we come to the equivalent statement: we still have mushrooms, but now instead of trees we have a family of segments with probabilities arranged to them. Every segment "exists" with this probability, otherwise it doesn't, and all these events are independent. We want to count the sum of probabilities (with weights) for each mushroom not to lie in any "existing" segment. (Note that we can reformulate the statement this way because any segments containing any fixed point are truly independent: they can't belong to the same tree. Thus the probability to survive for any point in this statement is equal to the probability for this point in the original statement).

Now, how do we count this? There are several ways:

1) "Scanning line". If we go from left to right, we can meet three kinds of events: "the segment i started", "the segment i finished", "the mushroom j found". We can easily support the probability of current point being covered by "existing" segment if we multiply it by segment's probability when we find its beginning and divide by it if we find its end. If we find a mushroom by the way, we can add the known probability to answer (multiplied by its power). To perform the above trick we just sort the array of events by x-coordinate and iterate over it.

This solution is good in theory, but in practice it has a flaw: if the number of segments is large, after multiplying lots of real numbers less then 1 we can exceed the negative explonent of the real type used, and thus get a 0 in a variable instead of desired value. And after any number of divisions it still would be 0, so we couldn't get any sane answer anymore.

This trouble can be resolved in several ways (without changing the solution much):

a) We can have no more than 101 distinct values of probabilities for segments. So, if we store an array for quantities of segments containing current point and having a corresponding probability, we just add and substract 1's from array's elements. When we find a mushroom we find the product of degrees with exponents stored in array, spending ~100 operations.

b) We can store a set of segments containing current point. Every operation with set works in O(log N) time, and iterating over the whole set works in O(N) time. So, upon meeting mushroom we iterate over set and multiply the probabilities for all segments in it.
The next thing that helps us is that we can drop the answer for current mushroom if it's too small. If we don't store the segments with probability 1, the most number of segments which probabilities' product more than 1e-8 is about 2000 (since 0.99 ^ 2000 < 1e-8). So we can count everything in time.

c) If we use logs of probabilities instead of themselves, we have to add and substract them instead of multiplying and dividing. This way we won't encounter any precision troubles.

2) Segment tree.

Let's sort the mushrooms by their coordinates. Let's also assume we have some set of segments and already counted the desired probabilities. And now we want to add a new segment to the set. What will change? The probabilities of mushrooms lying in this segment (and thus forming a segment in the array) will multiply by segment's probability.
Now it's clear we can use multiplication segment tree (or simple addition segment tree if we use logs again) to perform the queries for all segments and then sum up the elements in the end.

About the strange score and pretest: we discovered the trouble with precision quite late, and realized that it makes the problem way harder ('cause it's hard to predict during writing and submission phases). What's worse, it won't show itself on the small tests. So we decided to "show up" the test and let the contestants solve this additional problem, for additional score. (However, not all solutions from above list do actually deal with this problem. Unfortunately, we didn't came up with them beforehand.)

138D - World of Darkraft

Notice that the game can be separated into two independent: for only even and only odd coordinate sum cells. The player chooses the game he would like to make a move in. Thus, if we find a Grundy function for each of this games we can find the whole game result.

Now let's observe only even cells, for instance. We can prove that every diagonally connected piece formed during the game is constructed as the intersection of the field rectangle with some diagonally oriented semi-planes, with exactly one semi-plane for every orientation. Let's enumerate every possible edges of semi-planes, which obviously are some diagonals of the grid. Now we have an enumeration of all possible pieces - by four diagonals being "edges" of this piece.

Now we want to count the Grundy function for some piece. To do this we iterate over all cells in this piece and find XORs of all Grundy functions of pieces formed by making a move in each cell, then find a minimal exclused non-negative number of this set (see the page on the Sprague-Grundy theorem above). All these pieces are smaller than current, so we can use the DP to count the functions. To easily iterate over cells in the piece we can iterate over numbers of two diagonals the cell lies on (going right-and-upwards and right-and-downwards), as we have exactly the bounds on their numbers as the parameters of the piece. For each case of diagonals we also have to check if the piece is inside the field.

So we have counted the Grundy functions for even- and odd-numbered cells separately. If they are equal, the answer is "LOSE", otherwise it's a "WIN" (see the theorem again).

Complexity - O((n + m)⁴ (number of pieces) mn (number of pieces inside one piece and counting MEX)).

138E - Hellish Constraints

The most interesting problem. =)

Let's start with the case when we have only one constriction - "c l r". For a string s let's count an array A with a length equal to s's. A[i] = 1 if the suffix of s starting at position i satisfies the condition, and A[i] = 0 otherwise.

So, we have s and already counted A. What happens if we write another symbol c' at the of s? Let s' = s + c', A' = A(s').

If c' ≠ c, than the part of A' corresponding to everything beside the last symbol does not change. The last element is 1 or 0 depending on the condition (it's easy to count).

If c' = c, some elements of A might change. Let's denote the i-th occurence of c in s' counting from the end as p_i(c) (symbols and occurences are enumerated from 1). If there are less then i occurences, p_i(c) = 0.

It's easy to see that elements from A'[p_l + 1(c) + 1..p_l(c)] are incremented by 1, and elements from A'[p_r + 2(c) + 1..p_r + 1(c)] are decremented by 1. It's also clear that as we add the symbols these invervals won't intersect for l and r separately (that is, every A[i] will be incremented and decremented not more than one time each).

Now we can have more then one constriction. We count B[i] as the number of constrictions the suffix starting at i-th position satisfies. Clearly, B[i] is the sum of A[i]'s for all constrictions. Also, we support the variable C - number of i-s that satisfy L ≤ B[i] ≤ R.

Similarly, we add symbols one after another and change B[i]. To do that, we must consider all the constrictions concerning new symbols and change the numbers in the intervals mentioned above. Changing the numbers is just iterating over symbols in the mentioned intervals and incrementing/decrementing B[i]'s (this procedure also lets us to support C effectively). As the intervals for each constriction do not intersect, we will not change any B[i] more than twice for each constriction, so the number of operations concerning any constriction is O(n), giving total number of operations O(nk). To get the answer, we just sum up C's states after adding every symbol (as every substring will be a suffix of some prefix exactly one time).

To find borders of every interval used (in which the B[i]'s are changed) we can enumerate all occurences of every symbols and count the borders easily, knowing how many times every symbol occured. The other way to do that is to keep two pointers for each constriction, showing where last intervals ended. On the next occurence we move these pointers to next occurences of corresponding symbol (however, we need to handle the case when not enough symbols have occured to changed B).