779A - Pupils Redistribution

Problem setter: MikeMirzayanov

To solve this problem let's use array cnt[]. We need to iterate through first array with academic performances and for current performance x let's increase cnt[x] on one. In the same way we need to iterate through the second array and decrease cnt[x] on one.

If after that at least one element of array cnt[] is odd the answer is  - 1 (it means that there are odd number of student with such performance and it is impossible to divide them in two. If all elements are even the answer is the sum of absolute values of array cnt divided by 2. In the end we need to divide the answer on 2 because each change will be counted twice with this way of finding the answer.

779B - Weird Rounding

Problem setter: MikeMirzayanov

To solve this problem we need to make k zeroes in the end of number n. Let's look on the given number as on the string and iterate through it beginning from the end (i.e. from the low order digit). Let cnt equals to the number of digits which we reviewed. If the current digit does not equal to zero we need to increase the answer on one. If cnt became equal to k and we reviewed not all digits we need to print the answer.

In the other case we need to remove from the string all digits except one, which equals to zero (if there are more than one such digit we left only one of them). Such digit always exists because the problem statement guaranteed that the answer exists.

779C - Dishonest Sellers

Problem setters: MikeMirzayanov and fcspartakm

To solve this problem we need at first to sort all items in increasing order of values a_i - b_i. Then let's iterate through sorted array. If for the current item x we did not buy k items now and if after discounts it will cost not more than now, we need to buy it now and pay a_x, in the other case we need to buy item x after discounts and pay b_x.

778A - String Game

Problem setter: FireZi

In this problem we have to find the last moment of time, when t has p as a subsequence.

If at some moment of time p is a subsequence of t then at any moment before, p is also its subsequence. That's why the solution is binary search for the number of moves, Nastya makes. For binary search for a moment of time m we need to check, if p is a subsequence of t. We remove a₁, a₂, ... a_m and check if p is a subsequence greedily.

778B - Bitwise Formula

Problem setter: burakov28

Note that changing i-th bit of chosen number doesn't change any bits of any of the variables other than i-th one. Also note that the total number of values is greater, as more variables have 1 at i-th position.

Let's solve for every bit independently: learn, what is the value of i-th bit of chosen number. We can try both values and simulate the given program. Choose one of the values that makes more variables to have 1 at i-th position. If both 0 and 1 give equal number of variables to have 1 at i-th position, choose 0.

778C - Peterson Polyglot

Problem setters: niyaznigmatul and YakutovDmitriy

While erasing letters on position p, trie changes like the following: all the edges from one fixed vertex of depth p are merging into one. You can see it on the picture in the sample explanation. After merging of the subtrees we have the only tree — union of subtrees as the result.

Consider the following algorithm. For every vertex v iterate over all the subtrees of v's children except for the children having largest subtree. There is an interesting fact: this algorithm works in in total.

Denote as s_x the size of the subtree rooted at vertex x. Let h_v be the v's child with the largest subtree, i.e. s_u ≤ s_hv for every u — children of v. If u is a child of v and u ≠ h_v then . Let's prove that.

1. Let . Then and .
2. Otherwise, if , then we know that s_u + s_hv < s_v. Therefore, .

Consider vertex w and look at the moments of time when we have iterated over it. Let's go up through the ancestors of w. Every time we iterate over w the size of the current subtree becomes twice greater. Therefore we could't iterate over w more than times in total. It proves that time complexity of this algorithm is .

Solution:

1. Iterate over all integers p up to the depth of the trie
2. For every vertex v of depth p
3. Unite all the subtrees of v with running over all of them except for the largest one.

How to unite subtrees? First method. Find the largest subtree: it has been already built. Try to add another subtree in the following way. Let's run over smaller subtree's vertices and add new vertices into respective places of larger subtree. As the result we will have the union of the subtrees of v's children. All we need from this union is it's size. After that we need to roll it back. Let's remember all the memory cells, which were changed while merging trees, and their old values. After merging we can restore it's old values in reverse order.

Is it possible to implement merging without rolling back? Second method. Let's take all the subtrees except for the largest one and build their union using new memory. After that we should have two subtrees: the largest one and the union of the rest. We can find size of their union without any changes. Everything we need is to run over one of these trees examining another tree for the existence of respective vertices. After this we can reuse the memory we have used for building new tree.

778D - Parquet Re-laying

Problem setter: pashka

Let's assume that the width of the rectangle is even (if not, flip the rectangle). Convert both start and final configurations into the configuration where all tiles lie horizontally. After that, since all the moves are reversible, simply reverse the sequence of moves for the final configuration.

How to obtain a configuration in which all tiles lie horizontally. Let's go from top to bottom, left to right, and put all the tiles in the correct position. If the tile lie vertically, then try to turn it into the correct position. If it cannot be rotated, because the neighboring tile is oriented differently, proceed recursively to it. Thus, you get a "ladder", which can not go further than n tiles down. At the end of the ladder there will be two tiles, oriented the same way. Making operations from the bottom up, we'll put the top tile in a horizontal position.

778E - Selling Numbers

Problem setters: niyaznigmatul and VArtem

Because the target value for this problem is calculated independently for all digits, we'll use the dynamic programming approach. Define dp_k, C as the maximum possible cost of digits after we processed k least significant digits in A and C is the set of numbers having the carry in current digit. This information is sufficient to choose the digit in the current position in A and recalculate the C set and DP value for the next digit.

The key observation is that there are only n + 1 possible sets instead of 2ⁿ. Consider last k digits of A and B_i. Sort all the length-k suffixes of B_i in descending lexicographical order. Because all these suffixes will be increased by the same value, the property of having the carry is monotone. That means that all possible sets C are the prefixes of length m (0 ≤ m ≤ n) of this sorted list of suffixes. This fact allows us to reduce the number of DP states to O(n·|A|). Sorting all suffixes of B_i can be accomplished using the radix sort, appending the digits to the left and recalculating the order.

The only thing that's left is to make all DP transitions in O(1) time. To do that, maintain the total cost of all digits and the amount of numbers that have the carry. After adding one more number with carry in current digit, these two values can be easily recalculated. After processing all digits in A, we have to handle the remaining digits in B_i (if there are any) and take the best answer. Total running time is .