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 A[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"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("hps.out")));