The minimal weight is at least $$$1$$$ since $$$1$$$ divides any integer (so $$$1$$$ divides $$$p_1$$$).

Since $$$k+1$$$ does not divide $$$k$$$, a permutation with weight equal to $$$1$$$ is: $$$[n,1,2,\cdots,n-1]$$$.

See the party as a graph.

Divide the vertices into two categories according to their degrees' parity.

Let's consider the case where $$$m$$$ is odd only, since if $$$m$$$ is even the answer is $$$0$$$.

Assume that you delete $$$x$$$ vertices with even degrees and $$$y$$$ vertices with odd degrees.

If $$$y \geq 1$$$, then only deleting one vertex with odd degree would have been enough.

If $$$y=0$$$, then the parity of the edges at the end is determined only by the number of edges whose both endpoints are deleted. In particular, there must be at least two adjacent vertices deleted with even degree.

Thus, an optimal solution either has $$$(x, y) = (0, 1)$$$ or $$$(x, y) = (2, 0)$$$ and the two vertices are adjacent.

One can iterate over all possible solutions with such structure and take the optimal one.

Total time complexity: $$$O(n)$$$.

The picture must consist of some stripes with at least $$$2$$$ rows or at least $$$2$$$ columns.

When $$$n$$$ is odd and all $$$\lfloor \frac{a_i}{m} \rfloor=2$$$, we cannot draw a beautiful picture using row stripes.

Let's first prove hint1 first.

If there is a pair of toroidal neighbors with different colors. For example, $$$col_{x,y}=a$$$ and $$$col_{x+1,y}=b(a\neq b)$$$. Then we will find $$$col_{x-1,y}=col_{x,y+1}=col_{x,y-1}=a$$$,$$$col_{x+2,y}=col_{x+1,y+1}=col_{x+1,y-1}=b$$$ must hold. Then we find another two pairs of toroidal neighbors $$$col_{x,y+1},col_{x+1,y+1}$$$ and $$$col_{x,y-1},col_{x+1,y-1}$$$. Repeat such process, we will find the boundary should be like:

Similar, the boundaries can be vertical lines, but horizontal lines and vertical lines can not exist in one picture.

So the pattern should be row stripes both with at least $$$2$$$ rows or column stripes both with at least $$$2$$$ columns.

Check if one can draw a beautiful picture with row stripes only or with column stripes only. We consider only the case of row stripes, the reasoning is analogous for column stripes.

If it is possible, then $$$\sum_{i=1}^{n} \lfloor \frac{a_i}{m} \rfloor \geq n$$$ must hold.

If $$$n$$$ is even, then such a condition is enough.

If $$$n$$$ is odd, there must be some $$$\lfloor \frac{a_i}{m} \rfloor \geq 3$$$. In this case, you can draw a beautiful picture using such algorithm:

• Sort $$$a_i$$$ from large to small.

• Draw $$$2$$$ rows stripes of each color if possible.

• If the picture still has some rows empty, insert new rows into each stripe.

Total time complexity: $$$O(n)$$$.

The maximum can always be achieved in the center position of one day's rain.

$$$a_i$$$ is a piecewise linear function and the slope of $$$a_i$$$ will only change for $$$O(n)$$$ times.

Supposing you know an invalid position $$$j$$$ where $$$a_j>m$$$, what are the properties of a rain that, if erase, makes it valid?

Let's call position $$$j$$$ a key position if it is the center position of a rain. i.e. there exists $$$i$$$ so that $$$x_i=j$$$.

You can calculate $$$a_j$$$ for all key positions $$$j$$$ using the difference array.

Let $$$d^{1}_{j}=a_{j}-a_{j-1}$$$, $$$d^{2}_{j}=d^{1}_{j}-d^{1}_{j-1}$$$, then the $$$i$$$-th day's rain will change it as follows:

$$$d^{2}_{x_i-p_i+1} \leftarrow d^{2}_{x_i-p_i+1}+1$$$

$$$d^{2}_{x_i+1} \leftarrow d^{2}_{x_i+1}-2$$$

$$$d^{2}_{x_i+p_i+1} \leftarrow d^{2}_{x_i+p_i+1}+1$$$

