STOPCOUNT - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

An election is held. N people vote, person i votes for Chef if and only if S_i = 1.
At how many points can Chef stop the count and be declared the winner, with no tie?

EXPLANATION:

For Chef to win after i votes have been counted, strictly more people must have voted for him among people 1, 2, \ldots, i.
So, for each i = 1, 2, 3, \ldots, N,

  • Let x denote the number of people who voted for Chef among these people.
    That is, x equals the count of indices j satisfying 1 \le j \le i and S_j = 1.
  • Let y denote the number of people who didn’t vote for Chef among these people.
    That is, y equals the count of indices j satisfying 1 \le j \le i and S_j = 0.
  • Then, this is a valid stopping point if and only if x \gt y.

This condition can easily be checked for each i in linear time, for \mathcal{O}(N^2) overall.
This is fast enough for the limits in this problem.

It’s possible to optimize this to \mathcal{O}(N) as well; simply store running counts for x and y instead of recomputing them every time.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    chef, antichef = 0, 0
    ans = 0
    for i in range(n):
        if s[i] == '1': chef += 1
        else: antichef += 1
        
        if chef > antichef: ans += 1
    print(ans)