USACO December 2021 Bronze Problem 1: Lonely Photo (version 1)

/*  prob1.java
*
*/

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

class prob1 {
    public static void main (String [] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st;
    
        st = new StringTokenizer(in.readLine());         
        int N = Integer.parseInt(st.nextToken());        
        // out.println(N);  // DEBUG
        
        int[] arrH = new int[N];                       // Holstein zero-one array
        int[] arrHsum = new int[N];                    // Holstein subset sum array

        st = new StringTokenizer(in.readLine());         
        char[] arrinput = (st.nextToken()).toCharArray();
         
        long answer = 0;
        int i,j;
        char c;
        int seqlen;
        int hcount;
        
        // initialize the subset sum
        if (arrinput[0] == 'H') {
			arrH[0]=1;
			arrHsum[0]=1;
		}
        
        // loop to fill in the subset sum
        for (i = 1; i < N; i++) {
            if(arrinput[i] == 'H') {
				arrH[i] = 1;
			} 
			arrHsum[i] = arrHsum[i-1] + arrH[i];
        }
        
        // loop to check sequences that start at index 0
        for (j=2;j<N;j++) {
			seqlen = j+1;
			if ((arrHsum[j]==1)||(arrHsum[j]==seqlen-1))  {
			    answer++;	
			}
	}
		
	// nested loop to check all other sequences
	for (i=1;i<N-2;i++) {
		for (j=i+2;j<N;j++) {
			seqlen = j-i+1;
		        // sequence starts at index i (for i>0)
		        // sequence ends at index j
			hcount = arrHsum[j]-arrHsum[i-1];
			if ((hcount==1)||(hcount==seqlen-1)) {
			    answer++;	
			}
		}		
	}
        
        // out.println(Arrays.toString(arrinput));          // DEBUG    
        // out.println(Arrays.toString(arrH));              // DEBUG
        // out.println(Arrays.toString(arrHsum));           // DEBUG
        
        out.println(answer);
        out.close();
    }
}

USACO February 2019 Bronze Problem: Revegetate

/*
ID: karihee1
LANG: JAVA
TASK: revegetate
*/

/*  revegetate.java
*/

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

class revegetate {
    public static void main (String [] args) throws IOException {

        //BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        //PrintWriter out = new PrintWriter(System.out);
        BufferedReader in = new BufferedReader(new FileReader("revegetate.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("revegetate.out")));

        StringTokenizer st;
    
        st = new StringTokenizer(in.readLine());        
        int N = Integer.parseInt(st.nextToken());        // Pastures
        int M = Integer.parseInt(st.nextToken());        // Cows
        
        // System.out.println(N + " " + M);   // DEBUGGING PRINT STATEMENT

        ArrayList<ArrayList<Integer> > pastureList = new ArrayList<ArrayList<Integer>>(N);
        for (int i=0; i<N; i++) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            pastureList.add(temp);
        }

        for (int i=0;i<M;i++) {
            st = new StringTokenizer(in.readLine());
            int P1 = Integer.parseInt(st.nextToken());    // Pasture 1 for this cow 
            int P2 = Integer.parseInt(st.nextToken());    // Pasture 2 for this cow 
            
            // System.out.println(P1 + " " + P2);  // DEBUGGING PRINT STATEMENT

            pastureList.get(P1-1).add(P2-1);
            pastureList.get(P2-1).add(P1-1);
        }

        //for (int i=0;i<N; i++) {
        //    System.out.println(pastureList.get(i).toString()); // DEBUGGING PRINT STATEMENT
        //}

        // Input Data Loaded...Begin Planting Seed

        int[] answer = new int[N];
        answer[0]=1; //initialize with seed type 1 in pasture 0, can't be conflict yet.

        ArrayList<Integer> work = new ArrayList<Integer>();
        for (int i=1;i<N;i++) {
            for (int j=1;j<=4;j++) {
                // attempt to place seed j in pasture i, check for conflict
                boolean conflict = false;
                work = pastureList.get(i);

                for (int p = 0; p < work.size(); p++) {
                    if (j==answer[work.get(p)]) {
                        conflict = true;
                        break;
                    }
                }
                if (conflict) continue;  // conflict found for seed type j, try next seed type
                else {
                    answer[i]=j;         // success!
                    break;
                } 
            }
        }

		for (int i=0; i<N; i++) {
            out.print(answer[i]);
        }
		out.println();
        out.close();
    }
}

USACO "Guess The Animal" Java Solution

/*
* Solution to 2019 USACO January Bronze Problem: Guess the Animal
*/

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

class guess {

    public static void main (String [] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st;

        st = new StringTokenizer(in.readLine());  
        int N = Integer.parseInt(st.nextToken());
        // out.println(N);  // DEBUG PRINT
        
        ArrayList<HashSet<String>> list = new ArrayList<HashSet<String>>();

		for (int i=0; i<N; i++) {

            st = new StringTokenizer(in.readLine());   
			String name = st.nextToken();
            int nqualities = Integer.parseInt(st.nextToken());

            // out.println(name + " " + nqualities); // DEBUG PRINT
            HashSet<String> tempset = new HashSet<String>();

			for (int j=0; j<nqualities; j++) {
			    tempset.add(st.nextToken());	
		    }
            list.add(tempset);
        }

        // out.println(list.toString()); // DEBUG PRINT
        int maxoverlap = 0;

        for (int i=0; i<N; i++) {
            for (int j=i+1; j<N; j++) {
                // make a copy of the HashSet at list.get(i) 
                //     because retainAll is destructive, 
                //         want to keep list intact
                HashSet<String> intersection = new HashSet<String>(list.get(i));
                intersection.retainAll(list.get(j));
                int overlap = intersection.size();
                if (overlap>maxoverlap) {
                    maxoverlap = overlap;
                }
                // out.println(i + " " + j + " " + intersection.toString() + " " + overlap); // DEBUG PRINT
            }
        }
        int answer = maxoverlap+1;
        out.println(answer); 
        // out.println(list.toString()); // DEBUG PRINT
        out.close();
    }
}