2022 Feb Gold Problem 1 Redistributing Gifts
Official Problem Statement[edit]
Problem[edit]
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[edit]
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[edit]
The output consists of N lines, each containing the most preferred gift each cow could hope to receive after reassignment.
Solution[edit]
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[edit]
C++[edit]
#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; } } } }
Java[edit]
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(); } }
Python[edit]
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()