Official Analysis (Java)

Explanation (DSU)

We can build edges between every pair of cows. After sorting the edges based on weight we can use a DSU. Doing so ensures that we include every cow only once through the smallest weights possible.

Implementation

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

Explanation (Prim's)

We can build edges between every pair of cows. We can then construct an MST by greedily selecting the nearest node every time. This guarantees that we include every cow in the network by using the smallest weights possible.

Implementation

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

Explanation (Binary Search + BFS)

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.

Implementation

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

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

Python

from collections import deque




def build_adj(cows):
	n = len(cows)
	adj = [[] for _ in range(n)]
	max_dist = 0
	for i, (xi, yi) in enumerate(cows):
		neighbors = []
		for j, (xj, yj) in enumerate(cows):

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