QBGI - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: kingmessi
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

N people stand in queue to enter a bar for a party, each of whom is either a girl or a boy.
They enter one by one, but once the number of boys who enter exceeds twice the number of girls, nobody else is allowed to enter.
Find the number of people who will enter the bar.

EXPLANATION:

This is a simple simulation task.

Let \text{boys} denote the number of boys who have entered so far, and \text{girls} denote the number of girls.
Initially, these are both 0.
Then, for each i from 1 to N:

  • If S_i = B, increase \text{boys} by 1.
    Otherwise, increase \text{girls} by 1.
  • Then, if \text{boys} \gt 2\times\text{girls}, print i and break out of the loop immediately.
  • If you never break out, the answer is N.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    boys, girls = 0, 0
    for i in range(n):
        if s[i] == 'B': boys += 1
        else: girls += 1
        
        if boys > 2*girls:
            print(i+1)
            break
    else:
        print(n)