Hint

Hint 1

Eliminate the operation of taking $\bmod$ and replace it with something else.

Hint 2

Rephrase the condition as $A_i \ne A_{i+1}$ and $|A_i - A_{i+1}| < M$.

Hint 3

Fix the final sequence. What kind of sequence satisfies the conditions, and what kind of sequence can be made from $A$?

Answer to Hint 3

Obviously, the final $A_i$ must have a remainder of $B_i$ when divided by $M$. Also, the magnitude relationship in $A$ does not change, so it must be preserved.

Hint 4

Once the final $A_1$ is fixed, all elements of the final $A$ are also determined.

Hint 5

When the final $A$ is fixed, in most cases, it is possible to achieve the obvious lower bound of the number of operations. In other cases, it is simple.

Hint 6

We want to minimize the sum of absolute values. There should be a well-known fact that can be used in such a situation.

Solution

We first process the case \(M=2\). If \(A\) and \(B\) match, the answer is 0; otherwise, it is -1. From now on, we assume \(M \geq 3\).

Eliminate the operation of taking \(\bmod\) and simply perform the operations as follows:

• Set \(A_i \leftarrow A_i + 1\) (this will be referred to as addition operation)
• Set \(A_i \leftarrow A_i - 1\) (this will be referred to as subtraction operation)

In this case, in addition to \(A_i \ne A_{i+1}\), it is necessary to maintain the condition \(|A_i - A_{i+1}| < M\).

If the final sequence is \(C\), it must satisfy \(C_i \bmod M = B_i\) and \(|C_i - C_{i+1}| < M\). Since \(B\) is a good sequence, \(C_i \ne C_{i+1}\).

Also, since the magnitude relationship of \(A_i\) and \(A_{i+1}\) does not change, it must match that of \(C_i\) and \(C_{i+1}\).

By the way, once $C_1$ is determined, the other terms are also uniquely determined. In fact, it can be shown that for $M \geq 3$, it is always possible to make $A$ match $C$, and $\sum_{i=1}^{N} |A_i - C_i|$ will be the number of operations. Below, we will prove this while actually constructing it.

Proof

We will call $i$ where $A_i < C_i$ a positive term, and otherwise a negative term.

It is sufficient to perform only addition operations on positive terms and only subtraction operations on negative terms.

Consider performing operations from the smaller $i$. Also, assume that we have aligned up to the $(i-1)$-th term.

First, there is no need to worry about the $(i-1)$-th term. If the $(i-1)$-th term prevented the operation, it would contradict the condition for $C$.

When the $i$-th term is a positive term, if $A_i + 1 = A_{i+1}$ or $A_i + 1 - A_{i+1} = M$, the addition operation cannot be performed as is. Otherwise, it is sufficient to perform the addition operation, so consider the case where this condition is met.

In this case, we will recursively perform the addition operation on the $(i+1)$-th term. If this is possible, it becomes possible to add to the $i$-th term.

When this operation is continued recursively, it is easy to show that there is no need to worry about the previous term. Also, since it is always possible to add to the $N$-th term, it can be shown that the process will end.

It is problematic if these terms are negative terms, but in either case, a contradiction arises if they are negative terms. Therefore, all terms on which the recursive addition is performed are positive terms.

The same can be shown for negative terms. Therefore, it has been shown that it is always possible to make $A$ match $C$, and $\sum_{i=1}^{N} |A_i - C_i|$ will be the number of operations.

Therefore, we only need to find the optimal way to determine \(C_1\). It can be seen that the possible \(C\) are limited to those where the sequence is determined by initially setting \(C_1 = B_1\) and adding multiples of \(M\) to all terms. For now, forget about adding multiples of \(M\) and consider adding any numbers.

Then, it can be seen that this is equivalent to minimizing a function of the form \(\sum_{i=1}^{N} |x_i - a|\). It can be shown that the \(a\) that minimizes this is the median of \(x\). This can be seen by considering the points where the slope changes. Even without this consideration, it is easily found using a data structure called Slope Trick.

Remembering to add multiples of \(M\), it is sufficient to consider only the multiples of \(M\) around the \(a\) that originally minimized the value. This is because the value increases as it moves away from the \(a\) that minimized it.

There are at most two such multiples, so it is sufficient to try both. The computational complexity is \(O(N \log N)\), with finding the median being the bottleneck. However, it can be reduced to \(O(N)\) using a method called Median of Medians. Either is fast enough to solve this problem.

Judge’s Solution (PyPy3)

def space(x,y):
    if x<y:return -1
    if x==y:return 0
    if x>y:return 1

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
if M==2:
    if A==B:
        print(0)
    else:
        print(-1)
    exit()
C=[B[0]]
for i in range(1,N):
    for j in range(C[-1]//M-3,C[-1]//M+3):
        if space(A[i-1],A[i])==space(C[-1],j*M+B[i]) and abs(C[-1]-(j*M+B[i]))<M:
            C.append(j*M+B[i])
            break
add=[]
for i in range(N):
    add.append(C[i]-A[i])
add.sort()
mid=add[N//2]
ans=1<<60
for i in range(mid//M-3,mid//M+3):
    now=0
    for j in range(N):
        now+=abs(A[j]+i*M-C[j])
    ans=min(ans,now)
print(ans)