Cow Checkups

Explicación

Analicemos el último caso de prueba en detalle.

Denotamos como “ubicación deseable” de una vaca una ubicación en la que 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.

Nótese que una contribución solo se puede lograr de una de dos formas.

La primera es si una vaca no estaba en una ubicación deseable y la vaca se movió a una ubicación deseable durante una operación.

La segunda es si una vaca ya estaba en una ubicación deseable y la vaca no se movió durante una operación.

Consideremos cómo calcular las contribuciones creadas estrictamente por el primer escenario.

Sea una vaca en la ubicación $i$ que intenta alcanzar una ubicación deseable en la ubicación $j$ , donde $i < j$ .

La forma más intuitiva de lograrlo es poner $l$ en $i$ y $r$ en $j$ , de modo que después de la operación $i$ se mueve a $j$ .

Observamos que lo mismo vale si ponemos $l$ en $i - 1$ y $r$ en $j + 1$ .

Así, la cantidad de contribuciones que se pueden hacer desde una vaca en la ubicación $i$ y una ubicación deseable en $j$ está limitada por la distancia mínima a cualquiera de los extremos del orden, porque después de eso $l$ o $r$ violarían las restricciones dadas para una operación válida.

En un sistema de indexación desde 0, la contribución de $i$ y $j$ se puede escribir como $\min(i + 1, n - j)$ .

Ahora consideramos cómo calcular las contribuciones creadas estrictamente por el segundo escenario.

Sea una vaca en la posición $i$ que ya está en una ubicación deseable.

La cantidad de contribuciones creadas es igual a la cantidad de operaciones que no involucran a $i$ . En el problema, se nos da que la cantidad de operaciones que pueden ocurrir entre $1$ y $N$ se puede escribir como

\frac{N (N + 1)}{2}.

Así, la cantidad de contribuciones creadas desde una vaca en la ubicación $i$ en una ubicación deseable se puede escribir como la suma de todas las operaciones posibles antes y después de $i$ :

\frac{i \cdot (i + 1)}{2} + \frac{(N - i - 1) \cdot (N - i)}{2}.

Podemos implementar esto recorriendo cada vaca para determinar cuántas contribuciones hace cada vaca del orden inicial.

Como cada vaca o bien está o bien no está ya en una ubicación deseable, el segundo escenario se trata con una simple comprobación de si la vaca está en una ubicación deseable, y luego aplicando la fórmula descrita arriba.

Sin embargo, para el primer escenario, puede haber varias ubicaciones deseables a las que una vaca podría moverse.

Denotemos una vaca y una ubicación deseable que pueden crear contribuciones como se describe en el primer escenario como un par $(i, j)$ .

Si comprobáramos de forma naive cada par, esto tomaría tiempo $\mathcal{O}(N)$ por vaca, ya que en el peor caso cada par de ubicaciones es viable.

Denotemos la distancia mínima de una ubicación deseable a un extremo como $d_{des}$ y la distancia mínima de una vaca a un extremo como $d_{cow}$ , donde $i$ denota la ubicación de la vaca y $j$ la ubicación deseada.

d_{cow} = \min(i + 1, N - i)

d_{des} = \min(j + 1, N - j)

Para una vaca dada, consideremos todas las ubicaciones deseables con las que se puede emparejar. Cada par aporta $\min(d_{cow}, d_{des})$ contribuciones. Así, para acelerar el procesamiento, queremos separar los pares de los que forma parte la vaca dada en dos grupos: aquellos en los que las contribuciones están limitadas por $d_{des}$ porque $d_{des} < d_{cow}$ , y aquellos en los que las contribuciones están limitadas por $d_{cow}$ porque $d_{cow} < d_{des}$ . Podemos particionarlos creando un arreglo ordenado de todos los $d_{des}$ , y luego haciendo búsqueda binaria sobre este arreglo para determinar el índice donde $d_{des} \geq d_{cow}$ . Antes de este índice, las contribuciones estarán limitadas por $d_{des}$ , y después de este índice, por $d_{cow}$ .

Sin embargo, esto sigue resultando en tiempo $\mathcal{O}(N)$ , ya que todavía hay que sumar todas las contribuciones de $d_{des}$ al final.

Podemos optimizarlo implementando un arreglo de sumas de prefijos que sume los índices $[0, i]$ del arreglo $d_{des}$ , de modo que podamos hallar la suma de los $d_{des}$ válidos desde el inicio de una lista hasta cualquier punto en tiempo $\mathcal{O}(1)$ . Luego, todas las contribuciones limitadas por $d_{cow}$ se pueden hallar multiplicando $d_{cow}$ por la cantidad de pares limitados.

Así, la fórmula de las contribuciones del primer escenario se puede hallar como se escribe abajo, dado que $m$ es el punto donde $d_{cow}$ pasa a ser menor que $d_{des}$ :

