Official Analysis (Java)

Explanation

Notice that if in the shuffle there is some position $P$ that doesn't receive any cows, then after one shuffle, $P$ will contain no cows and thus be empty.

Since $P$ will remain empty for all future shuffles, then the position reachable from $P$ will also eventually contain no cows in the next shuffle, and this effect propagates throughout the positions.

In general, we observe that if all the positions that direct a cow to some position $P$ eventually become empty, then $P$ will also become empty. In other words, this process ends up eliminating all non-cycle positions.

Therefore, for every position $P_i$, we keep track of how many positions exist which could indefinitely contain cows and direct them to $P_i$ after exactly one shuffle. After computing these quantities, we start a queue of positions which are guaranteed to never contain cows after some number of shuffles.

We keep a counter for the number of positions that contain cows indefinitely, and start by assuming all positions as such.

Since any such position cannot contribute cows to the position it directs to, we must decrement our counter for that position and potentially add it to our queue.

We continue processing positions until our queue is empty, and the answer is the number of positions that were never enqueued.

Implementation

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

Copy
#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;

Copy
import java.io.*;
import java.util.*;

public class Shuffle {
	public static int n;
	public static int[] parent;
	public static int[] currStatus;  // 0 is not-visited, 1 is visited, 2 is
	                                 // part of cycle
	public static void count(int i) {
		HashSet<Integer> there = new HashSet<Integer>();

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

	# Calculate number of cows that a position will receive after one shuffle.
	for i in range(n):