Codeforces Round #829 Editorial

Let's process each character of the string from left to right and store the number of unanswered questions . Initially this value equals to zero. Consider the -th character of the string. If it equals to "Q", increase by one. If it equals to "A", decrease by one. If has become negative, it means that some of the questions was answered several times. In this case let's assign zero to .

If will be equal to zero after processing all string, then all questions were answered, and the answer is "Yes". Otherwise, the answer is "No".

Time complexity: for each test case.

Let's prove that the minimum difference of consecutive elements is not greater than . To do it, let's prove that larger value is not achievable. Consider element of a permutation with value . It will have at least one adjacent element in the constructed permutation. And the maximum absolute difference of this element with the adjacent elements is at most .

Now we will construct the permutation with the minimum absolute difference of consecutive elements equals to . Assign . Now we can construct such permutation: . It's easy to see that the minimum absolute difference of consecutive elements equals to .

If the sum of all elements of the array is odd, the partitions does not exist because the partition does not affect the parity of the sum. Otherwise the answer exists.

Let's build such construction. As the sum of all elements is even, is even too. Consider pairs of elements with indices , , ..., . Consider the pair . If , add the segment to the answer. In this case the alternating sum of elements of this segment will be equal to . Otherwise we will add two segments to the answer: and . The sum of the first segment is , and the sum of the second segment is . The sum of two sums will be equal to zero. So the sum of all alternating sums will be equal to zero.

If the sum of all numbers in the array is odd, then splitting is impossible, because splitting does not affect the evenness of the sum. Otherwise, we will build the answer constructively. Suppose we have considered some kind of array prefix. Let's keep going until we get exactly non-zero numbers.

We want to make these two non-zero numbers add up to . Then if on the last segment the sum is already equal to , then just take it as an answer. Otherwise, consider a few cases:

• If the length of the segment is even, then we simply separate the last number (it will be non-zero) into a separate segment. Then its sign will change and in total these two numbers will give .
• The same can be done if the length of the segment is odd, but its first element is equal to . Separate this and repeat the algorithm above.
• If the length of the segment is odd and the first element is not equal to , then we separate it. Then the value of the first element will not change, and the last will change to the opposite, and then their sum will be equal to .

Let's create an array where equals to number of elements equals to in the initial array.

Note that equals to sum of over all from to , does not affect anything because divides itself. We have to check if this sum is divisible by .

Suppose there exists some such that . In this case we can make two transformations: and the sum of will not change because .

Let's perform this operation until it is possible for all numbers from to . After all operations the sum of will not change and for each the inequality will be satisfied because if we could perform an operation with this element.

Let's see what is the maximum value of sum of over all from to after all operations. We know that for all , so the maximum value of the sum is the sum of over all .

Note that .

It means that the sum of such values over all from to equals to . Each factorial from to will be added and subtracted from the sum. So the result is .

So the only one case when this sum is divisible by is when the sum equals to . It means that equals to zero for all from to after performing all operations.

Time complexity: .

Let the number of zeros in the array be . Let be the expected number of swaps needed when there are zeros in the first positions. Then, we know that , and we can write down the recurrence equations for by considering the case where some element equals to one from the first positions and some element equals to zero from the last positions are swapped.

This is the only case where the value will change. Thus, our recurrence is as follows.

Let . Then .

The answer is , where is the initial number of zeros in the first positions.

Let's paint our field in a chess coloring.

Now let's consider our operations not as the movement of sunbeds, but as the movement of free cells. Then, a free cell adjacent to the long side of the sunbed can move to a cell of the sunbed that is not adjacent to this one, for units of discomfort. A free cell adjacent to the short side of the sunbed can move to a cell of the sunbed that is not adjacent to this one, for units of discomfort. Note that in this cases, the free cell does not change its color (in chess coloring).

Since each sunbed should occupy one black and one white cell, then some two free cells of different colors should move to neighboring ones using operations.

It can be shown that in the optimal answer we use no more than one operation with each sunbed.

Then, for each position, looking at the adjacent sunbeds, we will determine where the free cell can move if it turns out to be in this position. Let's construct a weighted oriented graph on the cells of the field. Edge of weight (equal to or ) will mean that there is a sunbed such that by moving it with an operation that brings discomfort, we will free the cell and block the cell .

Note that the graphs on the black and white cells are not connected. Let's run Dijkstra's algorithm from all free cells at once. Then, for each cell - the minimum distance in this graph from a free cell is equal to the minimum amount of discomfort that must be used to free this cell.

The answer to the problem is the minimum for all pairs , neighboring cells, . Or if there is no pair of adjacent cells, both of which are reachable from the free ones.

