Cow Checkups

Explicación

Denotamos como “ubicación deseable” de una vaca una ubicación donde una vaca de esa especie será revisada por el veterinario bovino.

Denotamos como “contribución” una instancia de una vaca que se mueve a una ubicación deseable.

Observamos que, para una operación dada con extremos $l$ y $r$ , una operación con extremos $l - 1$ y $r + 1$ mueve las vacas de $l$ a $r$ a las mismas ubicaciones, y además intercambia $l - 1$ y $r + 1$ . Por lo tanto, solo los dos extremos recién agregados pueden cambiar si una vaca está en una ubicación deseable.

Así, podemos empezar en todas las operaciones donde $l = r$ , y luego expandir gradualmente las operaciones decrementando $l$ e incrementando $r$ hasta que la operación deje de ser válida, y calcular cuántas contribuciones agregan los extremos cada vez que expandimos la operación. Esto solo calcula todas las operaciones de longitud impar, así que hacemos lo mismo empezando desde $l = r - 1$ , para calcular todas las operaciones de longitud par.

Una expansión puede agregar o restar una contribución:

Puede agregar una contribución al mover una vaca de una ubicación previamente no deseable a una ubicación deseable.
Puede restar una contribución al mover una vaca de una ubicación previamente deseable a una ubicación no deseable.

Esto se puede comprobar con unas pocas sentencias if simples durante la iteración.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++Python


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int num_cows;
	cin >> num_cows;
 
	vector<int> initial_order(num_cows);
 
	for (int i = 0; i < num_cows; i++) { cin >> initial_order[i]; }
 
	vector<int> ideal_order(num_cows);
 
	for (int i = 0; i < num_cows; i++) { cin >> ideal_order[i]; }
 
	// Guardar la cantidad de operaciones que resultan en N vacas revisadas como un arreglo donde
	// operations[N vacas revisadas] = cantidad de operaciones
	vector<int> operations(num_cows + 1);
 
	// Calcular la cantidad de vacas que ya están en una ubicación deseable
	int correct_placement = 0;
	for (int i = 0; i < num_cows; i++) {
		if (initial_order[i] == ideal_order[i]) { correct_placement++; }
	}
 
	// Iteración de subarreglos de longitud impar
	for (int i = 0; i < num_cows; i++) {
		int left = i;
		int right = i;
 
		// current_placement = (# vacas movidas a posiciones correctas) - (# vacas sacadas
		// de posiciones correctas)
		int current_placement = 0;
 
		while (left >= 0 and right < num_cows) {
			if (initial_order[left] == ideal_order[right]) { current_placement++; }
 
			if (initial_order[right] == ideal_order[left]) { current_placement++; }
 
			if (initial_order[left] == ideal_order[left]) { current_placement--; }
 
			if (initial_order[right] == ideal_order[right]) { current_placement--; }
 
			operations[current_placement + correct_placement]++;
 
			left--;
			right++;
		}
	}
 
	// Iteración de subarreglos de longitud par
	for (int i = 1; i < num_cows; i++) {
		int left = i - 1;
		int right = i;
 
		// current_placement = (# vacas movidas a posiciones correctas) - (# vacas sacadas
		// de posiciones correctas)
		int current_placement = 0;
 
		while (left >= 0 and right < num_cows) {
			if (initial_order[left] == ideal_order[right]) { current_placement++; }
 
			if (initial_order[right] == ideal_order[left]) { current_placement++; }
 
			if (initial_order[left] == ideal_order[left]) { current_placement--; }
 
			if (initial_order[right] == ideal_order[right]) { current_placement--; }
 
			operations[current_placement + correct_placement]++;
 
			left--;
			right++;
		}
	}
 
	for (int op : operations) { cout << op << "\n"; }
}


num_cows = int(input())
initial_order = [int(x) for x in input().split()]
ideal_order = [int(x) for x in input().split()]
 
# Guardar la cantidad de operaciones que resultan en N vacas revisadas como un arreglo donde
# operations[N vacas revisadas] = cantidad de operaciones
operations = [0 for i in range(num_cows + 1)]
 
# Calcular la cantidad de vacas que ya están en una ubicación deseable
correct_placement = 0
for i in range(num_cows):
	if initial_order[i] == ideal_order[i]:
		correct_placement += 1
 
# Iteración de subarreglos de longitud impar
for i in range(num_cows):
	left = i
	right = i
 
	# current_placement = (# vacas movidas a posiciones correctas) - (# vacas sacadas de posiciones correctas)
	current_placement = 0
 
	while left >= 0 and right < num_cows:
		if initial_order[left] == ideal_order[right]:
			current_placement += 1
 
		if initial_order[right] == ideal_order[left]:
			current_placement += 1
 
		if initial_order[left] == ideal_order[left]:
			current_placement -= 1
 
		if initial_order[right] == ideal_order[right]:
			current_placement -= 1
 
		operations[current_placement + correct_placement] += 1
 
		left -= 1
		right += 1
 
# Iteración de subarreglos de longitud par
for i in range(1, num_cows):
	left = i - 1
	right = i
 
	# current_placement = (# vacas movidas a posiciones correctas) - (# vacas sacadas de posiciones correctas)
	current_placement = 0
 
	while left >= 0 and right < num_cows:
		if initial_order[left] == ideal_order[right]:
			current_placement += 1
 
		if initial_order[right] == ideal_order[left]:
			current_placement += 1
 
		if initial_order[left] == ideal_order[left]:
			current_placement -= 1
 
		if initial_order[right] == ideal_order[right]:
			current_placement -= 1
 
		operations[current_placement + correct_placement] += 1
 
		left -= 1
		right += 1
 
for op in operations:
	print(op)