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.