Skip to Content
CTRL K

The Bovine Shuffle

Análisis oficial (Java) 

Explicación

Notemos que si en el barajado hay alguna posición PP que no recibe ninguna vaca, entonces después de un barajado PP no contendrá vacas y por lo tanto estará vacía.

Como PP permanecerá vacía en todos los barajados futuros, entonces la posición alcanzable desde PP también terminará sin vacas en el siguiente barajado, y este efecto se propaga por las posiciones.

En general, observamos que si todas las posiciones que dirigen una vaca a alguna posición PP terminan vacías, entonces PP también quedará vacía. En otras palabras, este proceso termina eliminando todas las posiciones que no están en un ciclo.

Por lo tanto, para cada posición PiP_i, llevamos la cuenta de cuántas posiciones existen que podrían contener vacas indefinidamente y las dirigen a PiP_i después de exactamente un barajado. Tras computar estas cantidades, empezamos una cola de posiciones que están garantizadas a no contener vacas después de cierta cantidad de barajados.

Mantenemos un contador del número de posiciones que contienen vacas indefinidamente, y empezamos asumiendo que todas las posiciones son así.

Como cualquier posición de ese tipo no puede aportar vacas a la posición a la que dirige, debemos decrementar nuestro contador para esa posición y potencialmente agregarla a nuestra cola.

Seguimos procesando posiciones hasta que la cola quede vacía, y la respuesta es el número de posiciones que nunca se encolaron.

Implementación

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

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main() {
	freopen("shuffle.in", "r", stdin);
	freopen("shuffle.out", "w", stdout);
 
	ll n;
	cin >> n;
	vector<ll> a(n);
	vector<ll> cows_after_shuffle(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
		cows_after_shuffle[a[i]]++;
	}
 
	ll ans = n;
	queue<ll> no_cows;
 
	// Calculamos las posiciones que quedan vacías después de un barajado.
	for (int i = 0; i < n; i++) {
		if (cows_after_shuffle[i] == 0) {
			no_cows.push(i);
			ans--;
		}
	}
 
	while (!no_cows.empty()) {
		ll curr = no_cows.front();
		no_cows.pop();
 
		// La posición `curr` no puede aportar ninguna vaca.
		if (--cows_after_shuffle[a[curr]] == 0) {
			// Si `a[curr]` no tiene vacas, la insertamos en la cola.
			no_cows.push(a[curr]);
			ans--;
		}
	}
	cout << ans << endl;
}
import java.io.*;
import java.util.*;
 
public class Shuffle {
	public static int n;
	public static int[] parent;
	public static int[] currStatus;  // 0 no visitado, 1 visitado, 2 es
	                                 // parte de un ciclo
	public static void count(int i) {
		HashSet<Integer> there = new HashSet<Integer>();
		while (currStatus[i] == 0) {
			there.add(i);
			currStatus[i] = 1;
			i = parent[i];
		}
 
		// se encontró un ciclo; marcamos todos los nodos que forman parte del ciclo
		if (there.contains(i)) {
			int savei = i;
			do {
				currStatus[i] = 2;
				i = parent[i];
			} while (i != savei);
		}
	}
	public static void main(String[] args) throws Exception {
		// Leemos el arreglo de padres.
		BufferedReader stdin = new BufferedReader(new FileReader("shuffle.in"));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		n = Integer.parseInt(tok.nextToken());
		StringTokenizer line = new StringTokenizer(stdin.readLine());
 
		parent = new int[n];
		for (int i = 0; i < n; i++) parent[i] = Integer.parseInt(line.nextToken()) - 1;
 
		currStatus = new int[n];
		for (int i = 0; i < n; i++)
			if (currStatus[i] == 0) count(i);
 
		// obtenemos la longitud del ciclo y devolvemos
		int res = 0;
		for (int i = 0; i < n; i++)
			if (currStatus[i] == 2) res++;
 
		PrintWriter out = new PrintWriter(new FileWriter("shuffle.out"));
		out.println(res);
		out.close();
		stdin.close();
	}
}
from collections import deque
 
with open("shuffle.in", "r") as input_file:
	n = int(input_file.readline())
 
	cows_after_shuffle = [0] * n
	a = list(map(int, input_file.readline().split()))
 
	# Calculamos cuántas vacas recibirá una posición después de un barajado.
	for i in range(n):
		a[i] -= 1
		cows_after_shuffle[a[i]] += 1
 
	ans = n
	no_cows = deque()
 
	# Calculamos las posiciones que quedan vacías después de un barajado.
	for i in range(n):
		if cows_after_shuffle[i] == 0:
			no_cows.append(i)
			ans -= 1
 
	while no_cows:
		curr = no_cows.popleft()
 
		# La posición `curr` no puede aportar ninguna vaca.
		cows_after_shuffle[a[curr]] -= 1
 
		# Si `a[curr]` no tiene vacas, la insertamos en la cola.
		if cows_after_shuffle[a[curr]] == 0:
			no_cows.append(a[curr])
			ans -= 1
 
print(ans, file=open("shuffle.out", "w"))
Fundamentos