USACO 2022 February Contest, Gold Problem 3. Moo Network

USACO 2022 February Contest, Gold Problem 3. Moo Network

Farmer John's NN cows (1N1051≤N≤105) are spread far apart on his farm and would like to build a communication network so they can more easily exchange electronic text messages (all of which of course contain variations of "moo").

The iith cow is located at a distinct location (xi,yi)(xi,yi) where 0xi1060≤xi≤106 and 0yi100≤yi≤10. The cost of building a communication link between cows ii and jj is the squared distance between them: (xixj)2+(yiyj)2(xi−xj)2+(yi−yj)2.

Please calculate the minimum cost required to build a communication network across which all the cows can communicate. Two cows can communicate if they are directly connected by a link, or if there is a sequence of links along which their message can travel.

**Note: the time limit for this problem is 4s, twice the default.**

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN, and the next NN lines each describe the xx and yy coordinates of a cow, all integers.

OUTPUT FORMAT (print output to the terminal / stdout):

Please output the minimum cost of a network that will allow all cows to communicate. Note that this cost might be too large to fit into a 32-bit integer and may require use of 64-bit integers (e.g., "long long" integers in C++).

SAMPLE INPUT:

10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0

SAMPLE OUTPUT:

660

SCORING:

  • Test cases 2-3 satisfy N1000N≤1000.
  • Test cases 4-15 satisfy no additional constraints.

Problem credits: Brian Dean

 USACO 2022 February Contest, Gold Problem 3. Moo Network 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Richard Qi, Benjamin Qi)

Let the cows be nodes of a graph, where an edge is between every pair of cows with weight equal to the squared distance between them. Our goal is to find a Minimum Spanning Tree of this graph.

Partial Credit: Because there are a total of O(N2)O(N2) edges, we can run Kruskal's or Prim's to solve this task in O(N2logN)O(N2log⁡N) or O(N2)O(N2). A few modifications to the code from the Moocast analysis suffice.

Nick Wu's code:

 

import java.io.*;
import java.util.*;
public class MooNetworkSlow {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.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<Edge>();
		for(int i = 0; i < n; i++) {
			parent[i] = i;
			for(int j = 0; j < i; j++) {
				long distance = (long)(x[i] - x[j]) * (x[i] - x[j]) + (long)(y[i] - y[j]) * (y[i] - y[j]);
				edges.add(new Edge(i, j, distance));
			}
		}
		Collections.sort(edges);
		long sumWeights = 0;
		int numComponents = n;
		for(Edge curr: edges) {
			if(find(curr.i) != find(curr.j)) {
				merge(curr.i, curr.j);
				sumWeights += curr.w;
				if(--numComponents == 1) {
					break;
				}
			}
		}
		pw.println(sumWeights);
		pw.close();
	}
	
	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);
	}
	
	static class Edge implements Comparable<Edge> {
		public int i, j;
		public long w;
		public Edge(int a, int b, long c){
			i=a;
			j=b;
			w=c;
		}
		public int compareTo(Edge e) {
			return Long.signum(w-e.w);
		}
	}
	
}

Full Credit: The main idea is to reduce the number of edges we need to consider to O(N)O(N), using the special condition that 0yi100≤yi≤10.

We use this important fact: consider 33 nodes of a graph aabbcc. Suppose that the weights of the three edges between these nodes satisfies wbc<wabwbc<wab and wac<wabwac<wab. Then, the minimum spanning tree can be chosen such that edge abab is not present. This can be proven by analyzing Kruskal's algorithm: the algorithm first encounters bcbc and acac in the sort order, immediately after which aa and bb must be connected. So, when abab is encountered, aa and bb are already connected.

Now, given points a=(x1,y1),c=(x2,y2),b=(x3,y3)a=(x1,y1),c=(x2,y2),b=(x3,y3) such that x1x2<x3x1≤x2<x3 and y2=y3,y2=y3, we don't need to consider the edge between (x1,y1)(x1,y1) and (x3,y3)(x3,y3) because of the reason above. Specifically, we can easily show that wbc<wabwbc<wab and wac<wabwac<wab.

Now, suppose that for each point (x1,y1)(x1,y1) we want to generate all the edges to points (x2,y2)(x2,y2) where x1x2x1≤x2 which could possibly be part of a MST. Consider the points in order of decreasing x.x. By the above observation, we only need to consider the edges from (x1,y1)(x1,y1) to the last added point for each 0y100≤y≤10, which can be maintained in linear time using an array of size 1111. Thus, we only need to run Kruskal on 11N11N distinct edges.

The overall time complexity of running this algorithm is O((Nmaxyi)(logN+logmaxyi))O((Nmaxyi)(log⁡N+log⁡maxyi)), which comes from sorting the edge weights during Kruskal.

Danny Mittal's code:

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class MooNetwork {
    static int[] union;
 
    static int find(int u) {
        if (union[union[u]] != union[u]) {
            union[u] = find(union[u]);
        }
        return union[u];
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        TreeMap<Integer, Integer>[] rows = new TreeMap[11];
        for (int y = 0; y <= 10; y++) {
            rows[y] = new TreeMap<>();
        }
        int[] xs = new int[n];
        int[] ys = new int[n];
        for (int j = 0; j < n; j++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            xs[j] = Integer.parseInt(tokenizer.nextToken());
            ys[j] = Integer.parseInt(tokenizer.nextToken());
            rows[ys[j]].put(xs[j], j);
        }
        List<Edge> edges = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            for (int y = 0; y <= 10; y++) {
                Map.Entry<Integer, Integer> entry = y == ys[j] ? rows[y].lowerEntry(xs[j]) : rows[y].floorEntry(xs[j]);
                if (entry != null) {
                    long dx = xs[j] - entry.getKey();
                    long dy = ys[j] - y;
                    edges.add(new Edge(j, entry.getValue(), (dx * dx) + (dy * dy)));
                }
            }
        }
        union = new int[n];
        for (int j = 0; j < n; j++) {
            union[j] = j;
        }
        edges.sort(Comparator.comparingLong(edge -> edge.weight));
        long answer = 0;
        for (Edge edge : edges) {
            int u = find(edge.a);
            int v = find(edge.b);
            if (v != u) {
                union[v] = u;
                answer += edge.weight;
            }
        }
        System.out.println(answer);
    }
 
    static class Edge {
        final int a;
        final int b;
        final long weight;
 
        Edge(int a, int b, long weight) {
            this.a = a;
            this.b = b;
            this.weight = weight;
        }
 
        @Override
        public String toString() {
            return "Edge{" +
                    "a=" + a +
                    ", b=" + b +
                    ", weight=" + weight +
                    '}';
        }
    }
}

Fun Fact #1: Note that Squared Euclidean Distance was not very special in our proof. In particular, the same solution can be used for Manhattan Distance or regular Euclidean Distance.

Fun Fact #2: Note that finding an MST in Squared Euclidean Distance is equivalent to finding an MST in Euclidean Distance, although it is not equivalent to finding an MST in Manhattan distance (can you see why?). So, an algorithm that can find a Euclidean MST could be used to solve this problem. General Euclidean MST (without the bound on yiyi) can be done in O(NlogN)O(Nlog⁡N) time.

[/hide]

翰林国际教育资讯二维码