Overview

This problem asks whether we can repeatedly perform an operation that removes adjacent pairs of cards with the “same color and same integer” from \(N\) cards so that the characters on the remaining cards match \(T\).

Through proper analysis, the conditions regarding the written integers (\(M\) and \(Q\)) can be ignored, and the problem reduces to determining “erasability by stack operations on card colors \(P\)” and “matching with the string \(T\)” using dynamic programming (DP).

---

Analysis

1. Integer \(M\) and Target Integer Sequence \(Q\) Can Be Ignored

At first glance, it seems necessary to consider the integers written on the cards and matching with \(Q\). However, we can think as follows:

• For the cards we want to keep, we can simply write the target integer sequence \(Q_1, Q_2, \ldots, Q_L\) on them in advance.
• For the pairs of cards we want to erase, we can appropriately assign integers so that they do not affect the remaining cards (for example, assigning the same integer to each pair erased from the inside out).

Therefore, we only need to consider “whether cards can be erased according to the color erasure rules”, and the constraints on the written integer \(M\) and the sequence \(Q\) can always be satisfied.

2. Color Erasability and Stacks

The operation of erasing two cards can be regarded as “matching colored parentheses”. Consider an operation where we push the card colors into a stack from left to right, and “pop the top of the stack whenever a card of the same color as the stack’s top arrives”.

Under this model, a necessary and sufficient condition for the entire sequence of cards in the interval \([a, b]\) to be completely erasable is that “the stack state immediately before position \(a\)” and “the stack state immediately after position \(b\)” are identical.

As a concrete example, let us look at the stack state after processing each prefix of \(P = \text{`ABBAC`}\): - Initial state (\(0\) cards processed): () - 1st card (A): ('A',) - 2nd card (B): ('A', 'B') - 3rd card (B): ('A',) (popped because B matched) - 4th card (A): () (popped because A matched) - 5th card (C): ('C',)

Since the state immediately before index \(0\) (the initial state) and the state immediately after index \(3\) (after \(4\) cards) are both (), we can see that the interval \([0, 3]\) (ABBA) is completely erasable.

3. Matching with Target String \(T\)

Suppose we match the \(j\)-th character \(T_j\) of the target string \(T\) to \(S[i_j]\) of the original cards. To ensure that the remaining cards match \(T\), the following conditions must be satisfied:

1. For each \(j\), \(S[i_j] == T_j\).
2. All intervals between the remaining cards (\([0, i_1-1]\), \([i_1+1, i_2-1]\), \(\dots\), \([i_L+1, N-1]\)) are completely erasable.

Using stack states, Condition 2 can be rephrased as: “the stack state immediately after \(S[i_{j-1}]\) matches the stack state immediately before \(S[i_j]\)”.

---

Algorithm

We use Dynamic Programming (DP) to sequentially update up to which character of \(T\) has been matched.

Step 1: Precomputing Stack States

For each position \(k\) (\(0 \le k \le N\)), compute the stack state (tuple of colors) after processing the prefix \(P[0 \dots k-1]\), and assign a unique ID (stack_ids[k]) to each state.

Step 2: Matching Determination via DP

• dp[i]: A boolean flag (True / False) indicating whether it is possible to match up to the current character of \(T\) with its last character assigned to \(S[i]\).

1. Initialization (Matching \(T[0]\)):

   • Set dp[i] = True for positions \(i\) satisfying \(S[i] == T[0]\) and stack_ids[i] == stack_ids[0] (the ID of the empty stack).

2. Transitions (Matching \(T[j]\) for \(1 \le j < L\)):

   • While traversing \(i\) from \(0\) to \(N-1\), maintain a record (seen_stack) of stack states (stack_ids[i]) immediately following DP positions that were valid in the previous step.
   • If \(S[i] == T[j]\) and seen_stack[stack_ids[i]] is True, update the new DP array with dp[i] = True.

3. Final Decision:

   • After matching up to \(T[L-1]\), if there exists an \(i\) such that dp[i] == True and stack_ids[i+1] == stack_ids[N] (the trailing interval is also erasable), output Yes; otherwise, output No.

---

Complexity

• Time Complexity: \(O(N \cdot L + N^2)\)

  • Computing the stack state for each prefix takes \(O(N^2)\) (since there are at most 3 color types, the stack length is at most \(N\)).
  • The DP update is performed \(L\) times, each iterating through \(N\) elements, taking \(O(N \cdot L)\).
  • Since \(N, L \le 1000\), this easily fits within the time limit.

• Space Complexity: \(O(N^2)\)

  • Memory usage is at most \(O(N^2)\) to store the stack states (tuples).

---

Implementation Notes

• Speeding up DP Transitions: By preparing a seen_stack array and keeping track of the “stack IDs immediately after positions \(i-1\) where dp was True” as index \(i\) advances, transition checks can be done in \(O(1)\) time. This keeps each DP update step down to \(O(N)\).

• Ignoring Inputs: \(M\) and \(Q_1, \ldots, Q_L\) given in the problem statement are not used in the decision logic, but they still need to be properly consumed/skipped from the input.

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    L = int(input_data[2])

    S = input_data[3]
    P = input_data[4]
    T = input_data[5]

    # Compute stack state IDs for each prefix of P
    stack_ids = [0] * (N + 1)
    stack_map = {(): 0}
    cur_stack = []

    for k in range(N):
        if cur_stack and cur_stack[-1] == P[k]:
            cur_stack.pop()
        else:
            cur_stack.append(P[k])
        t = tuple(cur_stack)
        if t not in stack_map:
            stack_map[t] = len(stack_map)
        stack_ids[k + 1] = stack_map[t]

    num_stacks = len(stack_map)

    # DP to find if T can be matched
    # dp[i] is True if T[0...j-1] can be matched ending at S[i]
    dp = [False] * N
    T0 = T[0]
    target_stack_0 = stack_ids[0]
    for i in range(N):
        if S[i] == T0 and stack_ids[i] == target_stack_0:
            dp[i] = True

    if not any(dp):
        print("No")
        return

    for j in range(1, L):
        T_j = T[j]
        next_dp = [False] * N
        seen_stack = [False] * num_stacks

        for i in range(N):
            if i > 0 and dp[i - 1]:
                seen_stack[stack_ids[i]] = True

            if S[i] == T_j and seen_stack[stack_ids[i]]:
                next_dp[i] = True

        dp = next_dp
        if not any(dp):
            print("No")
            return

    # Final check: after matching T[L-1] at index i,
    # the suffix P[i+1...N-1] must be reducible to empty.
    target_stack_N = stack_ids[N]
    for i in range(N):
        if dp[i] and stack_ids[i + 1] == target_stack_N:
            print("Yes")
            return

    print("No")


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.6-flash-high.