Editing
2022 Feb Gold Problem 1 Redistributing Gifts
Jump to navigation
Jump to search
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Official Problem Statement == [http://www.usaco.org/index.php?page=viewproblem2&cpid=1209 Redistributing Gifts] == Problem == Farmer John has assigned gifts to his cows, but the cows decide to reassign the gifts among themselves. Each cow has a preference list for the gifts and they want to exchange gifts in such a way that every cow ends up with the same gift as she did originally, or a gift that she prefers more. The goal is to determine, for each cow, the most preferred gift that she could receive after reassignment. === Input Format === The first line contains the number of cows and gifts, N (1 β€ N β€ 500). The next N lines each contain the preference list of a cow. Each line is a permutation of the numbers 1 through N. === Output Format === The output consists of N lines, each containing the most preferred gift each cow could hope to receive after reassignment. == Solution == The solution for this problem revolves around the construction of a directed graph G and then finding valid distributions that correlate to simple cycle partitions in the vertices of G. Here are the steps to the solution: * Construction of Directed Graph: We start by creating a directed graph G, where the vertices are labelled from 1 to N. Each vertex i represents a cow and it contains an edge i->j if i equals j or if cow i prefers gift j over gift i. In simpler words, this graph is a representation of cows and their gift preferences. * Cycle Partition and Distributions: There is a one-to-one correlation between valid distributions of gifts and partitions of the vertices of G into simple cycles. For instance, a distribution where gift 1 is assigned to cow 1, gift 3 to cow 2, gift 2 to cow 3, and gift 4 to cow 4, it corresponds to a subset of G's edges: {1β1, 2β3, 3β2, 4β4}. This subset of edges partitions the vertices of G into three cycles: a self-loop at 1, a loop involving 2 and 3, and another self-loop at 4. * Distribution Validation: A distribution where cow i receives gift j is valid if and only if G has a simple cycle containing edge i->j. This cycle can be confirmed to exist if there's a path from j to i in the graph. * Cycle Detection and Preference List: In O(N^3) time, the solution calculates all pairs of vertices (i,j) such that a path exists from i to j. For every cow i, it then iterates over her preference list and outputs the first gift g such that there exists a path from g to i. The core part of the solution lies in the concept of graph theory, particularly in finding cycles and paths in a directed graph. Each cow's preference list is used to create the graph and later, to determine the most preferred gift she can receive after redistribution. == Code == === C++ === <pre> #include <bits/stdc++.h> using namespace std; void depthFirstSearch(int src, int cur, vector<vector<int>>& gifts, vector<vector<bool>>& reachable) { if (reachable[src][cur]) { return; } reachable[src][cur] = true; for (int gift : gifts[cur]) { depthFirstSearch(src, gift, gifts, reachable); } } void computeReachability(vector<vector<int>>& gifts, vector<vector<bool>>& reachable, int cowCount) { for (int i = 0; i < cowCount; ++i) { depthFirstSearch(i, i, gifts, reachable); } } int main() { int cowCount; cin >> cowCount; vector<vector<int>> giftPreferenceList(cowCount); vector<vector<int>> preferenceGraph(cowCount); vector<bool> temp(cowCount, false); vector<vector<bool>> reachable(cowCount, temp); bool preferredGiftAvailable; for(int i = 0; i < cowCount; i++){ preferredGiftAvailable = true; for(int j = 0; j < cowCount; j++){ int a; cin >> a; a--; giftPreferenceList[i].push_back(a); if(preferredGiftAvailable){ preferenceGraph[i].push_back(a); } if(i == a){ preferredGiftAvailable = false; } } } computeReachability(preferenceGraph, reachable, cowCount); for (int i = 0; i < cowCount; i++){ for (int gift : giftPreferenceList[i]){ if (reachable[gift][i]) { cout << gift + 1 << "\n"; break; } } } } </pre> === Java === <pre> import java.util.*; public class Main { static List<Integer>[] giftPreferenceList; static boolean[][] reachable; public static void depthFirstSearch(int src, int cur) { if (reachable[src][cur]) { return; } reachable[src][cur] = true; for (int gift : giftPreferenceList[cur]) { depthFirstSearch(src, gift); } } public static void computeReachability() { for (int i = 0; i < giftPreferenceList.length; ++i) { depthFirstSearch(i, i); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int cowCount = scanner.nextInt(); giftPreferenceList = new ArrayList[cowCount]; reachable = new boolean[cowCount][cowCount]; boolean preferredGiftAvailable; for (int i = 0; i < cowCount; i++) { giftPreferenceList[i] = new ArrayList<>(); preferredGiftAvailable = true; for (int j = 0; j < cowCount; j++) { int a = scanner.nextInt() - 1; giftPreferenceList[i].add(a); if (i == a) { preferredGiftAvailable = false; } } } computeReachability(); for (int i = 0; i < cowCount; i++) { for (int gift : giftPreferenceList[i]) { if (reachable[gift][i]) { System.out.println(gift + 1); break; } } } scanner.close(); } } </pre> === Python === <pre> def dfs(src, cur, gifts, reachable): if reachable[src][cur]: return reachable[src][cur] = True for g in gifts[cur]: dfs(src, g, gifts, reachable) def calc_reachable_dfs(gifts, reachable, N): for i in range(N): dfs(i, i, gifts, reachable) def main(): N = int(input()) giftlist = [] reachable = [[False for _ in range(N)] for _ in range(N)] for _ in range(N): better = True gift_preference = list(map(int, input().split())) gift_preference = [g - 1 for g in gift_preference] giftlist.append([]) for g in gift_preference: if better: giftlist[-1].append(g) if g == len(giftlist) - 1: better = False calc_reachable_dfs(giftlist, reachable, N) for i in range(N): for g in giftlist[i]: if reachable[g][i]: print(g + 1) break if __name__ == "__main__": main() </pre> [[Category:Yearly_2021_2022]] [[Category:Gold]] [[Category:Binary Search]] [[Category:Prefix Sum]] [[Category:Greedy]]
Summary:
Please note that all contributions to Wiki may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
My wiki:Copyrights
for details).
Do not submit copyrighted work without permission!
Cancel
Editing help
(opens in new window)
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Page
Discussion
English
Views
Read
Edit
View history
More
Search
Navigation
Main page
Recent changes
Random page
Help about MediaWiki
Tools
What links here
Related changes
Special pages
Page information