Zlobober's blog

By Zlobober, 10 years ago, translation, In English

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 ti 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 ti = min(tfather, hi).

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 ti 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 ti. 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 ti 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 ti 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 ti. 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 ti = a ≤ LIM. And then in set of ti 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 tc (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 tfree ≥ 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) xp + yp ≤ max(xv, yv). In this case Polycarp can be in (0, 0) after xp + yp 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 xp + yp ≤ max(xv, yv) condition fulfilled and in some moment Polycarp will reach (0, 0). It's impossible that Vasiliy wins because our condition would be unfulfilled.

2) xp ≤ xv, yp ≤ yv. 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 xp = xv > 0 he goes to (xp - 1, yp).
  • If yp = yv > 0 he goes to (xp, yp - 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(xv, yv). 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 2di 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 * sigma2 + n * sigma) = O(n * sigma2). 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).

Tutorial of VK Cup 2015 - Round 2
  • Vote: I like it
  • +123
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Can anyone explain his solution for problem A?

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +50 Vote: I do not like it

    Let us define "cave effective height" as minimum of cave's height and all that cave ancestors' heights.

    First, let's analyze the problem if we cannot increase cave's height. Consider two miners a and b with heights ha > hb and two caves p and q, with p being an ancestor of q. If (in one solution) we assign a to q and b to p, notice, that we can swap them. So following greedy approach works: Assign miners in height decreasing order. Each time choose for the miner the cave, which parent is already filled and with largest effective height from all caves satisfying the first condition.

    If we find the solution, no cave height needs to be raised. Otherwise, we got miner, which doesn't fit in any of the caves that left.

    I claim, that if solution to the original problem exists, we will increase one cave to his height. There is no need to raise any cave more, and we still cannot assign him anywhere if we raise any cave less. Also, we know, that all caves filled before had their heights no lower, so we need to raise height of the cave, that has its parent already filled.

    We are now left with m miners h1 > ... > hm. Now let's maintain sequence x1 - 1, x2 - 2, ..., xm - m, where xk is the number of caves that can fit miners hk, ..., hm. We will be changing heights of some caves. If at some moment, all sequence elements are non-negative, we can assign all miners, so we got the solution. We can use segment tree to store this sequence (we need operations: add constant to interval, get global minimum). Now all that's left is to try to increase (one at a time) height of a cave, that has its parent already filled and check for all effective heights changes. Each cave affect caves only in its subtree.

    Total complexity:

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution for A:

    1. USACO-step: sort all miners by height.

    2. For each cave calculate the "blocking cave". The blocking cave for some cave V is the cave which you definitely need to increase in order to increase the effective height of the 1-V path. Basically the blocking cave for V is the lowest cave on the 1->V path (1 and V included). If there are multiple caves with the smallest height on that path pick arbitrary, it doesn't matter.

    3. For each cave V calculate the maximum possible path height. This is the height which you can achieve by making its blocking cave to have infinite height. And this value is simply the second minimum height on 1->V path. If V is a root itself then this height is Infinity.

    4. Group these maximum possible path heights by blocking cave index. Each such group will give you an information of what cave heights you might achieve if you increase this particular blocking cave's height to some new value.

    5. Obviously if you increase a height in one group then path heights in all other groups will remain equal to the height of their blocking cave.

    6. Sort all groups by their blocking cave's height.

    7. Do the final magic:

    I claim that if you want to check what is the minimum height you can assign to some group X so that all miners will have a home then you can check that with the rest of the caves being assigned greedily and that will give you the correct result. One more detail for assigning heights greedily. For all groups coming before X you assign shortest available miners, so effectively all you need to remember is how long will be a prefix of people that you will be able to cover with all groups coming before X. For all groups coming after X you try to assign the tallest fitting guy to the cave.

    You see that the right part of that greedy assignment is a bit more complicated than the left one because the suffix of assigned miners might not be contiguous. For that reason it makes sense to iterate over groups in reversed order, starting with the group where blocking cave has maximum height. Then you know which prefix of people you will be able to assign to the groups coming before your current group and all you need to check is whether you will be able to assign remaining people to your current group if you increase its blocking cave's height somehow. You can easily do that in time proportional to the number of caves in this group. After you check this particular group you will move to the right part with regards to the group you will check next, so before leaving your current group you use all its caves with their current height (which are equal to the blocking cave height, since it won't be increased anymore) to put into each cave the tallest fitting miner.

    That was wordy. My submission — 10924081.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think something is wrong here..?

In problem F; the first idea, with this example: 5 5 acdff adcgh

if we check (c,d), the string S and T: 01000 and 01000; and we check (d,c), the string S and T: 01000 and 01000

=> chose position 1 (according to the solution) ; but it is not true.

Sorry for my bad English! :D

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, we don't choose (x,y) pair directly after this first step, we only mark this position as this may be the answer, and we should check later whether this position is real answer or not, about that it is said that it can be done in "O(sigma) where sigma = 26 — the size of the alphabet" but I don't have any idea yet how it's done in O(sigma).