PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There’s a conveyor belt of length N.
Each section has either L or R written on it, denoting left and right, respectively.
The direction of the i-th section is denoted S_i.
An object placed on a section will move in the direction denoted by that section.
An item is placed at position P.
You want it to reach one end of the belt, i.e. either section 0 or N+1.
Find the minimum number of changes that need to be made in the conveyor directions to achieve this.
EXPLANATION:
Suppose the item is placed at position P, and we want to make it reach the left end, i.e. position 0.
The only way this is possible, is if the item moves left at each position P, P-1, \ldots, 3, 2, 1.
Thus, we need S_i = L to hold for each i = 1, 2, \ldots, P.
The number of changes needed to achieve this is hence the count of R among the first P positions; since these are exactly the positions that need to be changed.
Similarly, if we wanted to make the item reach the right end, N+1, instead - the only way is for positions P, P+1, \ldots, N to all contain R.
So in this case, the minimum number of changes is the count of L among the positions from P to N.
For the final answer, we’re fine with sending the item to either end - so just take the minimum of both cases.
That is, the answer equals the minimum of:
- The number of
R’s present among positions 1 to P, and - The number of
L’s present among positions P to N.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, p = map(int, input().split())
s = input()
left = s[:p].count('R')
right = s[p-1:].count('L')
print(min(left, right))