532A - Berland Miners

We can add n - k miners with height 0 and it won't affect answer. So we can assume that numbers of miners and caves are the same.

For every cave let's define t_i as maximal possible height of miner working in cave i if we wouldn't change any cave. We can calculate it from root to leaves with line t_i = min(t_father, h_i).

Let's say we don't change anything. We will try to assign all workers if it's possible or to do the best possible assignment otherwise — the one where there are few free (not occupied) caves and they are high (value t_i is big). I will say later why we want them to be high. Formal definition (you don't have to read the next paragraph):

For every assignment let's sort free caves by t_i. In the best assignment number of free caves is minimal possible. And for every position in such a list free cave in the best assignment has value t_i not lower than in any other assignment. It can be proven that best possible assignment exists (it's not so obvious though).

How to find the best possible assignment? Let's sort caves ascending by t_i and for every cave let's assign the tallest free miner who can work here. It will give us the best possibble assignment. Why? Let's say we've just made first bad decision (different than in the best assignment). It doesn't make sense to leave a cave empty if we can assign here someone. So we put a worker somewhere and we won't be able to do assignment now (we assumed that we've just made bad decision). From definition "we put here tallest possible miner" we know that we couldn't assign here taller guy. Maybe we want to assign here shorter miner and this "highest possible" goes somewhere else? But we can swap them and everything will be ok. So there remains last option: we don't want to put anyone here. But we will have to assign our guy to some higher cave so we can leave his destiny cave empty and put him here. To sum up, it's ok to assign highest possible free worker with iterating over caves sorted by t_i. Almost the same sentences are the proof for other lemma:

If we want to have few free (not assigned) miners and we want them to be short it's optimal to iterate somehow over caves and to assign the tallest possible free miner in every cave. It works for every order of iterating over caves. And every order gives us the same set of free miners (but not necessarily the same set of free caves).

Why did we want free caves to be high? Because to assign everyone we must change height of cave not higher than the lowest free cave. Why? In short: otherwise that lowest free cave will remain free after running our assignment-algo (described above) on new tree. But we managed to find maximal possible height of lowest free cave. Let's call this value as LIM. And we know minimal set of free miners.

Changing height of cave i from a to something bigger does something only when t_i = a ≤ LIM. And then in set of t_i some changes happen. There were caves blocked before by cave i so they had t equal to a. These caves will have bigger t so in set of values t we have change e.g. from {5, 5, 5} to {7, 10, 8} (a was equal to 5). Let's throw out miners from caves with changed t_c (maybe some of these caves were empty anyway). If we can't assign free miners (we found them before) to new caves then assigning everything isn't possible. Otherwise it is — we assign them in these caves with changed t and there are some threw out miners. But all of them were in caves with t = a ≤ LIM so they are not higher than LIM. And we know that every free cave has t_free ≥ LIM because LIM is height of lowest free cave. So we can put them there.

Solution is to find result with binary search and to answer question: can we assign miners to caves with changing one cave by at most D? With our assignment-algo we calculate optimal lowest free cave and set of free miners. Then for every cave we try to increase its height by D if it had t not higher than LIM. It's also important that checking change of every cave has amortized linear complexity. If increasing height of cave A affects t of cave B below then later changing height of B does nothing — B is blocked by A anyway.

532B - Work Group

This problem can be solved by using dynamic programming over subtrees of company hierarchy. Denote as D[v][e] maximum possible efficiency that can be obtained by taking several people from subtree of v so that pairity of their number is e in order condition from statement is fullfilled for all already taken people. Then it is easy to calculate D[v][e] from values of children of v by considering intermediate value T[i][e] — maximum possible efficiency that we can obtain by using first i subtrees of v with overall pairity e.

It's important to not to forget that there are two cases: we may take v itself or we may decide to not take it. In first case it is important that all subtrees have overall even number of taken people. In the second case there is no such restriction.

532C - Board Game

We will consider three cases:

1) x_p + y_p ≤ max(x_v, y_v). In this case Polycarp can be in (0, 0) after x_p + y_p moves and Vasiliy will always be ,,behind''. It's enough for Polycarp to make any move and he is always able to do it. It makes Polycarp closer to (0, 0) and after Vasiliy's move we again have x_p + y_p ≤ max(x_v, y_v) condition fulfilled and in some moment Polycarp will reach (0, 0). It's impossible that Vasiliy wins because our condition would be unfulfilled.

