### TriumphantEggplant's blog

By TriumphantEggplant, history, 6 weeks ago,

Same blog post here — https://forum.usaco.guide/t/help-with-usaco-2021-february-silver-problem-1/924

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.util.StringTokenizer;

public class LonelyPastureSilver {
static final boolean[][] cows = new boolean[3000][3000];
static final int[][] adj = new int[3000][3000];

static void add(int x, int y) {
if (!cows[x][y]) {
cows[x][y] = true;
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];
}
}
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];
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];
}
}
}
}
}

public static void main(String[] args) throws IOException {
StringBuilder out = new StringBuilder();
for (int j = 0; j < n; j++) {
int x = Integer.parseInt(tokenizer.nextToken()) + 1000;
int y = Integer.parseInt(tokenizer.nextToken()) + 1000;
}
System.out.print(out);
}
}


My code -

import java.util.*;
import java.io.*;
public class problem1 {
public static void main(String[] args) throws IOException {
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
for(int i=0;i<n;i++) {
int x=Integer.parseInt(st.nextToken()),y=Integer.parseInt(st.nextToken());
String state=x+" "+y;

if(cow.contains(state)) ans--;

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;
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)) {
ans++;
break;
}
}
}
} else neigh.put(nextState,1);
if(empty&&!cow.contains(nextState)) {
ans++;
}
}
}

static int[] dirX,dirY;
static int n,ans=0;
static HashMap<String,Integer> neigh;
static HashSet<String> cow;
}


• +5

 » 6 weeks ago, # |   0 Teach me how to get gud senpai.
 » 6 weeks ago, # |   +6 I haven't read your solution code in depth, so I don't know for sure that this is the only problem, but one issue with your code isn't only that you're using HashMaps and HashSets instead of just arrays, but that you're using Strings as the keys -- I imagine that this adds large constant factor as opposed to using Integers or a custom Pair of Integers class as keys.
•  » » 6 weeks ago, # ^ |   0 Thanks. It runs in time after I used an array as opposed to the hashmap. I didn't realize that it made such a huge difference.
•  » » » 6 weeks ago, # ^ |   +1 If you want to efficiently encode two integers as one key, you may need to create a pair class. Another common hack for efficiency in Java is to combine two integers into a 64-bit long.