USACO Gold 2016 December - Moocast

Authors: Neo Wang, Óscar Garries, Kevin Sheng

Edit This Page

Official Analysis (Java)

Implementation (DSU)

Time Complexity: O(N2log⁡(N2))\mathcal{O}(N^2 \log(N^2))

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 MooCast {
	static class Edge {
		public int a;
		public int b;
		public int dist;
		public Edge(int a, int b, int dist) {
			this.a = a;

Python

from typing import NamedTuple


 Code Snippet: DSU (Click to expand)




class Edge(NamedTuple):
	a: int
	b: int
	dist: int

Implementation (Binary Search + BFS)

Time Complexity: O(N2log⁡(hi))\mathcal{O}(N^2 \log(\text{hi})), where hi≥2⋅250002\text{hi} \ge 2 \cdot 25000^2

An alternative solution involves using binary search and BFS.

Let's define a function that checks if all cows are reachable spending a maximum of power per walkie-talkie. This can be accomplished with BFS.

Notice that since this function is monotonic: if all cows are reachable with a certain power level PP, they will still be reachable with any power level greater than PP.

Therefore, binary search can be employed to find the minimum value of power for which all_reachable(power) holds true.

C++

#include <fstream>
#include <iostream>
#include <queue>
#include <vector>


using std::cout;
using std::endl;
using std::pair;
using std::queue;
using std::vector;

Java

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


public class Moocast {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("moocast.in"));
		int cowNum = Integer.parseInt(read.readLine());
		int[][] cows = new int[cowNum][2];
		for (int c = 0; c < cowNum; c++) {
			StringTokenizer cow = new StringTokenizer(read.readLine());

Implementation (Minimum Spanning Tree)

Time Complexity: O(N2)\mathcal{O}(N^2)

C++

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


int dist_sq(pair<int, int> &a, pair<int, int> &b) {
	int dx = a.first - b.first;
	int dy = a.second - b.second;
	return dx * dx + dy * dy;
}


int main() {

Java

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


public class MooCast {
	static int distSq(int[] a, int[] b) {
		int dx = a[0] - b[0];
		int dy = a[1] - b[1];
		return dx * dx + dy * dy;
	}

Python

def dist_sq(a, b):
	return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2




with open("moocast.in", "r") as stdin:
	N = int(stdin.readline())
	cows = [tuple(map(int, stdin.readline().strip().split())) for _ in range(N)]


dist = {c: float("inf") for c in cows}
dist[cows[0]] = 0

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