2) x_p ≤ x_v, y_p ≤ y_v. In this scenario Polycarp must block Vasiliy somehow. He must make such a move that after any Vasiliy's response condition will be fulfilled again.

• If x_p = x_v > 0 he goes to (x_p - 1, y_p).
• If y_p = y_v > 0 he goes to (x_p, y_p - 1).
• Otherwise he makes any move.

With this strategy Vasiliy is unable to get out of our new condition.

3) Otherwise we can consider any shortest path to (0, 0) for Vasiliy. Lenght of it is max(x_v, y_v). For any cell on this path Polycarp has greater distance than Vasiliy to it so he can't be there before Vasiliy and he can't block him. Vasiliy wins. Alternative explanation: after any possible Polycarp move Vasiliy can make a move that none of conditions (1) and (2) aren't fulfilled.

532D - Landmarks

First observation: column crashes only if distance between its neighbours is greater than 2d_i so it doesn't matter where exactly is this column. The only important thing is how far are left and right neighbour of it.

For every column C let's calculate does there exist subset of columns on the left that everything is stable between C and leftmost bearing column. If answer is yes then how close can be left neighbour of C? Then we will know how far the right neighbour can be. We will use dynamic programming.

Slow approach: For every previous column let's check if it can be neighbours with C. The closest column fulfilling this condition is best left neighbour of C.

Faster approach: Let's denote far[i] as the biggest possible coordinate where right neighbour of column i can be. In our dp we need an extra stack with possible candidates for being left neighbour of new column. In this stack columns are sorted in ascending order by index (and coordinate) and in descending order by far[i]. For every new column we must remove from the top of stack columns which have too low far[i]. Then last column on stack is the best left neighbour and we can calculate value far for current column. It is O(n) algorithm.

Some columns can't be connected with leftmost bearing column and for them we have far[i] = 0. If there exists column with far[i] not less than coordinate of rightmost bearing column then we don't have to add new column and answer is 0.

Ok. Now let's run the same dp from right to the left. Some columns are connected with leftmost bearing column, some other columns with righmost one. And we will want to place new column somewhere between them. Brute force solution is to check every pair of columns and to say: we want these two columns to be neighbours of added column. With values far[i] calculated in dp we check if we can have such a situation and we eventually consider result to be half of a distance between these two columns.

How to make this last part faster? We must create two stacks with best candidates for neighbours of new column. One stack with columns connected to the leftmost column, one with the ones connected to the rightmost one. On these stacks we can find answer with two pointers technique.

Whole solution is linear in time and memory.

532E - Correcting Mistakes

Suppose that S is obtained from W by deleteing the earlier symbol than T. Then it is true that W = A + x + B + y + C, S = A + x + B + C, T = A + B + y + C, where x and y are deleted symbols and A, B и C are some (possibly, empty) strings.

Let's calculate A as a longest common prefix of S and T and C as a longest common suffix. Remove both of them from strings. Now we now that x and y are respectively the first letter of string S and last letter of string T. Remove them too. The only thing left is to check if remaining parts of strings are equal.

Perform such operation for S and T and for T and S.

532F - Encoding

There are two possible ideas for solving this task.

Fix pair of letters x and y. Replace all letters x in S with 1s and all remaining letters with 0s. Do the same for y with string T. By using KMP algorithm or Z-function determine all positions where string T can be attached to string S so there is a match. If such condition is fullfilled for pair (x, y), and for pair (y, x) then this position is a possible match position if we use pair (x, y) and possibly some other pairs.

Now for each suitable position we need to check if letters can be distributed in pairs according to the information we know. This can be done in O(sigma) where sigma = 26 — the size of the alphabet. So, this solution works in O(n * sigma² + n * sigma) = O(n * sigma²). It fits in time limit if implementation is efficient enough.

Another way is to perform such transformation with both strings that allows us to compare them up to letters renaming. Let's replace each letter with distance from it to the closes letter to the left from it that is the same (or with -inf if there is no such letter). Now for strings to be equal we just need to check that string T matches the substring of S in all positions except, possibly, first occurence of each letter in T. This can be done by modified prefix-function or by hashing.

Now suppose we know that in some position string T is the same as string S up to renaming letters. It's not hard to determine the letter permutation for this renaming (by just checking what matches in S with first occurence of each letter in string T). Let's check that this permutation is a set of transpositions in O(sigma). So, we have a solution in O(n * sigma).