Mincross

Análisis oficial (C++) 

Explicación

Sea $\texttt{posA}[i]$ la posición de la vaca $i$ en el arreglo $\texttt{A}$ y $\texttt{posB}[i]$ la posición de la vaca $i$ en el arreglo $\texttt{B}$ (donde los arreglos $\texttt{A}$ y $\texttt{B}$ representan los dos lados del camino). Observemos que dos vacas $i$ y $j$ se cruzan si $\texttt{posA}[i] < \texttt{posA}[j]$ y $\texttt{posB}[i] > \texttt{posB}[j]$.

Podemos usar el hecho anterior para calcular el número inicial de cruces. Usando un árbol de estadísticas de orden (Order Statistics Tree), podemos almacenar inicialmente todos los $\texttt{posB}[\texttt{A}[i]]$. Para obtener el número de vacas que se cruzan con la vaca $i$, podemos borrar todos los $\texttt{posB}[\texttt{A}[j]]$ tales que $j < i$ y consultar el número de elementos en el árbol que son menores que $\texttt{posB}[\texttt{A}[i]]$. Para optimizar el borrado, podemos iterar de $1$ a $N$ y borrar cada $\texttt{posB}[\texttt{A}[i]]$ antes de cada consulta.

Para manejar los desplazamientos cíclicos, solo nos importa mover la primera vaca a la última posición. Todos los demás cruces se mantienen constantes. Consideremos desplazar el arreglo $\texttt{B}$ hacia la izquierda:

• Para desconectar los cruces existentes de $\texttt{B}[1]$, debemos restar $\texttt{posA}[\texttt{B}[1]]$ porque sabemos que para todas las posiciones $j$ tales que $j < \texttt{posA}[\texttt{B}[1]]$, $\texttt{A}[j]$ está unida a alguna posición $\texttt{B}[k]$ tal que $k > 1$.
• Ahora, $\texttt{B}[1]$ se convierte en $\texttt{B}[N]$. El número de cruces nuevos es $N - \texttt{posA}[\texttt{B}[N]]$ porque sabemos que para todas las posiciones $j$ tales que $j > \texttt{posA}[\texttt{B}[N]]$, $\texttt{A}[j]$ está unida a alguna posición $\texttt{B}[k]$ tal que $k < N$.

Nuestra respuesta es el mínimo de cruces entre todos los desplazamientos cíclicos. Nótese que también puede que tengamos que considerar desplazar $A$.

Implementación

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

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
 
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
int main() {
	ifstream cin("mincross.in");
	int n;
	cin >> n;
	vector<int> a(n);
	for (int &i : a) {
		cin >> i;
		i--;
	}
	vector<int> b(n);
	for (int &i : b) {
		cin >> i;
		i--;
	}
 
	ll final_ans = LLONG_MAX;
	for (int iter = 0; iter < 2; iter++) {
		vector<int> pos_a(n), pos_b(n);
		for (int i = 0; i < n; i++) {
			pos_a[a[i]] = i;
			pos_b[b[i]] = i;
		}
 
		// compute initial crossings
		ll crossings = 0;
		ordered_set<int> oset;
		for (int i = 0; i < n; i++) { oset.insert(pos_b[i]); }
		for (int i = 0; i < n; i++) {
			oset.erase(pos_b[a[i]]);
			crossings += oset.order_of_key(pos_b[a[i]]);
		}
 
		ll ans = crossings;
		// how many crossings after we perform i + 1 cyclic shifts?
		for (int i = 0; i < n; i++) {
			crossings -= pos_a[b[i]];
			crossings += n - pos_a[b[i]] - 1;
			ans = min(ans, crossings);
		}
 
		final_ans = min(ans, final_ans);
		swap(a, b);  // after first iteration, consider shifting array a instead
	}
 
	ofstream("mincross.out") << final_ans << endl;
}