### The Problem

The problem text is shown below (USACO Page): ### Explanation

Sometimes, creating a visual for a problem can give you all the insight you need to solve it. When I saw this problem, the first thing I did was draw out the sample case. I started with the sample case: I made myself a coordinate grid, plotted out the points, and drew the ranges of the walkie-talkies as circles, with the given power of each walkie-talkie as the circle’s radius. This is what my diagram looked like: A (much neater) recreation of my diagram for the given sample case

I then ran through the process in my head, counting out how many cows received the message with each cow as a starting point. I did not skip steps and ran through it as I imagined an algorithm would, giving me the following process for the solution (a signal starting at cow 1 that reaches 3 cows): A diagram demonstrating how the message (red) propagates through the network.

As you may have noticed while watching the signal spread, it did so in such a way that was very similar to the well-known algorithm of Breadth-first search (hereafter BFS). Here is a diagram demonstrating BFS applied to a tree: A BFS algorithm being applied to a tree (source of GIF).

How are the two similar? Both begin at one root point, then spread to all unvisited adjacent nodes (or cows) in the tree before spreading further down the line. Thus, I decided to implement a BFS algorithm to obtain my solution. More specifically, I decided to run a BFS from every cow, keeping track of the number of cows reached by a signal from that cow. In the end, the largest number of cows reached by any BFS (signal) would be my solution.

I implemented this in my code through the common technique of storing a tree through the form of an adjacency list, and I initialized this list once before beginning any BFS by looping through every possible pair of cows, checking which, if any, of the cows could reach the other, and then adding to their adjacency `List`s correspondingly. All that was left was to implement a BFS (I worried about recursion’s impact on memory, so I just used a `Queue`) and keep track of the largest number of cows reached by any one signal. There are plenty of comments in my code, so I will not go through it chunk by chunk and explain what is happening as I have in some previous posts.

### My Solution

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

public class Moocast {
private static String fileNamePrefix = "moocast";

public static void main(String[] args) throws IOException {

int[][] cows = new int[Integer.parseInt(stringTokenizer.nextToken())];

for (int i = 0; i < cows.length; i++) {
int[] cowData = {Integer.parseInt(stringTokenizer.nextToken()), Integer.parseInt(stringTokenizer.nextToken()), Integer.parseInt(stringTokenizer.nextToken())};

cows[i] = cowData;
}

// Represent the tree as adjacency lists (an array of List<Integer>s of cows in range)

// Initialize the lists for each cow
for (int i = 0; i < adjacencies.length; i++)

// Loop through every cow and set up the adjacency lists
for (int cowOne = 0; cowOne < cows.length; cowOne++)
for (int cowTwo = cowOne + 1; cowTwo < cows.length; cowTwo++) {
if (isWithinRange(cows[cowOne], cows[cowTwo]))

if (isWithinRange(cows[cowTwo], cows[cowOne]))
}

// Perform a BFS from each cow and find the longest BFS length
for (int cow = 0; cow < cows.length; cow++) {
// Visited array to ensure we don't check or count the same cow twice
boolean[] visited = new boolean[cows.length];
// BFS path length for cow

// Queue of cows to check
visited[cow] = true;

while (!queue.isEmpty()) {
int currentCow = queue.poll(); // Get the cow at the top of the queue
visited[currentCow] = true;
broadcastStrength++; // This cow has been reached, increase the number of cows in this broadcast

if (!visited[connectedCow]) {
visited[connectedCow] = true;
}
}

// Update the current maximum broadcast strength

}

PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter(fileNamePrefix + ".out")));
writer.close();
}

// Are the x and y coordinates of otherCow inside the circle around thisCow?
private static boolean isWithinRange(int[] thisCow, int[] otherCow) {
// Uses the Pythagorean Theorem to determine the distance between the center of the thisCow circle and otherCow
double distanceSquared = Math.pow(thisCow - otherCow, 2) + Math.pow(thisCow - otherCow, 2);

// If otherCow is in the circle, this distance squared must be less than the radius squared
return distanceSquared <= Math.pow(thisCow, 2);
}
}
``````

### Results

This solution successfully passes all test cases without exceeding the memory or runtime limits, as seen below: 