Asymptotics of the solution:

Let bi the maximum value of the resulting product before any movements. The problem statement says that it is guaranteed that .

• Observation 0 — after each movements the value of the resulting product is not greater than .
• Observation 1 — each machine of kind should be moved to the end of the sequence, and each machine of kind  — to the beginning of the sequence, and the order of movements does not make sense.
• Observation 2 — there are at most non-trivial machines of kind (such machines that ). We will need some more strong observation for machines of kind , but this will be useful too.
• Observation 3 — if there are two machines , , where and , then in optimal answer machine may be moved if and only if machine is moved too. It is true because we could increase the answer otherwise, by moving machine instead of machine .

The last two observations says that there are not many subsets of machines of kind (that satisfies the property from observation 3). Let's say that there are such subsets, in the end of the editorial we will estimate this value.

Let's pick out subsegments of machines of kind between machines of kind , sort them and count prefix sums. There will be not more than such segments. In the optimal answer some maximums will be moved from each of the segments.

Let's fix some subset of machines of kind , that will be moved to the end, and count the current value of the output product. Consider some element in the array. Let the product of machines to the left of it be , and to the right of it — to be . Now if we move this element to the beginning of the array, the value of the resulting product will increase by . Let's call this . Now we have to find the sum of some numbers of maximum values .

Let's use binary search to find some "critical" value : such value that all elements will be moved to the beginning. of each element is not greater than . Inside binary search we have to iterate over all segments of elements and find the number of elements with inside this segment using binary search. We have to check if we can to move the selected amount of elements to the beginning of the array to understand how to move borders of the external binary search.

After we find the critical value , let's iterate over all segments and add the sum of elements that are to the answer. Separately let's consider elements with = . We could move some of them to the beginning too. Let's update the answer with this value.

Time complexity: . It should be noted that this estimate is actually higher than in fact.

Let's estimate the value now:

• Consider some sequence , such that and
• Sort it by ascending,  — the product of elements will not change and the number of "interesting" subsets will not become smaller.
• Replace all the smallest elements of the sequence with , the second minimums with and so on. If there are smaller number of elements equals to than elements equals to and , let's swap their numbers. Now the number of interesting subsets is not changed, is not increased. The sequence looks like now.
• The number of interesting subsets in the new sequence equals to , where is the number of elements if sequence equals to .
• (Let's run the code that will brute-force over all sequences of such kind and see that the number of interesting subsets is , which is achieved on sequence )
• Let's continue estimating this value "fairly": the elements of the sequence do not exceed because . Let's replace each number with a prime number corresponding to it by order: and replace all elements with . The product of elements will increate in at most times, so the product will not exceed . It is easy to check that the maximum is achieved in , so the product is not greater than .
• The number of interesting subsets of our sequence does not exceed the number of divisors of received numbers that can be estimated as

Let's formalize the problem condition. It is required to calculate the number of squares in the table for which we have inequality , where is a of positive integers in the sqare and is a of absolute values of all negative integers in the square. Then we denote cost of a square as . Note that when the square is expanded, its value cannot decrease.

Let's fix the diagonal that contains the upper left and lower right sides of the square. Now, with a fixed lower right cell, we want to maintain the upper left cell of the square that is maximally removed from it so that its cost does not exceed . Note that this upper-left boundary can only shift in the direction of moving the right lower one, which means we can use the two pointers technique.

We will also need to maintain a set of numbers that are contained in a square. To do this, we will process each cell separately, which are added and removed from our square. Note that for each cell there are no more than diagonals on which it is possible to construct a square containing this cell, and also note that due to the structure of our solution for each such diagonal, our cell will be added to the set no more than time. Thus, the total number of additions of cells to our set does not exceed , and accordingly the total number of additions of numbers to the set does not exceed .

We will also need to find out the of all positive integers in the square, as well as the of absolute values of negative integers in the square. Here we need to make another observation about our algorithm. The number of queries will not exceed . That is, you can use the square roots technique to adding and removing integers in time, and find out the values in time.

To summarize, our algorithm will work in asymptotic time:

As the author of the problem, I want to apologize for the very low TL in this problem. Due to the specificity of the task, it was difficult to cut off the wrong solutions. The solution described above, if implemented correctly, fits into TL with a time reserve at least second. But if suddenly you didn't write it efficiently enough and you have TL, then you can try using the following tips:

• Sort the numbers in each cell. This will help to better in the cache. It does benefit buffering provided by a cache.
• It is more accurate to implement your algorithm without making unnecessary MEX queries.
• Use bit magic and implement the search in time where is machine word size. Such a solution may have a better time-constant and it is better to be vectorized