Official Analysis (Java)

In order to maximize the amount of wins, we want to find a changing point such that the wins before and wins after are maximized. Because Bessie can only play one gesture for one sequence, it is best for her to play against whichever gesture Farmer John plays the most in that sequence. Thus, the maximum number of wins in one sequence is the amount of hooves, papers, or scissors, whichever one is greatest.

We can precompute the number of hooves, papers, and scissors at a certain point using prefix sums. Then, we maximize the wins before and wins after for every possible changing point and find the greatest number of wins.

C++

Implementation

Time Complexity: O(N)\mathcal{O}(N)

#include <bits/stdc++.h>
using namespace std;


int main() {
	freopen("hps.in", "r", stdin);


	int n;
	cin >> n;
	vector<int> hooves(n + 1), paper(n + 1), scissors(n + 1);

Java

import java.io.*;


public class HPS {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new FileReader("hps.in"));


		int n = Integer.parseInt(br.readLine());
		int[] hooves = new int[n + 1];
		int[] paper = new int[n + 1];
		int[] scissors = new int[n + 1];

Python

with open("hps.in") as r:
	n = int(r.readline().strip())
	hooves = [0 for _ in range(n + 1)]
	paper = [0 for _ in range(n + 1)]
	scissors = [0 for _ in range(n + 1)]


	for i in range(1, n + 1):
		hooves[i] += hooves[i - 1]
		paper[i] += paper[i - 1]
		scissors[i] += scissors[i - 1]

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum