Overview

\(N\) students each support either Takahashi or Aoki, and over \(M\) speeches, the support of a specified student is flipped each time. The task is to find the point at which the number of supporters of one of the candidates reaches \(0\).

Observations

The key insight in this problem is that we only need to track the change in the number of supporters after each speech.

While we do need to maintain the “detailed state” of which candidate each student currently supports, determining whether the election is decided can be judged solely by whether the number of Takahashi’s supporters (\(T\) count) or Aoki’s supporters (\(A\) count) becomes \(0\).

• Since speech \(R_i\) flips the support of student \(R_i\), if that student currently supports T, they switch to A, decreasing the \(T\) count by \(1\) and increasing the \(A\) count by \(1\). The reverse works similarly.
• After each speech, we simply check whether the \(T\) count or the \(A\) count is \(0\).

Naively scanning the entire string each time to recount T and A would result in \(O(NM)\), but by using incremental counter updates, each speech can be processed in \(O(1)\).

Algorithm

1. Initialization: Store each student’s support state from string \(S\) into an array, and count the number of Ts as t_count and As as a_count.
2. Processing speeches (\(i = 1, 2, \ldots, M\)):
   • Check the current support of student \(R_i\).
   • If changing T → A: decrease t_count by \(1\) and increase a_count by \(1\).
   • If changing A → T: decrease a_count by \(1\) and increase t_count by \(1\).
   • Also flip the support state in the array (for future lookups).
   • If t_count == 0 or a_count == 0, output \(i\) and terminate.
3. If the condition is never met after all \(M\) speeches, output \(-1\).

Concrete Example

\(N=3\), \(S =\) TAT (\(T\): 2 people, \(A\): 1 person), and speeches target student \(1\), then student \(3\):

After the 2nd speech, t_count == 0, so the answer is 2.

Complexity

• Time complexity: \(O(N + M)\)
  • Scanning \(S\) during initialization takes \(O(N)\), and each speech is processed in \(O(1)\), so the total is \(O(M)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) for the array holding each student’s current support state.

Implementation Tips

• Incremental updates: Instead of recounting the entire array each time, update only the counters by the change amount, achieving \(O(1)\) per operation.

• Fast input: In Python, reading all input at once with sys.stdin.buffer.read() allows efficient processing of large inputs.

• 1-indexed → 0-indexed: Student numbers in the problem are \(1\)-based, but arrays are \(0\)-based, so access using R_i - 1.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = input_data[idx].decode(); idx += 1
    
    support = list(S)
    t_count = S.count('T')
    a_count = N - t_count
    
    for i in range(M):
        r = int(input_data[idx]) - 1; idx += 1
        if support[r] == 'T':
            support[r] = 'A'
            t_count -= 1
            a_count += 1
        else:
            support[r] = 'T'
            t_count += 1
            a_count -= 1
        
        if t_count == 0 or a_count == 0:
            print(i + 1)
            return
    
    print(-1)

main()

This editorial was generated by claude4.6opus-thinking.