USACO Gold 2017 January - Hoof, Paper, Scissors

Official Analysis

Video Solution

Note: The video solution might not be the same as other solutions. Code in C++.

Solution

The main observation for this problem is that we only need to keep track of the number of games played $i$, the number of times switched so far $j$, and the current gesture $k$ in order to determine the largest number of previous games won for any game $i$.

For every move, either Bessie can either switch or stay on her current gesture. If she changes her gesture, then the next game $i+1$ will have used $j+1$ gestures, which corresponds to the $\texttt{dp}$ state $\texttt{dp}[i+1][j+1][k]$. We can simulate this for all 3 gestures. Then, we just increment $\texttt{dp}[i][j][k]$ if Bessie wins at game $i$ with gesture $k$.

Note that you can just compare the current gesture to H, P, S because there is always exactly one way to win.

Time Complexity: $\mathcal{O}(NK)$

Copy
 Code Snippet: C++ Short Template (Click to expand)

const int MX = 1e5 + 5;

int dp[MX][25][3];  // dp[i][j][k] is the largest number of games she wins at
                    // games i with switches j with current item k
int moves[MX];      // 0 == H 1 == P 2 == S

int main() {
	setIO("hps");

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

public class HoofPaperScissors {
	static int[] moves;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("hps.in"));
		StringTokenizer inputLine = new StringTokenizer(br.readLine());
		int numGames = Integer.parseInt(inputLine.nextToken());

Copy
with open("hps.in") as read:
	n, k = map(int, read.readline().strip().split())
	moves = [0] * n
	for i in range(n):
		a = read.readline().strip()
		if a == "H":
			moves[i] = 0
		elif a == "P":
			moves[i] = 1
		else: