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]; vector<int> gifts[501]; void dfs(int src, int cur) { if (reachable[src][cur]) return; reachable[src][cur] = true; for (int g : gifts[cur]) 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) for (int g : gifts[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) { gifts[i].resize(N); for (int &g : gifts[i]) cin >> g; while (gifts[i].back() != i) gifts[i].pop_back(); } // either of these work calc_reachable_dfs(); // calc_reachable_floyd(); for (int i = 1; i <= N; ++i) for (int g : gifts[i]) if (reachable[g][i]) { cout << g << "\n"; break; } }
Danny Mittal's code:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringJoiner; import java.util.StringTokenizer; public class RedistributingGifts { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); int[][] rankings = new int[n + 1][n + 1]; for (int cow = 1; cow <= n; cow++) { StringTokenizer tokenizer = new StringTokenizer(in.readLine()); 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++) { int bestGift = 0; for (int gift = 1; gift <= n; gift++) { if (rankings[cow][gift] > rankings[cow][bestGift] && reachable[cow][gift]) { bestGift = gift; } } joiner.add(bestGift + ""); } System.out.println(joiner); } }
Additional Notes: