2016 Dec Gold Problem 1 Moocast

Official Problem Statement

Moocast

Problem

The Moo-cast problem revolves around Farmer John's cows organizing an emergency "moo-cast" system for broadcasting important messages among themselves. The cows equip themselves with walkie-talkies, which have a limited transmission radius. However, cows can relay messages to one another along a path consisting of several hops, eliminating the need for every cow to transmit directly to every other cow.

Solution

Solution:

• Utilize depth-first search (DFS) or breadth-first search (BFS) algorithms to explore each cow's broadcast range. For each cow, initiate a DFS or BFS and calculate the number of reachable cows.
• For each cow, check whether the distance to other cows is less than or equal to its broadcast radius. If so, the cow can pass the message to the other cow.
• Among all cows, find the one that can transmit the message to the largest number of cows.
• Output the maximum number of cows.

Code (DFS and Flood Fill)

C++

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

struct Cow {
    int i, x, y;
};

vector<Cow> cows;

void dfs(unordered_map<int, vector<pair<int, int>>>& graph, vector<bool>& visited, int node, int val) {
    if (visited[node]) return;
    visited[node] = true;
    for (auto edge : graph[node]) {
        if (visited[edge.first]) continue;
        if (edge.second <= val) dfs(graph, visited, edge.first, val);
    }
}

bool reach(unordered_map<int, vector<pair<int, int>>>& graph, int total, int val) {
    vector<bool> visited(total, false);
    dfs(graph, visited, 0, val);
    return count(visited.begin(), visited.end(), true) >= total;
}

int main() {
    freopen("moocast.in", "r", stdin);
    freopen("moocast.out", "w", stdout);

    int n;
    cin >> n;
    cows.resize(n);
    for (int i = 0; i < n; i++) {
        cows[i].i = i;
        cin >> cows[i].x >> cows[i].y;
    }

    int minDistance = 625000000 * 2, maxDistance = 0;
    unordered_map<int, vector<pair<int, int>>> graph;
    for (Cow cow : cows) {
        for (Cow cow1 : cows) {
            if (cow.i == cow1.i) continue;
            int d = (cow1.x - cow.x) * (cow1.x - cow.x) + (cow1.y - cow.y) * (cow1.y - cow.y);
            minDistance = min(d, minDistance);
            maxDistance = max(d, maxDistance);
            graph[cow.i].push_back({cow1.i, d});
        }
    }

    while (minDistance < maxDistance) {
        int mid = (minDistance + maxDistance) / 2;

        if (reach(graph, n, mid)) {
            maxDistance = mid;
        } else {
            minDistance = mid + 1;
        }
    }

    cout << maxDistance << endl;
}

Java

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

public class MooCast {
    static class Cow {
        int i, x, y;

        public Cow(int i, int x, int y) {
            this.i = i;
            this.x = x;
            this.y = y;
        }
    }

    static List<Cow> cows = new ArrayList<>();

    public static void dfs(Map<Integer, List<Pair<Integer, Integer>>> graph, boolean[] visited, int node, int val) {
        if (visited[node]) return;
        visited[node] = true;
        for (Pair<Integer, Integer> edge : graph.get(node)) {
            if (visited[edge.getKey()]) continue;
            if (edge.getValue() <= val) dfs(graph, visited, edge.getKey(), val);
        }
    }

