USACO analysis
Mark Chen |
16 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
Problem 2. Hoof, Paper, Scissors
Problem Summary
Hoof Paper Scissors is a game like paper, scissor, stone. In the game, Hoof > Scissors, Scissors > Paper, and Paper > Hoof. The cow Bessie know the sequence of gesture that will be used by Farmer John, but it only can change its gesture for $k$ times, where $k$ is a number that is less than 20.
Given the gesture sequence of farmer John and maximum number of change ($k$) for Bessie, what is the maximum number of games Bessie can win?
Proposed Solution
We can use the dynamic programming to solve this problem. First, we noticed that three variables are needed to represent a state for Bessie.
- The current gesture Bessie is using
- The number of game Bessie has won
- The number of time that Bessie change its gesture
Therefore, we will build up a 3D array $T$ with size $3\times N \times k$, where $N$ is the number of games Bessie and John will have. $T[0][n][k]$ represent the maximum number of game that Bessie can win when it has “Hoof” at $n$th game and has changed its gesture for $k$ times.
Suppose we have a function isWin(gesture, n) that will return whether Bessie will win. If Bessie wins, return 1; otherwise, return 0. Then we can calculate through the whole table using these equations:
If either $n$ or $k$ is out of bound (not in 3D array $T$, return 0.
After calculating through all the table, we should check all the elements in slice $T[][N][]$. (the maximum win number may not require maximum number of change). The final result will be the maximum value of these $3\times k$ values.
Time Complexity Analysis
Since we know that $1\leq N\leq 100,000$ and $1\leq k\leq 20$, the 3D array we will construct has a size of $3\times100,000\times20 = 6\times 10^7$. Since we need to calculate through the whole table, our program may require $1\times 10^8$ computational steps and time complexity of $O(kN)$. Since this time complexity is on the edge of TLE, we should use Java to solve this problem.
