USACO Silver 2020 January - Wormhole Sort

Authors: Óscar Garries, Neo Wang, Kevin Sheng

Edit This Page

Official Analysis (Java)

Solution 1 - Binary Search and Floodfill

Time Complexity: O((N+M)log⁡max⁡wi)\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 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(Nlog⁡N)\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 pip_i are in the same component as ii.

Implementation

Time Complexity: O(N+Mα(M))\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!

Join Forum