Currently working on the gold Feb 2019 problem Fenced In.
I have been able to get 6/10 test cases thus far, and I am timing out on the rest 4.
My algorithm basically resonates with the official solutions’, where the regions are nodes and fences are edges, and runs MST on them.
I’ve tried looking at previous posts on this problem, and thus tried sorting the edges grouped by weight(where I previously sorted by individual edges). However, I seem to be still timing out.
Here’s my code:
import java.io.*;
import java.util.*;
public class fencedin2 {
public static int MAX = 1;
public static int[][] S;
public static Pair[][] P;
public static Map<Integer, List<Edge>> E = new TreeMap<>();
public static void main(String args[]) throws IOException {
setupFile("fencedin");
//setupSystem();
int A = nextInt(), B = nextInt(), n = nextInt(), m = nextInt();
int[] a = new int[n + 2], b = new int[m + 2];
a[n + 1] = A;
for(int i = 1; i <= n; i++) a[i] = nextInt();
Arrays.sort(a);
b[m + 1] = B;
for(int i = 1; i <= m; i++) b[i] = nextInt();
Arrays.sort(b);
S = new int[n + 1][m + 1];
P = new Pair[n + 1][m + 1];
List<Integer> keys = new ArrayList<>();
for(int x = 0; x <= n; x++){
for(int y = 0; y <= m; y++){
int h = a[x + 1] - a[x]; // horizontal of region
int v = b[y + 1] - b[y]; // vertical
if(x != n){
if(E.get(v) == null){
E.put(v, new ArrayList<>());
keys.add(v);
}
E.get(v).add(new Edge(new Pair(x, y), new Pair(x + 1, y), v));
}
if(y != m){
if(E.get(h) == null){
E.put(h, new ArrayList<>());
keys.add(h);
}
E.get(h).add(new Edge(new Pair(x, y), new Pair(x, y + 1), h));
}
S[x][y] = 1;
P[x][y] = new Pair(x, y);
}
}
// kruskals
long ANS = 0;
Collections.sort(keys);
m : for(Integer k : keys){
for(Edge e : E.get(k)){
if(union(e)){
ANS += e.w;
}
if(MAX == (n + 1)*(m + 1)) break m;
}
}
out.println(ANS);
out.close();
}
public static boolean union (Edge e){
Pair A = find(e.a);
Pair B = find(e.b);
if(equal(A, B)) return false;
MAX = Math.max(MAX, S[A.x][A.y] + S[B.x][B.y]);
if(S[A.x][A.y] > S[B.x][B.y]){
S[A.x][A.y] += S[B.x][B.y];
P[B.x][B.y].x = P[A.x][A.y].x = P[e.a.x][e.a.y].x = P[e.b.x][e.b.y].x = P[A.x][A.y].x;
P[B.x][B.y].y = P[A.x][A.y].y = P[e.a.x][e.a.y].y = P[e.b.x][e.b.y].y = P[A.x][A.y].y;
}else {
S[B.x][B.y] += S[A.x][A.y];
P[B.x][B.y].x = P[A.x][A.y].x = P[e.a.x][e.a.y].x = P[e.b.x][e.b.y].x = P[B.x][B.y].x;
P[B.x][B.y].y = P[A.x][A.y].y = P[e.a.x][e.a.y].y = P[e.b.x][e.b.y].y = P[B.x][B.y].y;
}
return true;
}
public static Pair find(Pair p){
if(equal(p, P[p.x][p.y])) return new Pair(p.x, p.y);
Pair pp = find(P[p.x][p.y]);
P[p.x][p.y].x = pp.x;
P[p.x][p.y].y = pp.y;
return new Pair(pp.x, pp.y);
}
public static boolean equal(Pair p1, Pair p2){
return (p1.x == p2.x) && (p1.y == p2.y);
}
public static class Edge {
Pair a, b;
int w;
Edge(Pair a, Pair b, int w){
this.a = a;
this.b = b;
this.w = w;
}
}
public static class Pair{
int x, y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
}
//
public static BufferedReader br;
public static StringTokenizer in;
public static PrintWriter out;
public static void setupSystem() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
in = new StringTokenizer(br.readLine());
out = new PrintWriter(System.out);
}
public static void setupFile(String F) throws IOException{
br = new BufferedReader(new FileReader(F + ".in"));
in = new StringTokenizer(br.readLine());
out = new PrintWriter(F + ".out");
}
public static int nextInt() throws IOException{
if(!in.hasMoreTokens()) in = new StringTokenizer(br.readLine());
return Integer.parseInt(in.nextToken());
}
}
I can’t seem to get this to run under time, and am not sure what I should do to resolve this.
Any help would be greatly appreciated
