Overview

This is a problem where, as students’ support states change, the election is decided the moment the number of supporters for one of the candidates reaches 0. After each speech, we check the number of supporters and output the speech number at which the election was decided.

Analysis

The core of the problem is efficiently managing the number of supporters after each speech. A naive approach of examining every student’s support state each time to calculate supporter counts would take \(O(N)\) time per speech, resulting in \(O(N \times M)\) total time. Under the constraints (\(N, M \leq 2 \times 10^5\)), this would require up to \(4 \times 10^{10}\) operations, which exceeds the time limit.

Instead, we can manage the supporter counts using variables. We count the supporters in the initial state, and each time a student’s support state changes due to a speech, we update the corresponding supporter count. This way, each speech is processed in \(O(1)\) time, and the overall time complexity is an efficient \(O(N + M)\).

Algorithm

1. From the initial string \(S\), count the number of Takahashi’s supporters count_t and Aoki’s supporters count_a.
2. For each speech:
   • Check the current support state of the target student.
   • Update count_t and count_a according to the support state (if it changes from T to A, decrease count_t by 1 and increase count_a by 1, and vice versa).
   • Flip the support state (in preparation for the next speech).
   • If the updated count_t or count_a becomes 0, output the current speech number and terminate.
3. If the election is not decided after all speeches, output -1.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) to count the initial supporter numbers
  • \(O(M)\) to process each speech
• Space complexity: \(O(N)\)
  • For storing the string \(S\) as a list

Implementation Notes

• Student numbers are given as 1-indexed, so convert to 0-indexed (idx = r - 1)

• Perform the support state change and supporter count update simultaneously

• After each speech, immediately check the supporter counts, and if one reaches 0, output the result and terminate the program right away

• Check for the case where input data is empty at the beginning (this may not occur under the problem’s constraints, but it’s a precaution)

  Source Code

import sys

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        print(-1)
        return
        
    n, m = map(int, data[0].split())
    s = list(data[1].strip())
    r_list = list(map(int, data[2:2+m]))
    
    count_t = s.count('T')
    count_a = n - count_t
    
    for i, r in enumerate(r_list):
        idx = r - 1
        if s[idx] == 'T':
            count_t -= 1
            count_a += 1
            s[idx] = 'A'
        else:
            count_t += 1
            count_a -= 1
            s[idx] = 'T'
            
        if count_t == 0:
            print(i+1)
            return
        if count_a == 0:
            print(i+1)
            return
            
    print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.