USACO Silver 2020 January - Wormhole Sort

Authors: Óscar Garries, Neo Wang, Kevin Sheng

Official Analysis (Java)

Solution 1 - Binary Search and Floodfill

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

Implementation

C++

#include <iostream>
#include <fstream>
#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.util.*;
import java.io.*;
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 xx, which is valid if all pip_i are in the same component as ii, which we can query in O(α(N))\mathcal{O}(\alpha(N)) using a Disjoint Set Union.

Implementation

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

C++

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

Java

import java.util.*;
import java.io.*;
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 pip_i are in the same component as ii.

Implementation

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

C++

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

Java

import java.util.*;
import java.io.*;
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!