This can be calculated efficiently using prefix sums.

We say that a position $$$j$$$ is valid if $$$a_j\le m$$$.

Now, consider an invalid position $$$j$$$; erasing the $$$i$$$-th day's rain will make it valid if and only if $$$p_j-|x_i-x_j| >= p_i-m$$$.

One can check that the region of $$$(x, p)$$$ satisfying such an inequality is a quadrant rotated $$$45^\circ$$$ anticlockwise and translated. And in particular, even the intersections of two such regions have the same structure and can be computed easily (to avoid using floating point numbers, one can multiply all $$$x_i,p_i$$$ by $$$2$$$).

In the end, for each $$$i$$$, you only need to check whether point $$$(x_i,p_i)$$$ belongs to such region.

Total time complexity: $$$O(n\log n)$$$.

Consider the same bit of three integers at the same time.

$$$a\bigoplus b \leq a+b$$$

Define $$$cnt_{i_1 i_2 i_3}$$$ as:

$$$j$$$th bit of $$$cnt_{i_1 i_2 i_3}$$$ is $$$1$$$ iif $$$i_1=a_j,i_2=b_j,i_3=c_j$$$

e.g. $$$a=(10)_2,b=(11)_2,c=(01)_2$$$ then $$$cnt_{110}=(10)_2,cnt_{011}=(01)_2$$$, other $$$cnt$$$ is 0.

$$$a=cnt_{100}+cnt_{101}+cnt_{110}+cnt_{111}$$$

$$$b=cnt_{010}+cnt_{011}+cnt_{110}+cnt_{111}$$$

$$$c=cnt_{001}+cnt_{011}+cnt_{101}+cnt_{111}$$$

$$$a\bigoplus b = cnt_{010}+cnt_{011}+cnt_{100}+cnt_{101}$$$

$$$a\bigoplus c = cnt_{001}+cnt_{011}+cnt_{100}+cnt_{110}$$$

$$$b\bigoplus c = cnt_{001}+cnt_{010}+cnt_{101}+cnt_{110}$$$

$$$a\bigoplus b + a\bigoplus c > b \bigoplus c \iff cnt_{011}+cnt_{100}>0$$$

similar:

$$$cnt_{101}+cnt_{010}>0$$$

$$$cnt_{110}+cnt_{001}>0$$$

then we use digit dp: $$$dp[n][i][j]$$$ means when we consider first $$$n$$$ bits, state of reaching the upper bound is $$$i$$$, state of conditions is $$$j$$$.

Enumerate $$$a_j b_j c_j$$$ for $$$j$$$ from $$$|n|-1$$$ to $$$0$$$ and make transition.

Time complexity is $$$O(2^9 |n|)$$$ where $$$|n|$$$ is the length of input.

If interval $$$A,B$$$ are all good and $$$A \cap B \neq \emptyset$$$, then $$$A \cap B$$$ is good, too.

If interval $$$A,B$$$ are all good and $$$A \cap B \neq \emptyset$$$, then $$$A \union B$$$ is good, too.

Consider enumerating good intervals according to their length.

Let's consider the interval in the order of its length (small to large) and add the edge one by one.

Initially, the graph has no edge. There are $$$n$$$ connected components each consisting of exactly one vertex. Note our algorithm will guarantee that at every moment every connected component's indices compose an interval. Let $$$[L_i,R_i]$$$ be the connected component vertex $$$i$$$ in.

If $$$[x,y]$$$ is good and $$$x$$$ and $$$y$$$ are not in the same connected component, we can merge $$$[L_x,R_y]$$$ into a larger connected component.

Supposing $$$[L_x,R_y]$$$ consist of $$$k+2$$$ connected components now, let's call them $$$[l_0,r_0],[l_1,r_1],\cdots,[l_{k+1},r_{k+1}](x\in [l_0,r_0],y\in [l_{k+1},r_{k+1}])$$$, you can link edges like:

$$$ \cdots-l_4-l_2-x-y-l_1-l_3-\cdots$$$

If $$$[x,y]$$$ is good and $$$x$$$ and $$$y$$$ are in the same connected component, then we do nothing.

Finally, you will get a valid tree.