# Fenced In Gold Feb 16

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<>());
}
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<>());
}
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 StringTokenizer in;
public static PrintWriter out;
public static void setupSystem() throws IOException {
out = new PrintWriter(System.out);
}
public static void setupFile(String F) throws IOException{
out = new PrintWriter(F + ".out");
}
public static int nextInt() throws IOException{
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

Maybe try turning your 2D arrays into 1D arrays?

1 Like

Hm, seems to still be timing out with 2D → 1D (and going even slower, for some reason?).

Here’s my updated code:

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

public class fencedin2 {
public static int MAX = 1;
public static int[] S;
public static int[] P;
public static Map<Integer, List<Edge>> E = new TreeMap<>();
public static int n, m;
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 int[(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<>());
}
E.get(v).add(new Edge(x * (m + 1) + y, (x + 1) * (m + 1) + y, v));
}
if(y != m){
if(E.get(h) == null){
E.put(h, new ArrayList<>());
}
E.get(h).add(new Edge(x * (m + 1) + y, x * (m + 1) + (y + 1), h));
}

S[x*(m + 1) + y] = 1;
P[x*(m + 1) + y] = x*(m + 1) + 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){
int A = find(e.a);
int B = find(e.b);
if(A == B) return false;

MAX = Math.max(MAX, S[A] + S[B]);
if(S[A] > S[B]){
S[A] += S[B];
P[B] = P[A] = P[e.a] = P[e.b] = P[A];
}else {
S[B] += S[A];
P[B] = P[A] = P[e.a] = P[e.b] = P[B];
}

return true;
}

public static int find(int p){
if(P[p] == p) return p;
return P[p] = find(P[p]);
}

public static boolean equal(Pair p1, Pair p2){
return (p1.x == p2.x) && (p1.y == p2.y);
}

public static class Edge {
int a, b;
int w;
Edge(int a, int 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 StringTokenizer in;
public static PrintWriter out;
public static void setupSystem() throws IOException {
out = new PrintWriter(System.out);
}
public static void setupFile(String F) throws IOException{
out = new PrintWriter(F + ".out");
}
public static int nextInt() throws IOException{
return Integer.parseInt(in.nextToken());
}
}
``````

Actually, it might be because of your edge map. Maps in Java (and most other languages) have a large constant factor, so maybe just put them in an `ArrayList` or `Edge[]` and sort accordingly?

1 Like

Now it’s timing out on the last 2 test cases:

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

public class fencedin {
public static int MAX = 1;
public static int[] S;
public static int[] P;
public static List<ALStack> E = new ArrayList<>();
public static int n, m;
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 int[(n + 1)*(m + 1)];
HashMap<Integer, Integer> keys2 = new HashMap<>();
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(keys2.get(v) == null){
keys2.put(v, E.size() - 1);
}
E.get(keys2.get(v)).E.add(new Edge(x * (m + 1) + y, (x + 1) * (m + 1) + y, v));
}
if(y != m){
if(keys2.get(h) == null){
keys2.put(h, E.size() - 1);
}
E.get(keys2.get(h)).E.add(new Edge(x * (m + 1) + y, x * (m + 1) + (y + 1), h));
}

S[x*(m + 1) + y] = 1;
P[x*(m + 1) + y] = x*(m + 1) + y;
}
}

// kruskals
long ANS = 0;
Collections.sort(E, Comparator.comparingInt(o -> o.w));
m : for(ALStack als : E){
for(Edge e : als.E){
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){
int A = find(e.a);
int B = find(e.b);
if(A == B) return false;

MAX = Math.max(MAX, S[A] + S[B]);
if(S[A] > S[B]){
S[A] += S[B];
P[B] = P[A] = P[e.a] = P[e.b] = P[A];
}else {
S[B] += S[A];
P[B] = P[A] = P[e.a] = P[e.b] = P[B];
}

return true;
}

public static int find(int p){
if(P[p] == p) return p;
return P[p] = find(P[p]);
}

public static class ALStack{
List<Edge> E;
int w;
ALStack(int w){
this.w = w;
E = new ArrayList<>();
}
}

public static class Edge {
int a, b;
int w;
Edge(int a, int 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 StringTokenizer in;
public static PrintWriter out;
public static void setupSystem() throws IOException {
out = new PrintWriter(System.out);
}
public static void setupFile(String F) throws IOException{
out = new PrintWriter(F + ".out");
}
public static int nextInt() throws IOException{
I’m not really sure what `keys2` does, but could that be turned into an array?
Ah, `keys2` basically just stores the index(value) in the unsorted `E` array that edges of weight {key} are stored in.