Codeforces Round #802 Editorial

Let's notice that the optimal path looks like the following: . The proof is relatively easy — all paths from to consist of cells and in the optimal path we have minimized all numbers in the path. The cost of such path is equal to . This sum can be found in by just summarizing all numbers, or it can be found in if you remember that .

Let X be the number in input. Consider two cases: first digit of X is 9 and not 9.

If the first digit of input number is not 9, we can simply output 9999...999 ( digits) - X.

If the first digit is 9, we can output 111...1111 ( digits) - X. It is easy to show that this number will be exactly -digit.

To simplify implementation, we can first find 9999...999 - X by subtracting all digits of X from 9, and than if this number is not -digit, add 111...1111 - 9999...999 = 11111...1112 to it.

Overall complexity will be .

Consider the difference array . Note that for it is necessary to make subtractions on the suffix. For , you need to make subtractions on the prefix. Let's add them to the answer. Let's calculate the final array using prefix and suffix sums for . Note that it will consist of the same numbers. Add to the answer, where is the resulting number.

To begin with, we note that it makes sense to open only some pipe prefix, because we need to fill all the locks, and more left pipes affect the total volume of the baths, which is obviously beneficial. Let's enumerate how many pipes we will open, namely which prefix of pipes we will open and calculate - how long it will take to fill the first locks if the first pipes are open. Let's introduce an auxiliary array - the sum of the capacities of the gateways on the prefix . Then . Let's see why this is so. We need all gateways on prefix to be filled, and also that the -th gateway be filled. Note that if the -th gateway does not have time to fill up in the time , then it will fill up in the time (filling will occur at the time , but since in the condition we are asked about integer times, we can round up and not use real arithmetic), it turns out when the required amount of water is poured into all the locks in total from all pipes. Now knowing for all open we can similarly calculate when all n gateways are full. For this will be . It is also obvious that when an additional pipe is opened, the time will not increase, therefore we can do a bin search by time and find out the answer for the desired request. If the request is less than the minimum filling time for the locks (when all pipes are open), then you need to print . Total running time O().

We need to find a simple criteria of a solvable puzzle. It can be shown that for every cell, except cell with value , it should have a neighbour with a smaller value. Indeed, if the puzzle is solvable, a cell going before the first occurence of our cell always has the smaller value. Conversely, if each cell has a smaller neighbor, one can list cells one at a time, and there will always be a path to the next cell along already visited cells with lower numbers.

Let's call a cell bad, if it's value is not and it doesn't have a neighbour with a smaller value. Consider any bad cell. Let's notice, that the pair that we swap should contain either the bad cell itself, or its neighbour, otherwise that bad cell will stay bad. That way we have pairs of candidates, for each of which we'll run a check if the resulting puzzle is solvable.

Now we'll learn how to quickly understand, if the puzzle became solvable after a swap. For this we'll keep the amount of bad cells. After the swap, the state can be changed only for these cells and their neighbours. Let's recalc the amount of bad cells and check if it's zero.

The resulting complexity is

We are asked to find a minimum cost perfect matching between 's in the matrices, where the cost between and is . Notice that the answer exists only if the number of 's is equal in both matrices. Consider that this is the case.

Notice that every either stays in its original row or changes it in a single operation. For simplicity let's assume that all operations of that kind are performed in the beginning. Let's denote as the difference between the -th prefix sum in -th row of the matrices. If the final row for each is fixed, then the answer is equal to , where in the number of 's that changed its row.

Now let's look at what happens when we change the row of a . For simplicity let's assume that it was in a cell . Then after the swap we have to increment by , decrement all by , and increment all by .

Now let's solve the following problem: we are given and and in one operation we can increment some suffix by and decrement the same suffix in the other array by . The goal is to minimize .

Notice that the following greedy algorithm works: iterate through columns from left to right and while and have different signs, decrement the suffix of one that's greater and increment suffix of one that's lower.

Now let's prove that this algorithm minimizes the target sum. For this consider some optimal sequence of operations. It doesn't matter in which order operations are performed, so let's assume they are performed from left to right, and are accumulated in a single element for the same suffix. If the sequences differ, denote as the first such position. Note that before that all and are the same in both our answer and the optimal one. Suppose that in the optimal answer we incremented -th suffix of by and decremented -th suffix of by . Then the target sum will increase by .

Consider the following cases:

• and or and . By triangle inequality , which means that those operations could be performed on the -st suffix and that wouldn't increase the answer.
• and . Here if , , which means that those operations could be performed on the -st suffix and that wouldn't increase the answer. Now if . We can assume that , otherwise we will perform an operation on values with the same sign, which we already shown can be done later on. Then . Greedy algorithm suggests doing exactly operations. Note that if we perform operations on suffix and operations on suffix , we will add to the answer and get the same state as the optimal answer. This means that we can do operations and not increase the answer.
• and . This case can be analyzed in the same way.

Let's come back to the original problem. Described greedy algorithm finds a lower bound on the answer. Let's show that it is always possible to achieve it when the operations are allowed only for moving 's between rows and the number of s in each row at the end should be the same. For this note that we can "perform" operations on 's from the second matrix, if we reverse their order and append to the end of the sequence for the first matrix. Now note that if on some prefix and have the same sign, but on prefix the signs differ, there has to be at least a single in column , and we can perform the operation suggested by the greedy algorithm. Finally, if the answer exists it is true that , and if and have the same sign at the end this means that they are both , which means that the constructed answer is correct.

This solution works in time.