ACCESS - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

A binary string S represents N actions on an access card.

  • S_i = 0 denotes a swipe.
  • S_i = 1 denotes a renewal, which resets the number of allowed swipes to X.

The card starts with no swipes available. Find out whether S represents a valid sequence of actions.

EXPLANATION:

It suffices to simply simulate the process.
Let R be a variable denoting the number of remaining swipes. Initially, R = 0.
Then, for each i from 1 to N:

  • If S_i = 1, set R to X.
  • If S_i = 0, subtract 1 from R.

If R becomes negative at any point of time, the answer is No.
Otherwise, the answer is Yes.

TIME COMPLEXITY:

\mathcal{O}(N\cdot X) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    ans = 'Yes'
    rem = 0
    for y in input():
        if y == '0': rem -= 1
        else: rem = x
        if rem < 0: ans = 'No'
    print(ans)