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.

A

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 $$$A,B$$$ in a $$$w\times d$$$ rectangle, find one path from $$$A$$$ to $$$B$$$ 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 $$$h$$$ 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.

B

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

Observe that: if $$$a_i \geq a_j$$$, and $$$i$$$ goes but $$$j$$$ does not go, then one of $$$i,j$$$ 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 $$$a$$$ among the selected and the one with the minimum $$$a$$$ among the unselected, thus we can do this in $$$O(n)$$$.

C

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

Now consider the following problem: we have an array $$$s_1,s_2,\cdots,s_n$$$. In one operation, one can arbitrarily choose $$$i,j$$$, and decrease $$$s_i$$$ by 1 and increase $$$s_j$$$ by 1. we want to change it to $$$t_1,t_2,\cdots,t_n$$$.

Back to the original one: we count the occurrences for all 26 characters $$$c_1,c_2,\cdots,c_{26}$$$. We want to rearrange them in arbitrary order and minimize $$$\sum_{j=1}^{i}|c_j-\frac{n}{i}|+\sum_{j=i+1}^{26}|c_j|$$$. Obviously sorting $$$c$$$ in decreased order will do.

After we iterate over all $$$i$$$ and find the one that gives minimal answer, use the method in the spoiler above to produce a construction. Total complexity is $$$O(n\log n+26n)$$$ for one test case.

D

Obviously the answer can always be $$$1$$$. Thus let's check if it can be $$$\geq 2$$$.

Iterate over $$$i,j$$$ such that $$$a_i<a_j$$$. If we want $$$a_i+X=n^2$$$ and $$$a_j+X=m^2$$$, then we have $$$a_j-a_i=m^2-n^2=(m+n)(m-n)$$$. So that we factorize $$$a_j-a_i=p\times q$$$, if $$$p,q$$$ is of same parity, we have $$$m=(p+q)/2,n=|p-q|/2$$$, thus yielding a possible $$$X=m^2-a_j$$$ (if it is non-negative).

In total, the above process gives $$$O(n^2d(10^9))$$$ possible $$$X$$$s, in which $$$d(10^9)$$$ denotes the the maximum number of divisors one number $$$\leq 10^9$$$ has, and equals to $$$1344$$$. So we can simply calculate the answer for all of them, resulting in the $$$O(n^3d(10^9))$$$ solution which can pass.

E

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 $$$i,j$$$, if $$$u_i\neq d_i, u_j=d_j$$$, and $$$l_j<l_i\leq r_i<r_j$$$, shrink the width of $$$i$$$ such that $$$u_i=d_i\neq u_j=d_j$$$. Sort everything by $$$l$$$ and greedy will do.

Step 3

For rectangle $$$i,j$$$, if $$$u_i\neq d_i, u_j=d_j$$$ and they intersect, shrink $$$j$$$ 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 $$$O(n\log n)$$$.

F

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

Define $$$f_{i,j}$$$ as the probability of the sequence $$$a=[j]$$$ getting operated $$$i$$$ times without blowing up.

After one operation, $$$[j]$$$ changes to $$$[j,j+1,j]$$$ or $$$[j,j-1,j]$$$. Using this to directly calculate $$$f$$$ will result in $$$O(n^4)$$$ solution which can not pass.

To optimize, we try to convolve the 3 arrays one by one. Define $$$g_{i,j}$$$ as the probability of the sequence $$$a=[j,j]$$$ getting operated $$$i$$$ times without blowing up.

Transition as follows:

where $$$s_{k,i-k}$$$ denotes the probability of operating sequence $$$a=[x,y]$$$ for $$$i$$$ times, $$$k$$$ operations fall to $$$x$$$ side and $$$i-k$$$ operations fall to $$$y$$$ side; $$$t_{k,i-k}$$$ similiarly denotes the probability of operating sequence $$$a=[x_1,x_2,y]$$$ for $$$i$$$ times, $$$k$$$ operations fall to $$$x$$$ side and $$$i-k$$$ operations fall to $$$y$$$ side;

$$$s,t$$$ can be calculated by transitions:

And we have solved it in $$$O(n^3)$$$.

G

Observe that, except for a star with $$$3$$$ leaves, the answer to any tree is less than $$$1$$$. 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 $$$+1$$$, blue be $$$-1$$$, and $$$F(u,s)$$$ denote the process of coloring the subtree of $$$u$$$ such that its sum is $$$s$$$.

Then it is a lot of casework:

1. If $$$u$$$ is a leaf, color $$$u$$$ with $$$s$$$.
2. If the minimum imbalance for the subtree is $$$2$$$, just color it that way.
3. If $$$u$$$ has two children, consider the minimum imbalance for each subtree.
   1. the two imbalances are $$$(2,2)$$$: Call $$$F(l,-2)$$$ and $$$F(r,2)$$$, and color $$$u$$$ with $$$s$$$.
   2. the two imbalances are $$$(2,1)$$$: Call $$$F(l,2)$$$ and $$$F(r,1)$$$, recolor $$$l$$$ to $$$-1$$$, and if the color of $$$r$$$ is $$$-1$$$, invert all colors in the subtree of $$$r$$$ and color $$$u$$$ with $$$1$$$; otherwise just color $$$u$$$ with $$$-1$$$.
   3. $$$(2,0)$$$: Call $$$F(l,2)$$$ and $$$F(r,0)$$$, if color of $$$r$$$ is $$$1$$$ then invert its subtree, and color $$$u$$$ with $$$s$$$.
   4. $$$(1,1)$$$: Call $$$F(l,s)$$$ and $$$F(r,s)$$$, if color of $$$l$$$ and $$$r$$$ are both $$$-s$$$, then invert the subtree of $$$r$$$ and color $$$u$$$ with $$$s$$$; otherwise just color $$$u$$$ with $$$-s$$$.
   5. $$$(1,0)$$$: Call $$$F(l,1)$$$ and $$$F(r,0)$$$, if color of $$$r$$$ is $$$-1$$$ then invert its subtree, and color $$$u$$$ with $$$-1$$$.
   6. $$$(0,0)$$$: Call $$$F(l,0)$$$ and $$$F(r,0)$$$, if both $$$l$$$ and $$$r$$$ are of color $$$s$$$, invert one of them, and color $$$u$$$ with $$$s$$$.
4. If $$$u$$$ has one children, denote it as $$$v$$$, and consider the degrees of $$$v$$$.
   1. $$$v$$$ is a leaf: color $$$u$$$ with $$$1$$$ and $$$v$$$ with $$$-1$$$.
   2. $$$v$$$ has one child (denote as $$$w$$$): If the minimum imbalance of $$$w$$$ is 2 then call $$$F(w,2)$$$ and recolor $$$w$$$ to $$$-1$$$; otherwise just call $$$F(w,s)$$$, and color $$$v$$$ the opposite of $$$w$$$ and $$$u$$$ the opposite of $$$v$$$.
   3. $$$v$$$ has two children (denote as $$$w_1$$$ and $$$w_2$$$): more casework, similiar to when we deal with $$$u$$$ 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 $$$O(n)$$$.

In Codeforces round 587, there is an user OrzCrabby_Maskiv participated, and his/her actual rating change is 30 to -9, but in the "rating change" list it was showing 100 → 100. You can add OrzCrabby_Maskiv as a friend to view his rating change in the list.

MikeMirzayanov if this is an issue please fix it.