Farmer John's Favorite Operation

Explicación

El problema nos pide minimizar la suma de $|a_i - x|$ para todos los $a_i$ , usando un $x$ de nuestra elección, con cada diferencia bajo módulo $M$ (estrictamente, optimizar la suma de $\min(a_i - x \bmod M, x - a_i \bmod M)$ ). Así, consideremos primero este problema sin el módulo.

Tomar $x$ como la mediana de esos números minimiza la distancia total . En el caso de que $N$ sea par, cualquier número entre los dos del medio (inclusive) funcionaría.

Ahora consideramos el módulo. Primero, tomamos cada número módulo $M$ . Observemos que cualquier elemento puede ser la mediana si sumamos o restamos $M$ a algunos elementos, desplazando algunos valores a la izquierda y a la derecha del elemento. Por ejemplo, dado $[1,3,7,9,13,17,19]$ y $M = 24$ , podemos hacer que $17$ sea la mediana sumando $M$ a los elementos $1$ y $3$ , resultando en el arreglo $[7,9,13,17,19,25,27]$ .

Así, cada elemento es un candidato para $x$ . Calculamos el costo de cada $x$ después del desplazamiento y tomamos el mejor candidato, que es el $x$ que da la menor suma de diferencias absolutas.

Para implementarlo, primero ordenamos $a$ . Luego, consideramos cada elemento de a como un $x$ potencial. Para cada valor candidato, calculamos o bien la cantidad de elementos anteriores que deben aumentarse en $M$ o la cantidad de elementos posteriores que deben disminuirse en $M$ para que este valor sea la mediana. Después, usamos sumas de prefijos para calcular la diferencia absoluta total. Sin embargo, esto requiere acceder a índices de $a$ que no están en el rango $[0, n)$ ; para mitigarlo, anteponemos a $a$ una copia de $a$ con $M$ restado de cada elemento, y añadimos al final una copia de $a$ con $M$ sumado a cada elemento. El rango $[n, 2n)$ de $a$ serán entonces los elementos originales sobre los que enumeramos, y podremos acceder a los elementos que vienen antes o después del arreglo original.

La respuesta final será la menor suma de diferencias absolutas sobre todos esos índices.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$ por caso de prueba

C++Python


#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
 
using namespace std;
 
void solve() {
	int n, m;
	cin >> n >> m;
	vector<long long> a;
	for (int i = 0; i < n; i++) {
		long long value;
		cin >> value;
		value %= m;
		// Los primeros n elementos son - m.
		value -= m;
		a.push_back(value);
	}
	sort(a.begin(), a.end());
	// Los elementos del medio son los originales módulo m, así que volvemos a sumar m.
	for (int i = 0; i < n; i++) { a.push_back(a[i] + m); }
	// Los últimos elementos son +m
	for (int i = 0; i < n; i++) { a.push_back(a[i] + 2 * m); }
 
	vector<long long> prefix_sum;
	prefix_sum.push_back(a[0]);
	for (int i = 1; i < 3 * n; i++) { prefix_sum.push_back(prefix_sum[i - 1] + a[i]); }
 
	long long ans = LLONG_MAX;
	for (int i = n; i < 2 * n; i++) {
		/*
		 * Calcular la diferencia total mínima de cada a[i] a x.
		 * Tratamos la "mediana" como la mediana izquierda si n es par, y
		 * descomponemos en cálculos de izquierda y derecha (porque el signo
		 * del argumento del valor absoluto cambia)
		 */
		long long cost = 0;
 
		// Calcular el costo de la diferencia entre todos los elementos
		// de la izquierda (más pequeños) y el valor actual
		if (n % 2 == 0) {
			/*
			 * Si n es par, sumar los siguientes n/2 - 1 elementos.
			 * Esto es la suma de (a[j] - a[i]) de j = i-(n/2-1) a j=i-1.
			 * El a[i] se factoriza de la suma y da
			 * lo de abajo:
			 */
			cost += a[i] * (n / 2 - 1) - (prefix_sum[i - 1] - prefix_sum[i - n / 2]);
		} else {
			// Para n/2 elementos
			// Esto es la suma de (a[j] - a[i]) de j = i-(n/2) a j=i-1.
			cost += a[i] * (n / 2) - (prefix_sum[i - 1] - prefix_sum[i - n / 2 - 1]);
		}
 
		// Lado derecho del valor actual (más grandes). Siempre n/2 elementos
		// a la derecha. Suma de a[j] - a[i] de j=i+1 a j=i+n/2.
		cost += (prefix_sum[i + n / 2] - prefix_sum[i]) - a[i] * (n / 2);
		ans = min(ans, cost);
	}
	cout << ans << endl;
}
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) { solve(); }
	return 0;
}


t = int(input())
for _ in range(t):
	n, m = map(int, input().split())
	nums = list(map(int, input().split()))
 
	# Módulo, ordenar y construir el arreglo
	rems = sorted([x % m for x in nums])
 
	# s es el arreglo con prefijo/sufijo añadidos
	s = [x - m for x in rems] + rems + [x + m for x in rems]
 
	# sumas de prefijos para consultar rápido las operaciones necesarias
	prefix = [s[0]]
	for i in range(1, len(s)):
		prefix.append(prefix[i - 1] + s[i])
 
	min_total = float("inf")
 
	for i in range(n, 2 * n):
		# Calcular la diferencia total mínima de cada s[i] a x.
		# Tratamos la "mediana" como la mediana izquierda si n es par, y
		# descomponemos en cálculos de izquierda y derecha (porque el signo
		# del argumento del valor absoluto cambia)
		cost = 0
 
		# Calcular el costo de la diferencia entre todos los elementos
		# de la izquierda (más pequeños) y el valor actual
		if n % 2 == 0:
			# Si n es par, sumar los siguientes n//2 - 1 elementos.
			# Esto es la suma de (s[j] - s[i]) de j = i-(n//2-1) a j=i-1.
			# El s[i] se factoriza de la suma y da
			# lo de abajo:
			cost += s[i] * (n // 2 - 1) - (prefix[i - 1] - prefix[i - n // 2])
		else:
			# Si n es impar, hacerlo para n//2 elementos:
			# Esto es la suma de (s[j] - s[i]) de j = i-(n//2) a j=i-1.
			cost += s[i] * (n // 2) - (prefix[i - 1] - prefix[i - n // 2 - 1])
 
		# Lado derecho del valor actual (más grandes). Siempre n//2 elementos
		# a la derecha. Suma de s[j] - s[i] de j=i+1 a j=i+n//2.
		cost += (prefix[i + n // 2] - prefix[i]) - s[i] * (n // 2)
 
		# Actualizar min_total
		min_total = min(min_total, cost)
 
	print(min_total)