SWISHGAME - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Toofan is playing a game containing N rings. Each ring can be either swished or passed.
The game ends when either all N rounds have been played, and X swishes have been achieved; or it’s impossible for Toofan to obtain X swishes from the following rings.

You’re given a string S of length M, denoting Toofan’s moves till the game ended. Find the value of N.

EXPLANATION:

Let ct denote the number of swishes Toofan obtained over the course of the game.
Then,

  • If ct \geq X, the game must have ended with Toofan clearing all N rings.
    • So, in this case the answer is just M - we know the full game.
  • Otherwise, ct \lt X and the game must have ended when it became clear that it’s impossible for Toofan to win any more, no matter what he does.
    • This means there are not enough rings remaining for Toofan to reach X swishes.
      He has ct swishes right now, so if there are at least another X - ct rings, he can possibly swish them all and reach X.
      So, there must be strictly less than X - ct more rounds remaining - meaning the maximum we can do is X - ct - 1.
    • Adding this to the existing number of rings M gives us the answer, that being M + (X - ct - 1).

TIME COMPLEXITY:

\mathcal{O}(M) per testcase.

CODE:

Editorialist's code (PyPy3)
for _ in range(int(input())):
    m, k = map(int, input().split())
    s = input()
    
    swish = s.count('S')
    if swish >= k: print(m)
    else: print(m + (k - 1 - swish))