I recently took the USACO 2021 Silver contest and TLEd on 3 testcases in problem 1 - http://www.usaco.org/index.php?page=viewproblem2&cpid=1110. After reading the solution, I noticed that my solution was very similar to the alternative solution by Danny Mittal. I feel there is only one main difference which is that I used HashMap and HashSet as opposed to arrays. Is this causing the problem? Or is there another reason. Any help would be appreciated, thanks!
Accepted solution -
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class LonelyPastureSilver {
static final boolean[][] cows = new boolean[3000][3000];
static final int[][] adj = new int[3000][3000];
static int answer = 0;
static void add(int x, int y) {
if (!cows[x][y]) {
cows[x][y] = true;
answer++;
if (cows[x][y] && adj[x][y] == 3) {
for (int[] another : new int[][]{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}}) {
int w = another[0];
int z = another[1];
add(w, z);
}
}
for (int[] other : new int[][]{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}}) {
int u = other[0];
int v = other[1];
adj[u][v]++;
if (cows[u][v] && adj[u][v] == 3) {
for (int[] another : new int[][]{{u - 1, v}, {u + 1, v}, {u, v - 1}, {u, v + 1}}) {
int w = another[0];
int z = another[1];
add(w, z);
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringBuilder out = new StringBuilder();
int n = Integer.parseInt(in.readLine());
for (int j = 0; j < n; j++) {
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int x = Integer.parseInt(tokenizer.nextToken()) + 1000;
int y = Integer.parseInt(tokenizer.nextToken()) + 1000;
answer--;
add(x, y);
out.append(answer).append('\n');
}
System.out.print(out);
}
}
My solution is here -
import java.util.*;
import java.io.*;
public class problem1 {
public static void main(String[] args) throws IOException {
BufferedReader scan=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);
dirX=new int[]{1,-1,0,0};
dirY=new int[]{0,0,1,-1};
cow=new HashSet<>();
neigh=new HashMap<>();
//loop through each placement
n=Integer.parseInt(scan.readLine());
for(int i=0;i<n;i++) {
StringTokenizer st=new StringTokenizer(scan.readLine());
int x=Integer.parseInt(st.nextToken()),y=Integer.parseInt(st.nextToken());
String state=x+" "+y;
//already added a cow here,doesnt affect anything except for ans, no need to add more neigh
if(cow.contains(state)) ans--;
//add start cow
else addNewCow(x,y);
out.println(ans);
}
out.close();
}
//curX curY is center of cross
//adding a new cow to un comfort the cow
static void addNewCow(int curX,int curY) {
String state=curX+" "+curY;
cow.add(state);
boolean empty=false;
if(neigh.containsKey(state)&&neigh.get(state)==3) empty=true;
for(int i=0;i<4;i++) {
int nextX=curX+dirX[i],nextY=curY+dirY[i];
String nextState=nextX+" "+nextY;
if(neigh.containsKey(nextState)) {
neigh.put(nextState,neigh.get(nextState)+1);
if(cow.contains(nextState)&&neigh.get(nextState)==3) {
for(int j=0;j<4;j++) {
int nextXt=nextX+dirX[j],nextYt=nextY+dirY[j];
String nextStatet=nextXt+" "+nextYt;
if(!cow.contains(nextStatet)) {
addNewCow(nextXt,nextYt);
ans++;
break;
}
}
}
} else neigh.put(nextState,1);
if(empty&&!cow.contains(nextState)) {
addNewCow(nextX,nextY);
ans++;
}
}
}
static int[] dirX,dirY;
static int n,ans=0;
static HashMap<String,Integer> neigh;
static HashSet<String> cow;
}