Home » 国际竞赛 » Details

USACO 2022 February Contest, Silver Problem 1. Redistributing Gifts

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午5:14

USACO 2022 February Contest, Silver Problem 1. Redistributing Gifts

Farmer John has $N$ gifts labeled $1 \dots N$ for his $N$ cows, also labeled $1 \dots N$ ( $1 \leq N \leq 500$ ). Each cow has a wishlist, which is a permutation of all $N$ gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.

FJ was lazy and just assigned gift $i$ to cow $i$ for all $i$ . Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.

For each $i$ from $1$ to $N$ , compute the most preferred gift cow $i$ could hope to receive after reassignment.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ . The next $N$ lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of $1 \dots N$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Please output $N$ lines, the $i$ -th of which contains the most preferred gift cow $i$ could hope to receive after reassignment.

SAMPLE INPUT:

SAMPLE OUTPUT:

In this example, there are two possible reassignments:

The original assignment: cow $1$ receives gift $1$ , cow $2$ receives gift $2$ , cow $3$ receives gift $3$ , and cow $4$ receives gift $4$ .
Cow $1$ receives gift $1$ , cow $2$ receives gift $3$ , cow $3$ receives gift $2$ , and cow $4$ receives gift $4$ .

Observe that both cows $1$ and $4$ cannot hope to receive better gifts than they were originally assigned. However, both cows $2$ and $3$ can.

SCORING:

Test cases 2-3 satisfy $N \leq 8$ .
Test cases 4-11 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2022 February Contest, Silver Problem 1. Redistributing Gifts 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Let's start by constructing a directed graph $G$ with vertices labeled $1 \dots 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. $◼$

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

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.