Unofficial tutorial to Codeforces Round 844 (A-G)

Unofficial tutorial to Codeforces Round 844 (A-G)

By Sol1, 4 days ago,

Seems like the official editorial has not been released for a long time, I'll try to provide an unofficial one for those who are tired of waiting. But I'm too weak to understand the solution to H by reading others' code :(. If you know the solution, I'll appreciate it if you can explain it to me.

Implementation can be seen in my submissions.

This is the first time I write an English editorial like this. If there's anything inappropriate, kindly point out.

Note that you have to move from the bottom to the top no matter what, so we can consider the following problem: Given 2 points in a rectangle, find one path from to that moves parellel to the edges of the rectangle and touch the edges at least once. After we get the answer to this problem, we can add to it to get the answer of the original.

This problem is easy to solve: iterate over which edge to touch, and the distance can be easily calculated.

The problem considers sets, thus we can sort the original array.

Observe that: if , and goes but does not go, then one of must be sad.

And we are done: just iterate over all prefixes, check if everyone is happy. Note that we can check the one with the maximum among the selected and the one with the minimum among the unselected, thus we can do this in .

Note that the character set consists of only 26 characters. We iterate over from to , check if is an integer. If it is, then it is possible to modify the string so it consists of distinct characters, each appearing times.

Now consider the following problem: we have an array . In one operation, one can arbitrarily choose , and decrease by 1 and increase by 1. we want to change it to .

Back to the original one: we count the occurrences for all 26 characters . We want to rearrange them in arbitrary order and minimize . Obviously sorting in decreased order will do.

After we iterate over all and find the one that gives minimal answer, use the method in the spoiler above to produce a construction. Total complexity is for one test case.

Obviously the answer can always be . Thus let's check if it can be .

Iterate over such that . If we want and , then we have . So that we factorize , if is of same parity, we have , thus yielding a possible (if it is non-negative).

In total, the above process gives possible s, in which denotes the the maximum number of divisors one number has, and equals to . So we can simply calculate the answer for all of them, resulting in the solution which can pass.

Observe that the total size of cover will not decrease. We will prove this by construction.

Divide the process into 4 steps:

Step 1

Remove all rectangles that are contained by some other rectangle. This can be done by a trivial greedy.

Step 2

For rectangle , if , and , shrink the width of such that . Sort everything by and greedy will do.

Step 3

For rectangle , if and they intersect, shrink so that they does not intersect but only touch on the edge. Still greedy and sortings.

Step 4

Segment cover for all rectangles.

Total complexity is .

Convert the problem onto the prefix sum array of the bracket sequence as follows:

Define as the probability of the sequence getting operated times without blowing up.

After one operation, changes to or . Using this to directly calculate will result in solution which can not pass.

To optimize, we try to convolve the 3 arrays one by one. Define as the probability of the sequence getting operated times without blowing up.

Transition as follows:

where denotes the probability of operating sequence for times, operations fall to side and operations fall to side; similiarly denotes the probability of operating sequence for times, operations fall to side and operations fall to side;

can be calculated by transitions:

And we have solved it in .

Observe that, except for a star with leaves, the answer to any tree is less than . Still, proof by construction.

And thus we are done with the first part, now everything is about constructing the answer.

We will do this in a recursive manner: let white be , blue be , and denote the process of coloring the subtree of such that its sum is .

Then it is a lot of casework:

1. If is a leaf, color with .
2. If the minimum imbalance for the subtree is , just color it that way.
3. If has two children, consider the minimum imbalance for each subtree.
   1. the two imbalances are : Call and , and color with .
   2. the two imbalances are : Call and , recolor to , and if the color of is , invert all colors in the subtree of and color with ; otherwise just color with .
   3. : Call and , if color of is then invert its subtree, and color with .
   4. : Call and , if color of and are both , then invert the subtree of and color with ; otherwise just color with .
   5. : Call and , if color of is then invert its subtree, and color with .
   6. : Call and , if both and are of color , invert one of them, and color with .
4. If has one children, denote it as , and consider the degrees of .
   1. is a leaf: color with and with .
   2. has one child (denote as ): If the minimum imbalance of is 2 then call and recolor to ; otherwise just call , and color the opposite of and the opposite of .
   3. has two children (denote as and ): more casework, similiar to when we deal with having two children. You may refer to my code for this.

Inverting a subtree can be done with a tag, thus the problem is done in .