TriumphantEggplant's blog

By TriumphantEggplant, history, 6 weeks ago, In English

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.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 code -

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;
}
 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Teach me how to get gud senpai.

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.