Overview

This is a problem about simulating annihilation reactions that occur when elements are sequentially placed into a test tube with a stack structure, and specific combinations become adjacent to each other.

Analysis

The key point of this problem is that you only need to compare two things: the “newly inserted element” and the “element currently at the top of the test tube”.

There is an important constraint in the problem statement: “After an annihilation occurs, no further reaction check is performed on the newly exposed end.” Because of this, each insertion results in only one of two outcomes: either “the top element is removed” or “a new element is added.”

If chain reactions were allowed, this would become complex, but thanks to this constraint, the problem can be solved with a simple simulation that only checks the top of the stack (the most recent element) at each step.

Since \(N\) can be as large as \(10^6\), each operation must be performed efficiently. Specifically, the following optimizations are effective: 1. Fast reaction pattern lookup: Store the reacting pairs \((X, Y)\) in a two-dimensional array (table) or hash set so that lookups can be done in \(O(1)\). 2. Efficient data structure: Use a “stack” that supports fast addition and removal from the end. Python lists (append and pop) perform these operations in \(O(1)\).

Algorithm

The simulation is performed with the following steps:

1. Preparation: Record the reaction patterns in a 26×26 two-dimensional array react[26][26]. If react[X][Y] is True, it means that inserting element \(Y\) right after element \(X\) causes a reaction.
2. Simulation:
   • Prepare an empty stack.
   • For each character \(c\) in the string \(S\), perform the following in order:
     • If the stack is not empty, and the combination of “the character at the top of the stack” and “the character \(c\) about to be inserted” is included in the reaction patterns:
       • Remove the top of the stack (pop). Do not add \(c\) to the stack.
     • Otherwise:
       • Add character \(c\) to the top of the stack (append).
3. Output:
   • If the stack is empty, output EMPTY.
   • Otherwise, concatenate and output the characters in the stack.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading the reaction patterns takes \(O(M)\), and processing each character of the string \(S\) takes \(O(N)\). Since stack operations and reaction lookups are \(O(1)\) per character, the entire process runs in linear time.
• Space complexity: \(O(N + \Sigma^2)\)
  • The stack stores at most \(N\) characters, requiring \(O(N)\) space. Additionally, recording the reaction patterns requires space proportional to the square of the number of uppercase letter types \(\Sigma=26\), but this can be treated as a constant.

Implementation Notes

• Fast I/O: Since \(N=10^6\), in Python, using sys.stdin.read().split() to read all input at once instead of input() can reduce execution time.

• Converting characters to numbers: By using ord(char) - ord('A'), you can convert ‘A’-‘Z’ to integers 0-25, making them easy to use as indices for a two-dimensional array.

• Checking for empty state: Accessing stack[-1] when the stack is empty causes an error, so always verify the stack is not empty with something like if stack: before referencing the top element.

  Source Code

import sys

def solve():
    # 標準入力からすべてのトークンを一度に読み込みます。
    # 大規模な入力（N=10^6）に対して効率的に処理を行うためです。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # トークンを順番に取り出すためのイテレータを作成します。
    it = iter(input_data)
    try:
        # 最初のトークンは文字列の長さ N（今回はループで s を直接回すため使いません）
        _ = next(it)
        # 次のトークンは反応パターンの数 M
        m = int(next(it))
        # その次のトークンは投入する元素の列 S
        s = next(it)
    except StopIteration:
        return
    
    # 反応パターンを 26x26 の二次元配列（テーブル）として保持します。
    # 英大文字 'A'-'Z' を 0-25 の整数にマップして管理します。
    react = [[False] * 26 for _ in range(26)]
    for _ in range(m):
        try:
            # 各反応パターン (X, Y) を取得し、テーブルを更新します。
            u_char = next(it)
            v_char = next(it)
            u = ord(u_char) - 65
            v = ord(v_char) - 65
            react[u][v] = True
        except StopIteration:
            break
            
    # 試験管の状態をスタックとして管理します。
    # 処理の高速化のため、文字ではなく 0-25 の整数として保持します。
    stack = []
    
    # 文字列 S の各元素を順番に処理（投入）します。
    for char in s:
        # 新たに投入する元素を整数に変換
        v = ord(char) - 65
        
        # 試験管が空でなく、かつ「試験管の一番上（末尾）」と「投入する元素」が反応する場合
        if stack and react[stack[-1]][v]:
            # 両方の元素が消滅するため、スタックの末尾を削除し、新しい元素も追加しません。
            # 問題文の指示通り、ここで新たに露出した末尾に対しての再反応チェックは行いません。
            stack.pop()
        else:
            # 反応が起きない場合は、新しい元素をスタックの末尾に追加します。
            stack.append(v)
            
    # すべての処理が終わった後のスタックの状態を出力します。
    if not stack:
        # スタックが空の場合は "EMPTY" を出力
        sys.stdout.write("EMPTY\n")
    else:
        # スタック内の整数を文字に戻して連結し、出力します。
        sys.stdout.write("".join(chr(v + 65) for v in stack) + "\n")

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.