Moocast

December 2016 Silver, Problem 3

Algorithm

First, generate an adjacency list using the power of each of the transmitters. Run a DFS starting from each of the cows, and pick the one that reaches the largest number of cows.

Python

# read input
f = open("moocast.in","r").read().split("\n")
n = int(f[0])
walkies = list(map(lambda i:list(map(int,i.split())),f[1:-1]))

# generate adjlist
adjList = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if j != i:
            if (walkies[i][0]-walkies[j][0])**2+(walkies[i][1]-walkies[j][1])**2 <= walkies[i][2]**2:
                adjList[i].append(j)

# run dfs
def dfs(node):
    global adjList, remaining
    remaining.remove(node)
    for i in adjList[node]:
        if i in remaining:
            dfs(i)

res = 0
for node in range(n):
    remaining = list(range(n))
    dfs(node)
    res = max(res,n-len(remaining))

# write output
open("moocast.out","w").write(str(res)+"\n")