USACO Silver 2020 January - Wormhole Sort

Authors: Óscar Garries, Neo Wang, Kevin Sheng

Official Analysis (Java)

Solution 1 - Binary Search and Floodfill

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

Implementation

C++

#include <fstream>#include <iostream>#include <vector>
using std::cout;using std::endl;using std::vector;
int main() {	std::ifstream read("wormsort.in");

Java

Warning!

Due to Java's relatively slow speed, the below solution will often TLE on some test cases.

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

C++

#include <fstream>#include <iostream>#include <vector>
using std::cout;using std::endl;using std::vector;
Code Snippet: DSU (Click to expand)


Java

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

C++

#include <algorithm>#include <fstream>#include <iostream>#include <vector>
using std::cout;using std::endl;using std::vector;
Code Snippet: DSU (Click to expand)

Java

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


Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!