Overview

This problem asks whether it is possible to match the target character sequence \(T\) and integer sequence \(Q\) with the remaining cards by repeatedly removing adjacent pairs of cards with the “same color and same integer” from the sequence of cards.

Since we can freely choose the integers to write, the problem essentially reduces to determining “whether all intervals other than the cards to be kept can be erased using only the color stack-based removal rule,” which can be efficiently solved using Dynamic Programming (DP).

---

Analysis

1. Irrelevance of the Integers \(M\) and \(Q\)

In the problem statement, the integers to be written on each card and the target integer sequence \(Q\) are given, but the integers to write can be chosen freely in the range from \(1\) to \(M\). By appropriately assigning the same integer to pairs of cards we want to erase, and assigning the target integer \(Q_k\) to the cards we want to keep, the integer conditions can always be satisfied. Therefore, the values of \(M\) and \(Q\) do not affect the decision, and we only need to consider “the color \(P\) and character \(S\) of each card.”

2. Erasability of Intervals and Stack States

Pairwise erasure of cards with colors \(A, B, C\) has the exact same structure as matching parentheses (stack). Consider looking at the colors sequentially from the beginning of the card sequence: if the current color is the same as the top of the stack, we pop (erase) it; if it is different, we push it.

Let \(\text{Stack}[i]\) be the state of the stack for the prefix up to the \(i\)-th card. Then, a necessary and sufficient condition for the interval \([l, r]\) (the group of cards from the \(l\)-th to the \(r\)-th) to be completely erasable is \(\text{Stack}[l-1] == \text{Stack}[r]\).

3. Conditions to Achieve the Target

To leave the target string \(T\) (length \(L\)), let the positions of the cards chosen from the original array be \(1 \le i_1 < i_2 < \dots < i_L \le N\). The conditions for this to be a valid choice are as follows:

1. Character matching: For each \(k \in [1, L]\), \(S_{i_k} = T_k\)
2. All cards in between are erasable:
   • From the beginning to right before \(i_1\): \(\text{Stack}[0] == \text{Stack}[i_1 - 1]\)
   • From right after \(i_k\) to right before \(i_{k+1}\): \(\text{Stack}[i_k] == \text{Stack}[i_{k+1} - 1]\)
   • From right after \(i_L\) to the end: \(\text{Stack}[i_L] == \text{Stack}[N]\)

---

Algorithm

1. Precomputing Stack States and Assigning IDs (Coordinate Compression)

   • For each \(i \ (0 \le i \le N)\), compute the stack string \(\text{Stack}[i]\) for the prefix \(P[0 \dots i-1]\).
   • To speed up string comparisons, assign integer IDs (\(0, 1, 2, \dots\)) to unique stack strings.

2. Dynamic Programming (DP)

   • DP State: dp[j] = a boolean value representing whether it is possible to match up to the \(k\)-th character of \(T\), choosing \(S_{j-1}\) as the \(k\)-th character.
   • Transitions:
     • Loop through \(k = 1 \dots L\).
     • Maintain the set of stack IDs immediately after the card positions \(p\) that were possible in the previous step (\(\text{Stack}[p]\)) (when \(k=1\), it contains only \(\text{Stack}[0]\)).
     • For each \(j \ (1 \le j \le N)\), if \(S_{j-1} == T_{k-1}\) and \(\text{Stack}[j-1]\) is contained in the above set, set next_dp[j] = true.
   • Final Decision:
     • After completing \(k = L\), if there exists a \(j\) such that dp[j] == true and \(\text{Stack}[j] == \text{Stack}[N]\), output Yes; otherwise, output No.

---

Complexity

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

  • The length of the stack string at each position is at most \(N\). Constructing the \(N+1\) stack strings and mapping them to IDs (std::map) takes \(O(N^2 \log N)\) or \(O(N^2)\).
  • The DP update consists of an outer loop running \(L\) times and an inner loop running \(N\) times, with each element update taking \(O(1)\).
  • Since \(L \le N\), the overall execution is sufficiently fast.

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

  • Uses \(O(N^2)\) memory to store \(N+1\) stack strings of length at most \(N\).

---

Implementation Points

• Converting Stack Strings to IDs: Comparing stack states as strings within DP would take \(O(N)\) time per comparison. By compressing them to integer IDs beforehand using map<string, int>, comparisons within DP can be performed in \(O(1)\) time.

• Index Correspondence: It is important to correctly manage the correspondence between 1-based and 0-based indexing (especially the relationships between \(S[j-1]\), \(\text{Stack}[j-1]\), and \(\text{Stack}[j]\)).

  Source Code

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, L;
    if (!(cin >> N >> M >> L)) return 0;

    string S, P, T;
    cin >> S >> P >> T;

    vector<int> Q(L);
    for (int i = 0; i < L; ++i) {
        cin >> Q[i];
    }

    // Precompute stack state strings for P[0...i-1] for i = 0...N
    vector<string> Stack(N + 1);
    Stack[0] = "";
    for (int i = 1; i <= N; ++i) {
        string cur = Stack[i - 1];
        char c = P[i - 1];
        if (!cur.empty() && cur.back() == c) {
            cur.pop_back();
        } else {
            cur.push_back(c);
        }
        Stack[i] = cur;
    }

    // Compress Stack strings to integer IDs
    map<string, int> stack_to_id;
    vector<int> stack_id(N + 1);
    int num_ids = 0;
    for (int i = 0; i <= N; ++i) {
        if (stack_to_id.find(Stack[i]) == stack_to_id.end()) {
            stack_to_id[Stack[i]] = num_ids++;
        }
        stack_id[i] = stack_to_id[Stack[i]];
    }

    // DP state: dp[j] indicates if T[0...k-1] can be matched ending at S[j-1]
    vector<bool> dp(N + 1, false);

    for (int k = 1; k <= L; ++k) {
        vector<bool> next_dp(N + 1, false);
        vector<bool> valid(num_ids, false);

        for (int j = 1; j <= N; ++j) {
            int p = j - 1;
            if (k == 1) {
                if (p == 0) {
                    valid[stack_id[0]] = true;
                }
            } else {
                if (p >= 1 && dp[p]) {
                    valid[stack_id[p]] = true;
                }
            }

            if (S[j - 1] == T[k - 1] && valid[stack_id[j - 1]]) {
                next_dp[j] = true;
            }
        }
        dp = next_dp;
    }

    // Final answer check
    bool ok = false;
    for (int j = 1; j <= N; ++j) {
        if (dp[j] && stack_id[j] == stack_id[N]) {
            ok = true;
            break;
        }
    }

    if (ok) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

---

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