Official Analysis (Java)

Video Solution

By Hannah Ying

Note: The video solution might not be the same as other solutions. Code in Java.

Solution 1 (DSU)

Explanation

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: $\mathcal{O}(N^2 \log(N^2))$

Copy
from typing import NamedTuple

 Code Snippet: DSU (Click to expand)


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

Solution 2 (Prim's)

Explanation

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: $\mathcal{O}(N^2)$

Copy
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 $P$, they will still be reachable with any power level greater than $P$.

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

Implementation

Time Complexity: $\mathcal{O}(N^2 \log(\text{hi}))$, where $\text{hi} \ge 2 \cdot 25000^2$

Copy
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):