Arranging Crystal Balls
Contest: Codeforces Round 831 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: data structures, divide and conquer, divide and conquer, dp, geometry, graphs, number theory

In the world of Compfestnesia, Pak Chanek discovers a secret underground dungeon. Inside it, there is a treasure chest that is surrounded by $$$n$$$ statues that are arranged in a circular manner. The statues are numbered from $$$0$$$ to $$$n-1$$$ with statue $$$i$$$ being to the left of statue $$$i+1$$$ and statue $$$n-1$$$ being to the left of statue $$$0$$$.

Pak Chanek observes that each statue is holding a crystal ball with an integer between $$$0$$$ and $$$m-1$$$ inclusive. Let's say the integer in the crystal ball of statue $$$i$$$ is $$$a_i$$$.

The dungeon provides instructions that every integer in the crystal balls must be $$$0$$$ in order to open the treasure chest. To achieve that, Pak Chanek is given an integer $$$k$$$, and he can do zero or more operations. In a single operation, Pak Chanek does the following:

1. Choose exactly $$$k$$$ consecutive statues. In other words, choose the statues $$$p, (p+1) \bmod n, (p+2) \bmod n, (p+3) \bmod n, \ldots, (p+k-1) \bmod n$$$ for some chosen index $$$p$$$.
2. Do one of the following:   For all chosen statues, change their values of $$$a_i$$$ into $$$(a_i+1) \bmod m$$$.  For all chosen statues, change their values of $$$a_i$$$ into $$$(a_i-1) \bmod m$$$.

Help Pak Chanek find the minimum possible number of operations to open the treasure chest.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n,m \leq 10^6$$$, $$$nm \leq 2 \cdot 10^6$$$, $$$1 \leq k < n$$$) — the number of statues, the bound of the integers in the crystal balls, and the number of statues that can be operated in a single operation.

The second line contains $$$n$$$ integers $$$a_0,a_1,\ldots,a_{n-1}$$$ ($$$0 \leq a_i < m$$$) — the integers in the crystal balls.

Output format:
If it is possible to perform zero or more operations so that $$$a_0=a_1=\ldots=a_{n-1}=0$$$, output the minimum number of operations required. Otherwise, output $$$-1$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first example, Pak Chanek can do the following operations:

1. Do the $$$a_i := (a_i-1) \bmod m$$$ operation $$$3$$$ times for statues $$$1$$$, $$$2$$$, and $$$3$$$. Now $$$a=[8,7,1,2,0]$$$.
2. Do the $$$a_i := (a_i-1) \bmod m$$$ operation $$$1$$$ time for statues $$$3$$$, $$$4$$$, and $$$0$$$. Now $$$a=[7,7,1,1,8]$$$.
3. Do the $$$a_i := (a_i+1) \bmod m$$$ operation $$$2$$$ times for statues $$$4$$$, $$$0$$$, and $$$1$$$. Now $$$a=[0,0,1,1,1]$$$.
4. Do the $$$a_i := (a_i-1) \bmod m$$$ operation $$$1$$$ time for statues $$$2$$$, $$$3$$$, and $$$4$$$. Now $$$a=[0,0,0,0,0]$$$.

Example input:
5 9 3
8 1 4 5 0

Example output:
7

Example input:
4 4 2
1 0 0 0

Example output:
-1

