USACO 2022 February Contest, Silver Problem 1. Redistributing Gifts

USACO 2022 February Contest, Silver Problem 1. Redistributing Gifts

Farmer John has NN gifts labeled 1N1…N for his NN cows, also labeled 1N1…N (1N5001≤N≤500). Each cow has a wishlist, which is a permutation of all NN 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 ii to cow ii for all ii. 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 ii from 11 to NN, compute the most preferred gift cow ii could hope to receive after reassignment.

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

The first line contains NN. The next NN lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of 1N1…N.

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

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

SAMPLE INPUT:

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4

SAMPLE OUTPUT:

1
3
2
4

In this example, there are two possible reassignments:

  • The original assignment: cow 11 receives gift 11, cow 22 receives gift 22, cow 33 receives gift 33, and cow 44 receives gift 44.
  • Cow 11 receives gift 11, cow 22 receives gift 33, cow 33 receives gift 22, and cow 44 receives gift 44.

Observe that both cows 11 and 44 cannot hope to receive better gifts than they were originally assigned. However, both cows 22 and 33 can.

SCORING:

 

  • Test cases 2-3 satisfy N8N≤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 GG with vertices labeled 1N1…N that contains an edge iji→j if i=ji=j or cow ii prefers gift jj to gift ii. For the sample case, GG 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 GG 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 GG's edges: {11,23,32,44}{1→1,2→3,3→2,4→4}. This subset of edges partitions the vertices of GG into three cycles: a self-loop involving 11, a loop involving 22 and 33, and another self-loop involving 44.

Observation 1: There is a distribution where cow ii receives gift jj if and only if GG has a simple cycle containing edge iji→j.

Proof:

Only If: A distribution where cow ii receives cow jj corresponds to a partition of the vertices of GG into some number of simple cycles containing the edge iji→j. It follows that one of those simple cycles contains the edge iji→j.

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

Observation 2: Using the first observation, GG has a simple cycle containing edge iji→j if and only if there exists a path from jj to ii.

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

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

 

#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)O(M) time, where MM is the number of edges in GG, by computing the strongly connected components of GG.
  • 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.

[/hide]

翰林国际教育资讯二维码