USACO Silver 2020 January - Wormhole Sort

Official Analysis (Java)

Solution 1 - Binary Search and Floodfill

If a certain wormhole width works, any larger wormhole width will work as well. Similarly, if a width fails, any smaller width will also fail. These two facts make it so that we can binary search on the minimal wormhole width.

To check if a given minimal wormhole width $x$ is valid, we use DFS to find all positions that can reach each other by traversing wormholes at most width $x$. If the cow's initial and sorted positions are both part of the same component, we've found a valid wormhole width!

For example, say we're testing a width of $10$ in the sample case. This makes our components $[0]$, $[1, 2]$, and $[3]$. Cow 1's initial position (3) and its final position (0) aren't in the same component, so this width wouldn't work.

Implementation

Time Complexity: $\mathcal O((N+M)\log \max w_i)$

Copy
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {
	std::ifstream read("wormsort.in");

Copy
import java.io.*;
import java.util.*;

public class WormSort {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("wormsort");

		int cowNum = io.nextInt();
		int wormholeNum = io.nextInt();

Solution 2 - Binary Search and DSU

Like the floodfill solution, we binary search on the answer $x$, which is valid if all $p_i$ are in the same component as $i$, which we can query in $\mathcal{O}(\alpha(N))$ using a Disjoint Set Union.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: DSU (Click to expand)

Copy
import java.io.*;
import java.util.*;

public class WormSort {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("wormsort");

		int cowNum = io.nextInt();
		int wormholeNum = io.nextInt();

Solution 3 - DSU

Due to the DSU's fast query and linking complexity, we can drop the binary search and instead add wormholes from greatest width to least width until all $p_i$ are in the same component as $i$.

Implementation

Time Complexity: $\mathcal{O}(N + M\alpha(M))$

Copy
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: DSU (Click to expand)

Copy
import java.io.*;
import java.util.*;

public class WormSort {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("wormsort");

		int cowNum = io.nextInt();
		int wormholeNum = io.nextInt();