Editorial:
Let's simplify the problem such that the only possible operation for each $$$k$$$ chosen statues is $$$a_i := (a_i - 1) \bmod m$$$.
To solve this, we first define $$$c_i$$$ as the number of times we do that operation for the statues $$$i, (i-1) \bmod n, (i-2) \bmod n, (i-3) \bmod n, \ldots, (i-k+1) \bmod n$$$. We can see that in the optimal configuration, $$$0 \leq c_i \leq m-1$$$ must hold. For it to make each element of $$$a$$$ to be $$$0$$$, $$$(c_i+c_{(i+1)\bmod n}+c_{(i+2)\bmod n}+\ldots+c_{(i+k-1)\bmod n})\bmod m=a_i$$$ must hold. The number of operations is equal to $$$c_0+c_1+c_2+\ldots+c_{n-1}$$$.
In order to extend to the original problem, we can see that for a given array $$$c$$$, the number of operations that can be made to be equal to $$$\sum_{i=0}^{n-1}\min(c_i,m-c_i)$$$. So we need to find an array $$$c$$$ satisfying the conditions above such that $$$\sum_{i=0}^{n-1}\min(c_i,m-c_i)$$$ is as small as possible.
We can see that $$$a_{(i+1)\bmod n} - a_i = c_{(i+k) \bmod n} - c_i$$$. That means, if we have determined the value of $$$c_i$$$, the value of $$$c_{(i+k) \bmod n}$$$ is forced. If we form an edge for each pair of indices $$$(i, (i+k) \bmod n)$$$, we will get $$$\text{GCD}(n,k)$$$ connected components. This means if we have determined the value of one vertex for each connected component, the values of the entire array $$$c$$$ are forced. However, we must also consider possibility that at least one connected component cannot have assigned values that satisfy all of its edges. In that case, it is impossible to finish the objective of the problem.
Define $$$d=\text{GCD}(n,k)$$$. For each $$$c_i$$$, we can find the difference relationship between it and $$$c_{i \bmod d}$$$. Therefore, to answer the problem, we must find the values of $$$c_0, c_1, c_2, \ldots, c_{d-1}$$$ such that $$$c_0+c_1+c_2+\ldots+c_{k-1}=a_0$$$ and if all the other values of $$$c$$$ are calculated, $$$\sum_{i=0}^{n-1}\min(c_i,m-c_i)$$$ is as small as possible.
For the $$$c_0+c_1+c_2+\ldots+c_{k-1}=a_0$$$ condition, using simple modular algebra, we can calculate one or more values $$$b_1,b_2,b_3,\ldots$$$ such that $$$c_0+c_1+c_2+\ldots+c_{k-1}=a_0$$$ if and only if $$$c_0+c_1+c_2+\ldots+c_{d-1}$$$ is equal to one of the values of $$$b$$$.
Let's consider the connected component $$$c_i, c_{i+d}, c_{i+2d}, \ldots$$$. It must have $$$\frac{n}{d}$$$ elements. Define $$$f_i(x)$$$ as the sum of $$$\min(c_j,m-c_j)$$$ for all elements of $$$c_j$$$ in that connected component if $$$c_i=x$$$. We can easily calculate all values of $$$f_i(x)$$$ for all connected components in $$$O(nm)$$$.
After this, we must the minimum value of $$$f_0(c_0)+f_1(c_1)+f_2(c_2)+\ldots+f_{d-1}(c_{d-1})$$$ such that $$$c_0+c_1+c_2+\ldots+c_{d-1}$$$ is equal to one of the values of $$$b$$$. This can be solved using modular knapsack dynamic programming, but the time complexity is $$$O(nm^2)$$$. We must optimise it further.
Consider the contribution of a single element $$$c_j$$$ to the values of $$$f_i(x)$$$ of its connected component. Let's say the difference relationship is that $$$c_i-c_j=w$$$ must hold. Notice that:
• It adds $$$(x-w)\bmod m$$$ to all values of $$$f_i(x)$$$ for each $$$x$$$ going up modularly from $$$w$$$ to $$$(w+\lfloor\frac{m}{2}\rfloor)\bmod m$$$
• It adds $$$(w-x)\bmod m$$$ to all values of $$$f_i(x)$$$ for each $$$x$$$ going up modularly from $$$(w+\lceil\frac{m}{2}\rceil)\bmod m$$$ to $$$w$$$.
We can see it as "changing slope" at most three times, namely in $$$x=w$$$, $$$x=(w+\lfloor\frac{m}{2}\rfloor)\bmod m$$$, and $$$x=(w+\lceil\frac{m}{2}\rceil)\bmod m$$$.
This means, if we add up all contributions of each element, the number of points the slope changes in one connected component is at most $$$\frac{3n}{d}$$$. We will call these points as special points.
Consider an array $$$c_0, c_1, c_2, \ldots, c_{d-1}$$$ satisfying the condition that $$$c_0+c_1+c_2+\ldots+c_{d-1}$$$ is equal to one of the values of $$$b$$$. Consider the case if there exists at least two different indices $$$i$$$ such that the value of $$$c_i$$$ is not a special point in $$$f_i$$$. Suppose the indices are $$$i_1$$$ and $$$i_2$$$. Since both of them are not special points, the slope between $$$(c_{i_1}-1)\bmod m$$$ and $$$c_{i_1}$$$ is the same as the slope between $$$c_{i_1}$$$ and $$$(c_{i_1}+1)\bmod m$$$. The same is true for $$$i_2$$$. Let's say $$$z_1$$$ is the increase in value of the final answer if we do $$$c_{i_1}:=(c_{i_1}+1)\bmod m$$$ and $$$c_{i_2}:=(c_{i_2}-1)\bmod m$$$, and $$$z_2$$$ is the increase in value of the final answer if we do $$$c_{i_1}:=(c_{i_1}-1)\bmod m$$$ and $$$c_{i_2}:=(c_{i_2}+1)\bmod m$$$. From the observation above, we can see that $$$z_1 = -z_2$$$, which means one of them is non-positive. This means, if this is the case, we can always change the array $$$c$$$ into another array with an equal or smaller final answer.
This means, we can always do that operation to get an array $$$c$$$ such that there is at most one non-special point. Therefore, we can just consider those cases to find the minimum answer.
We can solve this using divide and conquer. We first call the recursive function $$$\text{dnc}(0,d-1)$$$. The moment we call the function $$$\text{dnc}(l,r)$$$, we have made the modular knapsack dynamic programming array if we have only considered the indices $$$i$$$ with $$$i<l$$$ or $$$r<i$$$ and only considering their special points. $$$\text{dnc}(l,r)$$$ recurses into $$$\text{dnc}(l,\frac{l+r}{2})$$$ and $$$\text{dnc}(\frac{l+r}{2}+1,r)$$$. Once $$$l=r$$$, we will consider that index as the one that can have a non-special point, then we can just iterate the array $$$b$$$ and take the answer from the knapsack array.
The depth of the recursion is at most $$$O(\log d)$$$. Each depth has insertions of $$$O(d)$$$ indices to the knapsack. Because each connected component only has $$$O(\frac{n}{d})$$$ special points, each depth does $$$O(n)$$$ dynamic programming transitions with each transition having $$$O(m)$$$ time complexity.
Time complexity: $$$O(nm \log (\text{GCD}(n,k)))$$$