USACO Silver 2017 January - Hoof, Paper, Scissors
13 March 2025
[ algorithms , usaco , silver ]

Give this problem a try USACO Silver 2017 January - Hoof, Paper, Scissors.


Approach


Example Code

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

public class Solution {
	public static int gesture(char c) {
		if (c == 'H') return 0;
		if (c == 'P') return 1;
		if (c == 'S') return 2;
		return -1;
	}

	public static int maxArray(int[] p) {
		return Math.max(p[0], Math.max(p[1], p[2]));
	}

    public static void main(String[] args) throws Exception {
        FastScanner io = new FastScanner("hps");
		// FastScanner io = new FastScanner();
		int N = io.nextInt();

		int[] gs = new int[N];
		for (int i = 0; i < N; i++) {
			char c = io.next().toCharArray()[0];
			int g = gesture(c);
			gs[i] = g;
		}

		// H = 0, P = 1, S = 2
		int[][] pref = new int[N][3];

		pref[0] = new int[]{0,0,0};
		pref[0][gs[0]]++;

		for (int i = 1; i < N; i++) {
			int[] p = pref[i-1];
			pref[i] = new int[]{p[0], p[1], p[2]};
			pref[i][gs[i]]++;
		}

		int[][] suff = new int[N][3];
		suff[N-1] = new int[]{0,0,0};
		suff[N-1][gs[N-1]]++;

		for (int i = N-2; i >= 0; i--) {
			int[] s = suff[i+1];
			suff[i] = new int[]{s[0], s[1], s[2]};
			suff[i][gs[i]]++;
		}
		
		int answer = 0;

		for (int i = 0; i < N-1; i++) { // switch at i
			int maxPref = maxArray(pref[i]);
			int maxSuff = maxArray(suff[i+1]);
			answer = Math.max(maxPref + maxSuff, answer);
		}
		answer = Math.max(maxArray(pref[N-1]), answer); // not switch

		io.println(answer);

		io.close();
    }

    /**
        RESERVED NUMBERS
    */
    public static int MOD = 1_000_000_007; // prime number

    /**
        DATA STRUCTURES
    */
    static class MultiSet {
        static TreeMap<Integer, Integer> multiset = new TreeMap<>();
        static void add(int x) {
            multiset.putIfAbsent(x, 0);
            multiset.put(x, multiset.get(x)+1);
        }
        static void remove(int x) {
            multiset.putIfAbsent(x, 0);
            multiset.put(x, multiset.get(x)-1);
            if (multiset.get(x) <= 0) multiset.remove(x);
        }
    }

    /**
        IO
    */
    static class FastScanner extends PrintWriter {
        private BufferedReader br;
        private StringTokenizer st;
		
		// standard input
        public FastScanner() { this(System.in, System.out); }
		public FastScanner(InputStream i, OutputStream o) {
            super(o);
			st = new StringTokenizer("");
            br = new BufferedReader(new InputStreamReader(i));
        }
		// USACO-style file input
        public FastScanner(String problemName) throws IOException {
            super(problemName + ".out");
			st = new StringTokenizer("");
            br = new BufferedReader(new FileReader(problemName + ".in"));
        }

        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }  
        public double nextDouble() { return Double.parseDouble(next()); }   
        public long nextLong() { return Long.parseLong(next()); }   
    }
}

Complexity Analysis

  • Time Complexity: O(N)
  • Space Complexity: O(N)

Sign-off

Congratulations on making it this far! Best of luck in your future competitions!