Summary

We select the cards to keep as a subsequence corresponding to the string \(T\), and determine whether all card sequences before, after, and between them can be completely erased.
By normalizing the erasability of color sequences using a stack and applying dynamic programming, we can solve this problem in \(O(NL)\).

Analysis

On the Integers Written

For the \(k\)-th card we decide to keep, we write \(Q_k\) on it as required. On the other hand, for cards to be erased, writing the integer \(1\) on all of them is sufficient.

Then, the condition “the integers are equal” is always satisfied between cards to be erased, so whether a sequence can be erased depends solely on their colors. Also, since erasing adjacent matching cards is not mandatory, cards that we intend to keep will not be accidentally erased.

Therefore, \(M\) and \(Q\) do not affect the determination of erasability.

Is a Color Sequence Erasable?

Consider the operation of removing adjacent identical colors from a color sequence. This can be normalized using the following stack operation:

• If the top of the stack is equal to the current color, remove the top of the stack (pop).
• Otherwise, add the current color to the stack (push).

For example, ABBA becomes:

• A
• AB
• A (BB is erased)
• Empty (AA is erased)

Thus, it can be completely erased.

On the other hand, in ABAB, each color appears an even number of times, but because identical colors are never adjacent, it cannot be erased. Simply counting the occurrences of each color is not sufficient.

Let \(\mathrm{state}[x]\) be the state obtained by normalizing the prefix of the first \(x\) cards of a color sequence \(P\) using the stack. Here, \(\mathrm{state}[0]\) is the empty state.

At this point, the condition that all cards in the half-open interval \([l,r)\) can be erased is equivalent to

\[ \mathrm{state}[l]=\mathrm{state}[r] \]

Reading each color is a reversible operation (popping if the top of the stack matches the color, pushing otherwise). Therefore, if the state before reading an interval is identical to the state after reading it, that interval as a whole can be normalized to empty.

Selecting Cards to Keep

Let the positions of the cards to keep be

\[ a_0<a_1<\cdots<a_{L-1} \]

Naturally, for each \(k\), we need

\[ S_{a_k}=T_k \]

Furthermore, cards cannot be erased across a card that is kept. Therefore, each of the following intervals must be completely erased independently:

• Before the first kept card
• Between adjacent kept cards
• After the last kept card

Using the states, these conditions can be expressed as follows:

\[ \mathrm{state}[a_0]=\mathrm{state}[0] \]

\[ \mathrm{state}[a_{k-1}+1]=\mathrm{state}[a_k] \quad (1\leq k<L) \]

\[ \mathrm{state}[a_{L-1}+1]=\mathrm{state}[N] \]

Issues with the Naive Approach

If we enumerate all subsequences corresponding to \(T\), the number of candidates becomes exponential.

Also, if we use dynamic programming and try all possible previously kept positions, each transition takes \(O(N)\), resulting in an overall time complexity of \(O(LN^2)\). For \(N, L \leq 1000\), this requires up to around \(10^9\) operations, which will not run in time.

Therefore, instead of tracking the exact previous position itself, we only track whether the required state \(\mathrm{state}[j+1]\) is reachable. This allows us to process each DP stage in \(O(N)\).

Algorithm

1. Find the Normalized State for Each Prefix

We represent the normalized stack as nodes in a persistent tree.

Each node maintains the following:

• parent: The state after popping the top of the stack
• topColor: The color at the top of the stack
• child[color]: The state after pushing that color

When reading color \(c\):

• If the current top color is \(c\), move to parent.
• Otherwise, move to child[c].

Only create a new node if child[c] does not exist yet.

This ensures that identical normalized results are always assigned the same state ID.
Let \(\mathrm{state}[x]\) be the state ID after reading the first \(x\) cards.

2. Select Cards to Keep via DP

After choosing up to the \(k\)-th character:

• dp[i] = true:
  Cards corresponding to \(T_0,\ldots,T_k\) can be chosen, with the last chosen position being \(i\).

Initialization

Since all cards before the first kept card must be erased, we set dp[i] = true for positions \(i\) satisfying:

\[ S_i=T_0 \quad\text{and}\quad \mathrm{state}[i]=\mathrm{state}[0] \]

Transitions

Let \(j\) be the previously kept position and \(i\) be the newly kept position, where \(j < i\). The interval \([j+1, i)\) between them must be erased.

Therefore, we require:

\[ \mathrm{state}[j+1]=\mathrm{state}[i] \]

We scan position \(i\) from left to right, recording \(\mathrm{state}[j+1]\) for reachable \(j < i\) into reachableState. Then, if

\[ S_i=T_k \quad\text{and}\quad \mathrm{reachableState}[\mathrm{state}[i]] \]

is satisfied, position \(i\) can be the next card to keep.

This allows us to process the transitions for each \(k\) in \(O(N)\).

3. Check After the Last Card

When the last kept position is \(i\), the condition for the trailing interval \([i+1, N)\) to be erased is:

\[ \mathrm{state}[i+1]=\mathrm{state}[N] \]

If there is at least one dp[i] = true satisfying this condition, the answer is Yes; otherwise, No.

Complexity

• Time Complexity: \(O(NL)\)
• Space Complexity: \(O(N)\)

Implementation Notes

• state[x] represents the state after processing the first \(x\) cards, i.e., the interval \([0, x)\). Be careful with index offsets relative to card positions.

• Since persistent stack states are managed using integer IDs, there is no need to compare strings or hashes, and collisions will not occur.

• In the DP transitions, before evaluating position \(i\), we add state[i] corresponding to dp[i-1] to reachableState. This ensures that the previous position is strictly less than \(i\).

• \(M\) and \(Q\) are intentionally not used in the determination, as we can simply write \(Q\) on the kept cards and \(1\) on all erased cards.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, L;
    cin >> N >> M >> L;

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

    vector<int> Q(L);
    for (int &q : Q) cin >> q;

    vector<int> parent(1, -1), topColor(1, -1);
    vector<array<int, 3>> child(1, array<int, 3>{-1, -1, -1});
    vector<int> state(N + 1, 0);

    int current = 0;
    for (int i = 0; i < N; ++i) {
        int color = P[i] - 'A';

        if (topColor[current] == color) {
            current = parent[current];
        } else {
            int next = child[current][color];
            if (next == -1) {
                next = static_cast<int>(parent.size());
                child[current][color] = next;
                parent.push_back(current);
                topColor.push_back(color);
                child.push_back(array<int, 3>{-1, -1, -1});
            }
            current = next;
        }
        state[i + 1] = current;
    }

    const int stateCount = parent.size();
    vector<char> dp(N, false), nextDp(N, false);

    for (int i = 0; i < N; ++i) {
        if (S[i] == T[0] && state[i] == state[0]) {
            dp[i] = true;
        }
    }

    for (int k = 1; k < L; ++k) {
        fill(nextDp.begin(), nextDp.end(), false);
        vector<char> reachableState(stateCount, false);

        for (int i = 0; i < N; ++i) {
            if (i > 0 && dp[i - 1]) {
                reachableState[state[i]] = true;
            }

            if (S[i] == T[k] && reachableState[state[i]]) {
                nextDp[i] = true;
            }
        }

        dp.swap(nextDp);
    }

    for (int i = 0; i < N; ++i) {
        if (dp[i] && state[i + 1] == state[N]) {
            cout << "Yes\n";
            return 0;
        }
    }

    cout << "No\n";
    return 0;
}

---

This editorial was generated by gpt-5.6-sol-high.