PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sezalmittal987
Tester: kaori1
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You know the next N moves your opponent will make, in a rock-paper-scissors game.
What’s the maximum number of wins you can obtain, if you cannot make the same move twice in a row?
EXPLANATION:
Consider a continuous block of your opponent’s moves, all of the same type - say, rock.
Say this block has length K.
You can’t play paper twice in a row, so within this block you certainly can’t win twice in a row.
That means that best you can do is to win the first, third, fifth, … games - all the odd-numbered ones.
More specifically, you can win \left\lceil \frac{K}{2} \right\rceil games out of these K, and no more.
It’s not hard to see that this applies to every block, so a clear upper bound on the answer is the sum of \left\lceil \frac{K}{2} \right\rceil across all blocks in the given string of moves.
For example, if S = \texttt{RRPRRRSSP}, the blocks have lengths [2, 1, 3, 2, 1], and adding up the ceilings of their half-lengths gives us 1 + 1 + 2 + 1 + 1 = 6 - meaning no matter what, we cannot get more than 6 wins here.
This bound is also achievable, so it is the answer!
Proof
As we noted above, within a block winning \left\lceil \frac{K}{2} \right\rceil is easy: just win alternate games starting from the first, and lose/draw the others.
The only issue is borders - that is, when moving from one type of block to another, we need to ensure that the same move isn’t played twice.
However, since we have three moves with us, and a loss is equivalent to a draw (we only care about winning), we can in fact always ensure this:
- If you win the last game of a block, the winning the first game of the next block is definitely going to use a different move.
- If you don’t win the last game of a block, there are two choices since you can either draw or lose.
One of them will be not the winning move of the next block, so choose this non-winning move, and it’s ensured that there will be no issues.
Implementation is quite simple: find all maximal contiguous blocks of equal characters in S, and add up (the ceiling of) their half-lengths.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
ans = i = 0
while i < n:
j = i
while j < n and s[j] == s[i]: j += 1
x = j-i
ans += (x+1)//2
i = j
print(ans)