USACO Bronze 2017 December - The Bovine Shuffle

Authors: Sathvik Chundru, Jesse Choe, Ryan Chou, David Guo

Appears In

Bronze - Simulation

If the cow in position $i$ moves to position $a_i$ after one shuffle, then after that shuffle the cow sitting at $a_i$ must have come from $i$ .

To undo a single shuffle, for each current position $j$ we find the unique $i$ satisfying $a_i = j$ and move the cow at $j$ back to $i$ . Repeating this step three times recovers the original ordering before any shuffles.

Implementation

Time Complexity: $\mathcal{O}(N)$

C++

#include <bits/stdc++.h>
using namespace std;

const int SHUFFLE_NUM = 3;

int main() {
	freopen("shuffle.in", "r", stdin);
	int n;
	cin >> n;

Java

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(" "))

Python

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):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum