2022 Feb Gold Problem 1 Redistributing Gifts

Official Problem Statement

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++

#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

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

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()