USACO 2017 December Contest Bronze Division - The Bovine Shuffle

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We want to do something similar to how we would find cycles in a permutation, but in reverse, since we have to undo the process 3 times.

Source codes

The source codes in C++ and Python can be seen below.

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

int main()
{
    ifstream cin("shuffle.in");
    ofstream cout("shuffle.out");

    int n;
    cin >> n;

    vector<int> dirs(n+1), tdir(n+1);
    vector<int> numbers(n+1);

    for(int i = 1; i <= n; i++)
        cin >> dirs[i], tdir[dirs[i]] = i;
    for(int i = 1; i <= n; i++)
        cin >> numbers[i];

    for(int i = 1; i <= 3; i++)
    {
        vector<int> numbers2(n+1);
        for(int j = 1; j <= n; j++)
            numbers2[tdir[j]] = numbers[j];
        numbers = numbers2;
    }

    for(int i = 1; i <= n; i++)
        cout << numbers[i] << '\n';
    return 0;
}

with open("shuffle.in", "r") as fin:
    tokens = fin.read().split()

n = int(tokens[0])
dirs = [0] * (n + 1)
tdir = [0] * (n + 1)
numbers = [0] * (n + 1)

index = 1
for i in range(1, n + 1):
    dirs[i] = int(tokens[index])
    index += 1
    tdir[dirs[i]] = i

for i in range(1, n + 1):
    numbers[i] = int(tokens[index])
    index += 1

for _ in range(3):
    numbers2 = [0] * (n + 1)
    for j in range(1, n + 1):
        numbers2[tdir[j]] = numbers[j]
    numbers = numbers2

with open("shuffle.out", "w") as fout:
    for i in range(1, n + 1):
        fout.write(str(numbers[i]) + "\n")