Skip to Content
CTRL K

The Bovine Shuffle

Análisis oficial (C++ y Java) 

Explicación

Si la vaca en la posición ii se mueve a la posición aia_i después de un shuffle, entonces después de ese shuffle la vaca que está en aia_i debió haber venido de ii.

Para deshacer un shuffle, para cada posición actual jj encontramos el único ii que satisface ai=ja_i = j y movemos la vaca de jj de vuelta a ii. Repetir este paso tres veces recupera el orden original antes de cualquier shuffle.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
const int SHUFFLE_NUM = 3;
 
int main() {
	freopen("shuffle.in", "r", stdin);
	int n;
	cin >> n;
 
	vector<int> shuffle(n);
	for (int &i : shuffle) { cin >> i; }
	vector<int> ids(n);
	for (int &i : ids) { cin >> i; }
 
	for (int i = 0; i < SHUFFLE_NUM; i++) {
		vector<int> past_order(n);
		for (int j = 0; j < n; j++) {
			// -1 porque la entrada del shuffle empieza desde 1
			past_order[j] = ids[shuffle[j] - 1];
		}
		ids = past_order;
	}
 
	freopen("shuffle.out", "w", stdout);
	for (const int &i : ids) { cout << i << '\n'; }
}
import java.io.*;
import java.util.*;
 
public class Shuffle {
	static final int SHUFFLE_NUM = 3;
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("shuffle.in"));
		int n = Integer.parseInt(read.readLine());
		int[] shuffle = Arrays.stream(read.readLine().split(" "))
		                    .mapToInt(Integer::parseInt)
		                    .toArray();
		int[] ids = Arrays.stream(read.readLine().split(" "))
		                .mapToInt(Integer::parseInt)
		                .toArray();
		read.close();
 
		for (int i = 0; i < SHUFFLE_NUM; i++) {
			int[] pastOrder = new int[n];
			for (int j = 0; j < n; j++) {
				// -1 porque la entrada del shuffle empieza desde 1
				pastOrder[j] = ids[shuffle[j] - 1];
			}
			ids = pastOrder;
		}
 
		PrintWriter written = new PrintWriter("shuffle.out");
		for (int i : ids) { written.println(i); }
		written.close();
	}
}
SHUFFLE_NUM = 3
 
with open("shuffle.in") as read:
	n = int(read.readline())
	shuffle = list(map(int, read.readline().split()))
	ids = list(map(int, read.readline().split()))
 
for _ in range(SHUFFLE_NUM):
	past_order = [0] * n
	for i in range(n):
		# -1 porque la entrada del shuffle empieza desde 1
		past_order[i] = ids[shuffle[i] - 1]
	ids = past_order.copy()
 
with open("shuffle.out", "w") as written:
	for i in past_order:
		print(i, file=written)
Fundamentos