2020 Jan Silver Problem 3 Wormhole Sort

Problem Statement

n the USACO problem titled "Wormhole Sort" (ID 992), you are given N cows located at integer points on a number line. There are M wormholes, and each wormhole connects two locations. Each wormhole has a width W, and a cow can only pass through the wormhole if the width is at least as large as the cow's size. Farmer John wants to sort the cows in increasing order of their size using the wormholes, such that each cow can travel from its original position to its final position in the sorted order.

Your task is to find the minimum width W required for all wormholes so that the cows can be sorted. If it is impossible to sort the cows using the wormholes, output -1.

Solution

A solution to this problem can be found using a binary search on the width W and the Union-Find data structure to track connected components of the graph formed by the wormholes.

C++ code example:

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<pair<int, int>> cows;
vector<tuple<int, int, int>> wormholes;
vector<int> parent;

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    parent[a] = b;
    return true;
}

bool can_sort(int min_width) {
    parent.resize(N);
    iota(parent.begin(), parent.end(), 0);

    for (auto &[width, a, b] : wormholes) {
        if (width >= min_width) {
            merge(a, b);
        }
    }

    for (int i = 0; i < N; i++) {
        if (find(i) != find(cows[i].second)) {
            return false;
        }
    }

    return true;
}

int main() {
    cin >> N >> M;
    cows.resize(N);
    wormholes.resize(M);

    for (int i = 0; i < N; i++) {
        cin >> cows[i].first;
        cows[i].second = i;
    }

    for (int i = 0; i < M; i++) {
        int a, b, width;
        cin >> a >> b >> width;
        wormholes[i] = make_tuple(width, a - 1, b - 1);
    }

    sort(cows.begin(), cows.end());

    int low = 1, high = 1e9 + 1;

    while (low < high) {
        int mid = (low + high) / 2;

        if (can_sort(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    if (low == 1e9 + 1) {
        cout << -1 << endl;
    } else {
        cout << low << endl;
    }

    return 0;
}