\text{prefix}[m] + d_{\text{cow}} \cdot (N - m).

Implementación

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

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]; }
 
	// Mapear la especie de una vaca a un arreglo de distancias mínimas al borde
	// de esa especie en el ordenamiento ideal
	unordered_map<int, vector<int>> edge_arrays;
 
	for (int i = 0; i < num_cows; i++) {
		int min_distance_to_edge = min(i + 1, num_cows - i);
 
		// Si todavía no existe un arreglo para una especie de vaca, crear uno
		// nuevo para esa especie
		if (edge_arrays.count(ideal_order[i]) == 0) {
			vector<int> new_edge_array = {min_distance_to_edge};
			edge_arrays.insert(make_pair(ideal_order[i], new_edge_array));
		}
 
		else {
			edge_arrays.at(ideal_order[i]).push_back(min_distance_to_edge);
		}
	}
 
	// Mapear la especie de una vaca a un arreglo de prefijos que suma las
	// contribuciones limitadas por d_desirable
	unordered_map<int, vector<long long>> prefix_arrays;
 
	// iterar por referencia es importante para ordenar
	for (auto &[species, edge_array] : edge_arrays) {
		// Ordenar los arreglos de bordes al iterar para poder hacer búsqueda binaria después
		sort(edge_array.begin(), edge_array.end());
 
		vector<long long> new_prefix_array = {0};
		for (int distance : edge_array) {
			new_prefix_array.push_back(new_prefix_array.back() + distance);
		}
 
		prefix_arrays.insert(make_pair(species, new_prefix_array));
	}
 
	long long total_contributions = 0;
 
	for (long long i = 0; i < num_cows; i++) {
		int species = initial_order[i];
 
		// Captura el caso borde en que una especie existe en el orden inicial
		// pero no en el orden ideal
		if (edge_arrays.count(species) == 0) { continue; }
 
		// Cálculo del escenario 1
		long long min_distance_to_edge = min(i + 1, num_cows - i);
		vector<int> &edge_array =
		    edge_arrays.at(species);  // la referencia es importante para ahorrar tiempo
		int index =
		    upper_bound(edge_array.begin(), edge_array.end(), min_distance_to_edge) -
		    edge_array.begin();  // Devuelve el punto de corte donde d_cow < d_desirable
 
		total_contributions += prefix_arrays.at(
		    species)[index];  // Suma las contribuciones limitadas por d_desirable
		total_contributions +=
		    (min_distance_to_edge) * ((long long)edge_array.size() -
		                              index);  // Suma las contribuciones limitadas por d_cow
 
		// Cálculo del escenario 2
		if (initial_order[i] == ideal_order[i]) {
			total_contributions +=
			    ((i * (i + 1)) / 2) + ((num_cows - i - 1) * (num_cows - i) / 2);
		}
	}
 
	cout << total_contributions << endl;
}


import bisect
 
num_cows = int(input())
initial_order = [int(x) for x in input().split()]
ideal_order = [int(x) for x in input().split()]
 
# Mapear la especie de una vaca a un arreglo de distancias mínimas al borde de esa especie en el ordenamiento ideal
edge_arrays = dict()
 
for i in range(num_cows):
	min_distance_to_edge = min(i + 1, num_cows - i)
 
	# Si todavía no existe un arreglo para una especie de vaca, crear uno nuevo para esa especie
	if ideal_order[i] not in edge_arrays:
		edge_arrays[ideal_order[i]] = [min_distance_to_edge]
 
	else:
		edge_arrays[ideal_order[i]].append(min_distance_to_edge)
 
# Mapear la especie de una vaca a un arreglo de prefijos que suma las contribuciones limitadas por d_desirable
prefix_arrays = dict()
 
for species, edge_array in edge_arrays.items():
	# Ordenar los arreglos de bordes al iterar para poder hacer búsqueda binaria después
	edge_array.sort()
 
	new_prefix_array = [0]
	for distance in edge_array:
		new_prefix_array.append(new_prefix_array[-1] + distance)
 
	prefix_arrays[species] = new_prefix_array
 
total_contributions = 0
 
for i in range(num_cows):
	species = initial_order[i]
 
	# Captura el caso borde en que una especie existe en el orden inicial pero no en el orden ideal
	if species not in edge_arrays:
		continue
 
	# Cálculo del escenario 1
	min_distance_to_edge = min(i + 1, num_cows - i)
	index = bisect.bisect(edge_arrays[species], min_distance_to_edge)
 
	total_contributions += prefix_arrays[species][index]
	total_contributions += (min_distance_to_edge) * (len(edge_arrays[species]) - index)
 
	# Cálculo del escenario 2
	if initial_order[i] == ideal_order[i]:
		total_contributions += ((i * (i + 1)) // 2) + (
			((num_cows - i - 1) * (num_cows - i)) // 2
		)
 
print(total_contributions)