    public static boolean reach(Map<Integer, List<Pair<Integer, Integer>>> graph, int total, int val) {
        boolean[] visited = new boolean[total];
        dfs(graph, visited, 0, val);
        int count = 0;
        for (boolean visit : visited) {
            if (visit) count++;
        }
        return count >= total;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("moocast.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("moocast.out")));

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            cows.add(new Cow(i, x, y));
        }

        int minDistance = 625000000 * 2, maxDistance = 0;
        Map<Integer, List<Pair<Integer, Integer>>> graph = new HashMap<>();
        for (Cow cow : cows) {
            for (Cow cow1 : cows) {
                if (cow.i == cow1.i) continue;
                int d = (cow1.x - cow.x) * (cow1.x - cow.x) + (cow1.y - cow.y) * (cow1.y - cow.y);
                minDistance = Math.min(d, minDistance);
                maxDistance = Math.max(d, maxDistance);
                graph.computeIfAbsent(cow.i,

Python

from collections import defaultdict

class Cow:
    def __init__(self, i, x, y):
        self.i = i
        self.x = x
        self.y = y

def dfs(graph, visited, node, val):
    if visited[node]:
        return
    visited[node] = True
    for edge in graph[node]:
        if visited[edge[0]]:
            continue
        if edge[1] <= val:
            dfs(graph, visited, edge[0], val)

def reach(graph, total, val):
    visited = [False] * total
    dfs(graph, visited, 0, val)
    return sum(visited) >= total

def main():
    with open('moocast.in', 'r') as fin:
        n = int(fin.readline().strip())
        cows = [Cow(i, *map(int, line.split())) for i, line in enumerate(fin)]

    min_distance = 625000000 * 2
    max_distance = 0
    graph = defaultdict(list)

    for cow in cows:
        for cow1 in cows:
            if cow.i == cow1.i:
                continue
            d = (cow1.x - cow.x)**2 + (cow1.y - cow.y)**2
            min_distance = min(d, min_distance)
            max_distance = max(d, max_distance)
            graph[cow.i].append((cow1.i, d))

    while min_distance < max_distance:
        mid = (min_distance + max_distance) // 2

        if reach(graph, n, mid):
            max_distance = mid
        else:
            min_distance = mid + 1

    with open('moocast.out', 'w') as fout:
        fout.write(str(max_distance) + '\n')

if __name__ == "__main__":
    main()

Code (Union Find)

C++

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

struct Edge {
    int i, j, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

vector<int> parent;

int find(int curr) {
    return parent[curr] == curr ? curr : (parent[curr] = find(parent[curr]));
}

void merge(int x, int y) {
    parent[find(x)] = find(y);
}

int main() {
    ifstream fin("moocast.in");
    ofstream fout("moocast.out");

    int n;
    fin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        fin >> x[i] >> y[i];
    }

    parent.resize(n);
    vector<Edge> edges;
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        for (int j = 0; j < i; j++) {
            int distance = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
            edges.push_back({i, j, distance});
        }
    }

    sort(edges.begin(), edges.end());
    int lastWeight = 0;
    int numComponents = n;
    for (const Edge& curr : edges) {
        if (find(curr.i) != find(curr.j)) {
            merge(curr.i, curr.j);
            lastWeight = curr.w;
            if (--numComponents == 1) {
                break;
            }
        }
    }

    fout << lastWeight << endl;
    fout.close();
}

Java

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

public class MooCast {
    static class Edge implements Comparable<Edge> {
        int i, j, w;

        public Edge(int i, int j, int w) {
            this.i = i;
            this.j = j;
            this.w = w;
        }

        @Override
        public int compareTo(Edge other) {
            return this.w - other.w;
        }
    }

    static int[] parent;

    public static int find(int curr) {
        return parent[curr] == curr ? curr : (parent[curr] = find(parent[curr]));
    }

    public static void merge(int x, int y) {
        parent[find(x)] = find(y);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("moocast.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("moocast.out")));
        int n = Integer.parseInt(br.readLine());
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            x[i] = Integer.parseInt(st.nextToken());
            y[i] = Integer.parseInt(st.nextToken());
        }
        parent = new int[n];
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            for (int j = 0; j < i; j++) {
                int distance = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
                edges.add(new Edge(i, j, distance));
            }
        }
        Collections.sort(edges);
        int lastWeight = 0;
        int numComponents = n;
        for (Edge curr : edges) {
            if (find(curr.i) != find(curr.j)) {
                merge(curr.i, curr.j);
                lastWeight = curr.w;
                if (--numComponents == 1) {
                    break;
                }
            }
        }
        pw.println(lastWeight);
        pw.close();
    }
}

Python

from sys import stdin
import heapq

def find(curr):
    global parent
    return curr if parent[curr] == curr else find(parent[curr])

def merge(x, y):
    global parent
    parent[find(x)] = find(y)

def main():
    with open("moocast.in", "r") as fin:
        n = int(fin.readline().strip())
        coords = [tuple(map(int, fin.readline().split())) for _ in range(n)]

    parent = list(range(n))
    edges = []

    for i in range(n):
        for j in range(i):
            x1, y1 = coords[i]
            x2, y2 = coords[j]
            distance = (x1 - x2) ** 2 + (y1 - y2) ** 2
            heapq.heappush(edges, (distance, i, j))

    last_weight = 0
    num_components = n

    while num_components > 1:
        weight, i, j = heapq.heappop(edges)
        if find(i) != find(j):
            merge(i, j)
            last_weight = weight
            num_components -= 1

    with open("moocast.out", "w") as fout:
        fout.write(str(last_weight) + "\n")

if __name__ == "__main__":
    main()