Problem Summary (USACO Gold 3 February 2016)

Given a rectangular coordinate plane of dimensions (A,B), there are N vertical fences, and M horizontal fences. Clearly, the intersection of these fences within the larger rectangle creates (n+1)(m+1) regions.

Given A,B,N,M, the x-coordinates of the N vertical fences and the y coordinates of the M horizontal fences, find the minimum amount of fence to remove to create a minimum spanning tree (connect all regions). In order to remove a fence and thus union two adjacent regions, the entire length of fence between them must be removed.

Solution

This is clearly a disjoint-set union problem (union-find/Kruskals), but the tricky part is building the edge-list and tree to union. Each edge is weighted by the length of fence between the two nodes that it connects.

Here is a quick outline of the code below:

1) Read in x,y coords of vertical, horizontal fences (also add 0,0,A,B as “fences”)

2) For each intersection of the fences (some special cases at ends), add the left-facing and up-facing edges to edge list, and additionally add the region between the two edges as a node to the union-find tree.

3) Run Kruskals, keeping track of distance.

This is an O(ElogV) algorithm, which should be more than fast enough since N and M are less than 2000. Note that the given solution (linked above) is fast enough, where this takes to long (failure) for the last 4/10 test cases.

Where is the performance bottleneck? How can this be improved?

#include <iostream> #include <fstream> #include <vector> #include <set> #include <algorithm>  #define ll long long  using namespace std;  const string PROJ_NAME = "fencedin";  struct edge {     ll dist;     int start;     int finish;     bool operator< (const edge &rhs) const { return dist < rhs.dist || (!(rhs.dist < dist) && start < rhs.start) || (!(rhs.start < start) && finish < rhs.finish); } };  struct uf_node {     int parent;     int level; };  ll A, B; int N, M; set<edge> edge_list; vector<uf_node> tree;  void make_edge_list(ifstream &fin){     fin >> A >> B >> N >> M;      vector<int> vert(N+2);     vert[0] = 0;     for(int i = 1; i<=N; i++) fin >> vert[i];     vert[N+1] = A;     N++;      vector<int> hori(M+2);     hori[0] = 0;     for(int i = 1; i<=M; i++) fin >> hori[i];     hori[M+1] = B;     M++;      sort(vert.begin(), vert.end());     sort(hori.begin(), hori.end());      tree.resize(N*M);     for(int i = 1; i<=N; i++){         for(int j = 1; j<=M; j++){             int curr = (i-1)*M+(j-1);              //Add node to DSU tree             uf_node n = {.parent = curr, .level = 0};             tree[curr] = n;              //Add leftward edge if not at bottom             if(i != N){                 edge left = {.dist = hori[j]-hori[j-1], .start=curr, .finish=curr+M};                 edge_list.insert(left);             }              //Add upward edge if not at right             if(j != M){                 edge up = {.dist = vert[i]-vert[i-1], .start=curr, .finish=curr+1};                 edge_list.insert(up);             }         }     } }  int find_par(int i) {     if(i != tree[i].parent) {         tree[i].parent = find_par(tree[i].parent);     }     return tree[i].parent; }  void do_union(int i, int j) {     int r = find_par(i);     int s = find_par(j);     if(r == s) return;     else if (tree[r].level > tree[s].level) {         tree[r].parent = s;     } else if (tree[s].level > tree[r].level) {         tree[s].parent = r;     } else {         tree[r].parent = s;         tree[r].level += 1;     } }  int main() {     ifstream fin (PROJ_NAME + ".in");     ofstream fout (PROJ_NAME + ".out");      make_edge_list(fin);      int total_dist = 0;     for(edge e: edge_list){         if(find_par(e.start) != find_par(e.finish)){             do_union(e.start, e.finish);             total_dist += e.dist;         }     }      fout << total_dist << endl;     return 0; }