Ah yes, "newbie-friendly" with last questions of either top-tier maths or DP/graph. Very friendly.

9/4=2.25

First sort the values of $$$a_i$$$, I'll assume they are sorted from now on.

If mean < median, we clearly need to perform at least $$$sum - median$$$ increases, and we can always perform this by increasing the largest value.

Otherwise, we increase all values from $$$a_i$$$ for all $$$\frac{n}{2} \leq i \leq n$$$ to the mean. Now the mean will also increase and we may have to perform this again, so what is the complexity of this? For median we are increasing only $$$\frac{n}{2}$$$ elements while mean considers all $$$n$$$, so for an increase of $$$x$$$ in the median, the mean increases by at most $$$\frac{x}{2}$$$, meaning the mean and the median will converge in at most $$$O(log(mean))$$$ iterations.

Just binary search for the minimum possible median, by keeping in mind that no element should be reduced.

Why is the maximum for ChefWM the number of prime factors of M?

u said fairly obvious for problem MSUB121! this technique of dividing into heavy/light nodes doesn't seem intuitive. Is this some standard technique??

Short answer: It is a dp where we perform operations for "heavy" nodes (more than $$$\sqrt{q}$$$ pairs) and "light" nodes (at most $$$\sqrt{q}$$$ pairs) in different ways.

Long answer:

Consider the naive $$$O(n ^ 2)$$$ idea, its a dp where $$$dp_{y} = max(max(dp_{x}), 1)$$$, over all $$$x \leq y$$$ for which there exists a pair $$$(a_x, a_y)$$$.

The problem here is that the sum of the number of such "edges" for all possible $$$i$$$ can be very high, as much as $$$O(n ^ 2)$$$.

Let us call values $$$a_x$$$ with more than $$$\sqrt{q}$$$ pairs $$$(a_x, a_y)$$$ "heavy" and those with less than $$$\sqrt{q}$$$ pairs "light".

When we have to update the values from $$$x$$$ to $$$y$$$ as above, we can have four cases:

• light -> light
• light -> heavy
• heavy -> light
• heavy -> heavy

For a light node $$$a_x$$$, "pushing" the answer to every possible $$$a_y$$$ such that $$$(a_x, a_y)$$$ is a pair takes at most $$$O(\sqrt{q})$$$ time since there are by the definition of a light node at most $$$\sqrt{q}$$$ pairs we can push values to so we can decide to push values in the first two cases.

However this isn't the case for heavy nodes which may have a degree as much as $$$q$$$. However we can notice that since each heavy node has at least $$$\sqrt{q}$$$ edges, there can be at most $$$\frac{q}{\sqrt{q}} = \sqrt{q}$$$ heavy nodes. So for each $$$a_y$$$ we can "pull" the answer from every heavy $$$a_x$$$ where $$$(a_x, a_y)$$$ is a pair in at most $$$O(\sqrt{q})$$$ which handles the remaining two cases.

So our total solution runs in $$$O(n \sqrt{q})$$$ which is fast enough.

If any two blue nodes are adjacent then the answer is clearly no, otherwise:

Lets compress all connected components of the same colour together, then if there is a path with only one colour $$$G$$$ or $$$R$$$ in them, then we will have $$$B - G - B$$$ or $$$B - R - B$$$.

So after compressing it we can just check if there exists a single node that has two or more blue nodes adjacent to it, if so the answer is no. Otherwise the answer is clearly yes.

Instead of compressing we can probably just do a subtree dp of some sort as well.

Cut all R-G edges and if there is a path from B to the other B, the answer is NO. You can use dsu or something to check this.

(off topic)

The generator problem will be also interesting! Here's how I generated cases whose answer are Yes.
Firstly, I colored vertices Red and Green so that the vertices of same color aren't adjacent.
Then I picked non-Blue vertex at random and check if the coloring remains valid after it is changed to Blue.
You can validiate coloring in $$$O(N)$$$ each time and $$$O(N^2)$$$ total, but can you do it in $$$O(N)$$$ total?

Cases with No is easy. After creating cases with Yes, just change non-Blue vertices Blue until the coloring become invalid.