Official Analysis (C++, Python)

Explanation

The problem asks us to minimize the sum of $|a_i - x|$ for all $a_i$, using an $x$ of our choice, with each difference under modulo $M$ (strictly, optimizing the sum of $\min(a_i - x \bmod M, x - a_i \bmod M)$). Thus, let us first consider this problem without the modulus.

Letting $x$ be the median of those numbers minimizes the total distance. In the case that $N$ is even, any number between the two numbers in the middle (inclusive) would work.

We now consider the modulus. First, take each number modulo $M$. Observe that any element can be the median if we add or subtract $M$ from some elements, shifting some values to the left and right of the element. For example, given $[1,3,7,9,13,17,19]$ and $M = 24$, we can make $17$ the median by adding $M$ to elements $1$ and $3$, resulting in the array $[7,9,13,17,19,25,27]$.

Thus, every element is a candidate for $x$. We compute the cost for each $x$ after shifting, and take the best candidate, which is the $x$ that results in the smallest sum of absolute differences.

To implement this, we first sort $a$. Then, we consider each element in a as a potential $x$. For each candidate value, we compute either the number of elements before it that must be increased by $M$ or the number of elements after it that must be decreased by $M$ in order to make this value the median. After that, we use prefix sums to compute the total absolute difference. However, this requires us to access indices of $a$ that are not in the $[0, n)$ range; to mitigate this, we prepend to $a$ a copy of $a$ with $M$ subtracted from every element, and append a copy of $a$ with $M$ added to every element. The range $[n, 2n)$ in $a$ will then be the original elements we enumerate over, and we will be able to access the elements that come before or after the original array.

The final answer will be the smallest sum of absolute differences over all such indices.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$ per test case

Copy
t = int(input())
for _ in range(t):
	n, m = map(int, input().split())
	nums = list(map(int, input().split()))

	# Mod, sort, and construct array
	rems = sorted([x % m for x in nums])

	# s is prepended/appended array
	s = [x - m for x in rems] + rems + [x + m for x in rems]