Codeforces Round #879 Editorial

First, let's make the sum of the array elements . To do this, we just need to change some to . The number of such replacements can be calculated using a formula or explicitly simulated.

After that, there are two possible situations: either the product of all elements is equal to , or the product of all elements is equal to . In the first case, we don't need to do anything else. In the second case, we need to replace one more with (note that in this case the sum will remain ).

Let's add leading zeros to if necessary. Now we can represent the numbers and as their longest common prefix, the digit at which the values differ, and the remaining digits. After digit , any digits can be placed, so it is advantageous to put in one number and in the other. Then the answer is equal to . For example, it is achieved with numbers and .

Let's show that the specific choice of a turn by Bob (which of the strings to reverse) does not affect Alice's strategy and therefore the answer to the problem.

Reversing the string twice does not change anything we are only interested in the parity of the number of reverses for both strings.

If Bob made an even number of moves in total, then the parity of the number of moves made by Bob with string coincides with the parity of the number of moves made by Bob with string pairs of characters at the same indices, after all reverses, will be , possibly in reverse order, but it doesn't matter. Here and are the original indices of the strings, which do not change with reversing.

If Bob made an odd number of moves, then exactly one of the strings will be reversed, and the pairs of characters in the same indices will be: (or in reverse order).

That is, the specific pairs of corresponding characters are determined only by the parity of the total number of moves made by Bob, and it does not matter which specific moves were made.

Therefore, Alice can choose one of two strategies:

• Make , and fix the end of the game when the number of moves made by Bob is even.
• Make , and fix the end of the game when the number of moves made by Bob is odd.

Let's count  — the number of indices where and differ, and  — the number of indices where and differ.

For the first strategy, Alice must make at least moves herself, and it is also necessary that the number of moves made by Bob is even it is easy to see that for this strategy the game will last moves.

For the second strategy, everything is roughly similar: the game will last moves, but the case needs to be handled separately.

And the answer to the problem will be the minimum of these two values. Asymptotic: .

Let's fix the students who will end up with the highest and lowest hands. Then, to maximize the difference, we can ask all the topics that the student with the highest hand knows. Then the second student will raise his hand for each topic in the intersection of their segments, and lower for each topic that only the first student knows. That is, the problem is to find segments and such that the value of is maximal, since the answer is .

The segment can intersect the segment in four ways: intersect the beginning of , intersect the end of , be completely inside , or not intersect it at all. So, if in the answer segment intersects the beginning of , then you can choose the segment with the minimal right end as the segment  — the intersection of such a segment with will be no greater than the intersection of with . Similarly, for the right end, you can select the segment with the maximal left end. If the answer has one segment in another, then you can consider the shortest segment in the set as the inner segment. If the segments in the answer do not intersect, then the segment does not intersect one of the "edge" segments.

Thus, to find the segment with which it has the minimum intersection for a given segment, you need to check 3 candidates: the shortest segment in the set, the segment with the minimal right end, and the one with the maximal left end. In total, to find the answer, you need to check pairs of segments.

Notice that the MEX of numbers will not exceed . Let's calculate all possible LCM values on segments that do not exceed . To do this, we will iterate over the right endpoint of the segments and maintain a set of different LCM values on segments with such a right endpoint.

Let these values be . Then , indeed, for each , it is true that is divisible by , and therefore , that is, , from which the required follows. That is, the values can be stored naively in some dynamic array. Now suppose we want to move the right endpoint, then the array should be replaced by and remove values greater than from the new array, as well as get rid of duplicates.

All these actions can be performed in time, after which we just need to find the MEX among the known set of values. This solution can also serve as proof that the desired MEX does not exceed , which is less than under the constraints of the problem. Thus, initially, we can only maintain numbers less than and not worry about overflows of a 64-bit integer type.

Let's solve the problem if there are no requests. The key object for us will be such cells that the number in them is less than the cell index. Note that for one carriage reset, we can transfer no more than one such number. So we have a lower bound on the answer.

Let's build a graph with edges . Then it will break up into cycles. Let's find the first position where , take a number from this position, shift it to , take a number from position , and so on. Then we will put the whole cycle in its place. How many carriage drops will there be? Exactly as many edges as there are such that . That is, the answer is exactly equal to the number of positions where .

Let's learn how to solve for shifts. Let's find for each cell such positions of the beginning of the array that it will satisfy in this configuration. It is easy to see that for a particular cell, such indexes will form a segment (possibly a prefix + suffix). Let's create a separate array and add one on these segments. Then in the i-th position there will be an answer if the array starts from the i-th cell.

Now let's solve for an array flip. It is easy to see that for this you can simply maintain the entire previous structure, but with the inverted original configuration of cells. Asymptotic: .