(Analysis by Benjamin Qi)

Let's start by constructing a directed graph $G$ with vertices labeled $1\ldots N$ that contains an edge $i\to j$ if $i=j$ or cow $i$ prefers gift $j$ to gift $i$. For the sample case, $G$ would contain the following edges:

1 -> 1
2 -> 1
2 -> 3
2 -> 2
3 -> 1
3 -> 2
3 -> 3
4 -> 1
4 -> 2
4 -> 3
4 -> 4


There is a one-to-one correspondence between valid distributions and partitions of the vertices of $G$ into simple cycles. For example, assigning gift 1 to cow 1, gift 3 to cow 2, gift 2 to cow 3, and gift 4 to cow 4 would correspond to the following subset of $G$'s edges: $\{1\to 1, 2\to 3, 3\to 2, 4\to 4\}$. This subset of edges partitions the vertices of $G$ into three cycles: a self-loop involving $1$, a loop involving $2$ and $3$, and another self-loop involving $4$.

Observation 1: There is a distribution where cow $i$ receives gift $j$ if and only if $G$ has a simple cycle containing edge $i\to j$.

Proof:

Only If: A distribution where cow $i$ receives cow $j$ corresponds to a partition of the vertices of $G$ into some number of simple cycles containing the edge $i\to j$. It follows that one of those simple cycles contains the edge $i\to j$.

If: Suppose there exists a simple cycle $C$ containing $i\to j$. Then we can assign each cow along $C$ the gift originally given to the next cow along the cycle, and every cow along $C$ will end up strictly better off. Let all cows not along $C$ receive their original gifts. This corresponds to a valid distribution. $\blacksquare$

Observation 2: Using the first observation, $G$ has a simple cycle containing edge $i\to j$ if and only if there exists a path from $j$ to $i$.

Solution: In $\mathcal{O}(N^3)$ time, compute all pairs of vertices $(i,j)$ such that there exists a path from $i$ to $j$. In the code below, we set $\texttt{reachable}[i][j]=1$ if such a path exists. The most straightforward way to do this is to start a depth-first search from each $i$. Alternatively, we can use Floyd-Warshall with bitsets to shave a constant factor off the runtime.

After that, for each cow $i$, it remains to iterate over her preference list and output the first gift $g$ such that there exists a path from $g$ to $i$.

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

int N;
bitset<501> reachable[501];

void dfs(int src, int cur) {
if (reachable[src][cur])
return;
reachable[src][cur] = true;
dfs(src, g);
}

void calc_reachable_dfs() {
for (int i = 1; i <= N; ++i)
dfs(i, i);
}

void calc_reachable_floyd() {
for (int i = 1; i <= N; ++i)
reachable[i][g] = true;
for (int k = 1; k <= N; ++k) // run floyd-warshall
for (int i = 1; i <= N; ++i)
if (reachable[i][k])
reachable[i] |= reachable[k];
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
assert(N <= 500);
for (int i = 1; i <= N; ++i) {
cin >> g;
}

// either of these work
calc_reachable_dfs();
// calc_reachable_floyd();

for (int i = 1; i <= N; ++i)
if (reachable[g][i]) {
cout << g << "\n";
break;
}
}


Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringJoiner;
import java.util.StringTokenizer;

public static void main(String[] args) throws IOException {
int[][] rankings = new int[n + 1][n + 1];
for (int cow = 1; cow <= n; cow++) {
for (int rank = n; rank > 0; rank--) {
rankings[cow][Integer.parseInt(tokenizer.nextToken())] = rank;
}
}
boolean[][] reachable = new boolean[n + 1][n + 1];
for (int cow1 = 1; cow1 <= n; cow1++) {
for (int cow2 = 1; cow2 <= n; cow2++) {
if (rankings[cow1][cow2] >= rankings[cow1][cow1]) {
reachable[cow2][cow1] = true;
}
}
}
for (int cow2 = 1; cow2 <= n; cow2++) {
for (int cow1 = 1; cow1 <= n; cow1++) {
for (int cow3 = 1; cow3 <= n; cow3++) {
reachable[cow1][cow3] = reachable[cow1][cow3] || (reachable[cow1][cow2] && reachable[cow2][cow3]);
}
}
}
StringJoiner joiner = new StringJoiner("\n");
for (int cow = 1; cow <= n; cow++) {
}
}
}
System.out.println(joiner);
}
}


• This problem was inspired by the Top trading cycle algorithm.
• It is actually possible to solve this problem in $O(M)$ time, where $M$ is the number of edges in $G$, by computing the strongly connected components of $G$.
• Alternatively, this problem can be phrased as finding all edges that may be part of a perfect matching in a bipartite graph, given an initial perfect matching.