We will consider the problem as if \(A_i\) does not return to \(0\) when it becomes \(N\). Instead, we aim to achieve a state where all \(A_i \mod N\) are different.

First, let’s consider whether it is possible to transform \(A\) into \(B\). The necessary and sufficient conditions for this can be written as follows:

• \(A_i \leq B_i\),
• Let \(S=\sum (B_i-A_i)\). Then,
  • \(S\) is a multiple of \(M\);
  • \(B_i-A_i \leq S/M\).

Next, let’s observe the characteristics of the optimal solution to the original problem. Suppose we have obtained an optimal solution that transforms \(A\) into \(B\). Among such optimal solutions, let’s assume we have one where \(\sum B_i^2\) is minimized. Then, it can be shown that there exists some \(x\) such that \(B\) is a permutation of \((x,x+1,\cdots,x+N-1)\).

We prove this by contradiction. First, suppose there are \(i,j\) such that \(B_j-B_i>N\). Now, let’s replace \(B_i,B_j\) with \(B_j-N,B_i+N\), respectively. Then, the transformation from \(A\) to \(B\) remains a valid solution, and the value of \(\sum B_i^2\) becomes smaller than before. This is a contradiction, and the proof is complete.

Sort \(A\) in ascending order beforehand. The only \(B\) we need to consider is of the form \((x,x+1,\cdots,x+N-1)\). Now we just need to convert the conditions for \(B\) into conditions for \(x\) and find the minimum value of \(x\) that satisfies these conditions.

First, the condition \(A_i \leq B_i\) simply provides a lower bound for \(x\).

Next is the condition that \(S\) is a multiple of \(M\). When written out, this becomes \(\sum (i-1-A_i) + Nx \equiv 0 \mod M\). If we let \(g=\gcd(N,M)\), this condition specifies the value of \(x \mod M/g\) (it is also possible that this condition is never satisfied).

Finally, the condition \(B_i-A_i \leq S/M\) also, after some algebraic manipulation, provides a lower bound for \(x\).

Therefore, in the end, we are looking for the smallest \(x\) that satisfies the lower bounds and the condition \(x \mod M/g\), which can be calculated.

If we implement the above discussion as is, this problem can be solved in \(O(N)\) time.

Sample Solution