Let $$$f_{l, r}$$$ denote $$$0$$$ if we cannot reduce the subarray $$$a_l,\dots,a_r$$$ to a single element. Otherwise it will denote the value this subarray can be reduced to.

Claim: If the subarray can be reduced to a single element, the value is always same, regardless the order of operations.

$$$f_{l,r}$$$ can be calculated by the following recursive relation, \begin{equation} $f_{l,r} = \begin{cases} a_l &\text{if $$$l = r$$$} \newline \max_{i = l}^{r — 1} [f_{l,i} = f_{i+1,r}] (f_{l,i} + 1) &\text{otherwise} \end{cases} \end{equation} Note: $$$[a]$$$ evaluates to $$$0$$$ if a is false, and $$$1$$$ otherwise.$$$\newline$$$ The remaining problem is trivial.

Let $$$dp_i$$$ be the minimum length the prefix $$$a_1,a_2,\dots,a_i$$$ can be reduced to. We can formulate the simple recursive relation $$$dp_i = \min_{2 \leq j \leq i, \ f_{j,i} \ne 0} \ \ dp_{j-1} + f_{j,i}$$$ where $$$dp_1 = 1.$$$ $$$dp_n$$$ is our answer.

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

const int N = 505;

int a[N];
int f[N][N];
int dp[N];

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

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f[i][i] = a[i];
    }

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int j = l; j < r; j++) {
                if (f[l][j] && f[l][j] == f[j + 1][r])
                    f[l][r] = f[l][j] + 1;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        dp[i] = 1e7;
        for (int j = 0; j < i; j++)
            if (f[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1);
    }

    cout << dp[n] << endl;
}

We can iterate over all prefixes of $$$t$$$ and try to create the prefix and the remaining suffix of $$$t$$$ as two disjoint subsequences from $$$s$$$. So the problem reduces to finding if two strings $$$a$$$ and $$$b$$$ can be disjoint subsequence of a given string $$$s$$$.

The reduced problem given as a hint can be trivially solved with dp using 3 states: let $$$f_{i,j,k}$$$ denote whether the prefix of $$$a$$$ of size $$$j$$$ and prefix of $$$b$$$ of size $$$k$$$ can be created by using the first $$$i$$$ characters of $$$s$$$ in a disjoint manner. $$$f_{i,j,k}$$$ can be easily calculated. If $$$s_i = a_j = b_k$$$ then we need to make a choice between inserting the current character in $$$a$$$ and $$$b$$$, we will explore both routes. Otherwise if $$$s_i$$$ matches with either one of the strings' current characters, we can use it in that string. \begin{equation} f_{i,j,k} = \begin{cases} 1 &\text{if } i = 0 \text{ and } j = 0 \text{ and } k = 0\newline 0 &\text{if } i = 0 \text{ and (} j > 0 \text{ or } k > 0\text{)}\newline f_{i-1,j-1,k} \ | \ f_{i-1,j,k-1} &\text{if } s_i = a_j = b_k \newline f_{i-1,j-[s_i = a_j],k-[s_i=b_k]} &\text{otherwise} \end{cases} \end{equation} However this will run in $$$O(|s||a||b|)$$$ or $$$O(|s|^3)$$$ for every prefix, which will exceed limits in this problem. We will improve this by reducing a state and changing return parameters. Instead of iterating over the characters of $$$s$$$ and choosing between appending to $$$a$$$ or $$$b$$$, we ask — what is the smallest prefix of $$$s$$$ that can contain prefix of size $$$j$$$ of $$$a$$$ and size $$$k$$$ of $$$b$$$ as disjoint subsequences. Let's define the answer to $$$|s|+1$$$ if such a prefix doesn't exist, let this be denoted by $$$dp_{j,k}$$$. To calculate this, we can precompute $$$nxt_{i,c}$$$ which is the index of the next occurrence of character $$$c$$$ after the $$$i$$$-th index in $$$s$$$. Again defined to be $$$|s| + 1$$$ if it doesn't exist. \begin{equation} dp_{i,j} = \begin{cases} 0 &\text{if } i = j = 0\newline min\left(nxt_{dp_{i-1,\ j},\ a_i},\ \ nxt_{dp_{i,\ j-1},\ b_j}\right) &\text{otherwise} \end{cases} \end{equation} Which will run in $$$O(|s|^2)$$$ for every prefix.

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int nxt[405][27];
void minimize(int &a, int b) {
    a = min(a, b);
}
bool disjoint_substrings(string s, string &a, string &b) {
    int n = s.size(), len_a = a.size(), len_b = b.size();
    vector <vector <int>> dp(len_a + 1, vector <int> (len_b + 1, n + 1));
    for(int i = 0; i <= len_a; i++) {
        for(int j = 0; j <= len_b; j++) {
            if(i == 0 and j == 0) {
                dp[i][j] = 0;
                continue;
            }
            if(j > 0) minimize(dp[i][j], nxt[dp[i][j - 1]][b[j - 1] - 'a']);
            if(i > 0) minimize(dp[i][j], nxt[dp[i - 1][j]][a[i - 1] - 'a']);
        }
    }
    return dp[len_a][len_b] <= n;
}
int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        string s, t;
        cin >> s >> t;
        int n = s.size(), m = t.size();
        for(int i = 0; i <= n + 1; i++)
            for(int j = 0; j < 26; j++) nxt[i][j] = n + 1;
        for(int i = n - 1; i >= 0; i--) {
            for(int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 1][j];
            nxt[i][s[i] - 'a'] = i + 1;
        }
        bool f = false;
        for(int i = 1; i <= m; i++) {
            string a = t.substr(0, i), b = t.substr(i, m - i);
            f |= disjoint_substrings(s, a, b);
        }
        cout << (f ? "YES\n" : "NO\n");
    }
}

Similar to the previous problem, this can be done in a straightforward manner. For every character of $$$s$$$, we can either choose to or delete it, or keep it in $$$s$$$ and try to make a substring equal to $$$p$$$ with it, while ensuring exactly $$$x$$$ characters are deleted in the end. But if we try to keep track of how much of $$$p$$$ has been built, how many characters have been deleted as well as which is the current character of $$$s$$$, there will be too many states and will exceed time limits. Here we can observe that we don't need to keep track of how much of $$$p$$$ has been currently built, because whenever we start building $$$p$$$ as a substring, it is always as good or better to finish it instead of leaving it incomplete(this is a consequence of substrings not overlapping). For every index, we can pre-calculate if a substring of $$$s$$$ equal to $$$p$$$ starts in this index in O(|s| * |p|) by brute-force, or O(|s| + |p|) using KMP or other matching algorithms. Now we only need to keep the current index and number of characters yet to be deleted as parameters, and for every index, we can delete it or try to complete a substring equal to $$$p$$$ starting from it. This can be calculated in $$$O(|s| * |s|)$$$ for all values of $$$x$$$.

The solution is done slightly differently, but overall it is similar enough so I didn't rewrite.

#include <bits/stdc++.h>
using namespace std;
int nxt[2005][505], dp[2005][2005];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s, p;
    cin >> s >> p;
    int n = s.size(), m = p.size();
    for(int i = 0; i <= n; i++) nxt[i][m] = i;
    for(int i = 0; i < m; i++) nxt[n][i] = 2 * n;
    for(int i = n - 1; i >= 0; i--) {
        for(int j = m - 1; j >= 0; j--) {
            nxt[i][j] = nxt[i + 1][j + (s[i] == p[j])];
        }
    }
    for(int i = 1; i <= n; i++) dp[n][i] = -2 * n;
    dp[n][0] = 0;
    for(int i = n - 1; i >= 0; i--) {
        for(int x = n; x >= 0; x--) {
            int j = nxt[i][0], del = j - i - m;
            dp[i][x] = dp[i + 1][x];
            if(x > 0) dp[i][x] = max(dp[i][x], dp[i + 1][x - 1]);
            if(j <= n and x >= del) 
                dp[i][x] = max(dp[i][x], 1 + dp[j][x - del]);
        }
    }
    for(int i = 0; i <= n; i++) cout << dp[0][i] << '\n';
}

The string created after some number of operations will stay adjacent after all future operations. Hence the operations can be simulated as an interval DP. And we have three options in each step, appending, prepending and stopping, and we will set up transitions as such.

We can represent the expression for $$$a$$$ as $$$a = t \ + $$$ some wildcards (they are characters that can match with any other characters in this case). We will represent a wildcard with $$$'*'$$$. So when we say two characters $$$x$$$ and $$$y$$$ are equal, we mean $$$x = y$$$ or $$$x = *$$$ or $$$y = *$$$. Note: adding wildcards isn't necessary for the solution, but they make the solution simpler to explain and less case-handling. Also 1-based indexing is used in the following paragraph.

Let's formulate a dynamic programming solution. After some operations, let the current string be $$$b$$$. In the final string $$$a$$$, b is substring in some interval. We represent this interval by $$$(l, r)$$$ where $$$l$$$ is the index in $$$a$$$ where $$$b$$$ starts and $$$r$$$ is the finishing index. Notice that we don't need to keep the information of how many characters of $$$s$$$ has been used, because it's simply the length of $$$b$$$. Let $$$dp_{l, r}$$$ be the number of ways we can finish the string to have the $$$t$$$ as a prefix if we have already built in the interval $$$(l, r)$$$ of $$$a$$$. The transition follows simple, if we have already built a prefix of length $$$m$$$, we can stop or keep appending. Otherwise we can't stop, and we will append or prepend only when the operation can match the characters accordingly. That is, we can transition from $$$dp_{l, r}$$$ to $$$dp_{l, r + 1}$$$ if $$$r < n$$$ and $$$s_{r - l + 2} = a_{r + 1}$$$ (wildcard matching applies here). Similarly we can transition from $$$dp_{l, r}$$$ to $$$dp_{l - 1, r}$$$ if $$$l > 1$$$ and $$$s_{r - l + 2} = a_{l - 1}$$$. We have yet to consider the base case — the first character. The first character can be inserted in any position it matches in $$$a$$$, that is, all positions $$$i$$$ such that $$$s_0 = a_i$$$, and it can be inserted in two ways since appending and prepending to an empty string is the same. Overall time complexity is $$$O(n^2)$$$. Note: The author editorial gives a similar solution with different parameters, but same idea. It doesn't use wildcards and runs in $$$O(n * m)$$$.

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 998244353;
string s, t;
LL dp[3005][3005];
int n, m;
LL call(int l, int r) {
    if(l == 0 and r == n - 1) return 1;
    LL &ret = dp[l][r];
    if(ret != -1) return ret;
    ret = 0;
    if(l == 0 and r >= m - 1) ret++; // we can stop
    if(r < n - 1 and (s[r - l + 1] == t[r + 1] or t[r + 1] == '*')) 
        (ret += call(l, r + 1)) %= mod; // append
    if(l > 0 and (s[r - l + 1] == t[l - 1] or t[l - 1] == '*')) 
        (ret += call(l - 1, r)) %= mod; // prepend
    return ret;
}
int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cin >> s >> t;
    n = s.size(), m = t.size();
    while(t.size() < n) t += '*';
    memset(dp, -1, sizeof dp);
    LL ans = 0;
    for(int i = 0; i <= n; i++) 
        if(s[0] == t[i] or t[i] == '*') (ans += call(i, i)) %= mod;
    cout << (ans * 2) % mod << '\n';
}

Any subtree in the binary search tree represents an interval in the original array.

For some interval $$$(l, r)$$$ which is represented by a subtree in the final BST, if the root of the subtree is at $$$a_i$$$ ($$$l \leq i \leq r$$$) then the next subtrees of the child represent the intervals $$$(l, i - 1)$$$ and $$$(i + 1, r)$$$. Again we choose roots from those sub-intervals and build the tree. A simple dp solution might be to keep the intervals and the chosen root as a parameter and iterate over all pairs of children that are not coprime and solve the subproblems. But this approach will run in $$$O(n^4)$$$ which will not pass. The observation here is that for some interval $$$(l, r)$$$ with root at $$$i$$$ with two children, we can consider it as two independent intervals $$$(l, i)$$$ with root at $$$i$$$ with one child, and $$$(i, r)$$$ with root at $$$i$$$ with one child. This means that don't need to explicitly choose a root for an interval, we can be sure that it's one of the two bounds of the interval, and we just need to know which one.

Let $$$left_{l, r}$$$ denote whether it is possible to create a binary tree with no co-prime adjacent nodes in the interval $$$(l, r)$$$ with root at $$$l$$$. Let $$$right_{l, r}$$$ be the same but with root at $$$r$$$. An interval $$$(l, r)$$$ is empty if $$$l > r$$$.

\begin{equation} left_{l,r} = \begin{cases} true &\text{if } l > r\newline \lor_{i = l + 1}^{r} \ right_{l + 1, i} \ \land \ left_{i, r} &\text{otherwise} \end{cases} \end{equation} note: here \lor is used for logical or and \land is used for logical and. Similarly, \begin{equation} right_{l,r} = \begin{cases} true &\text{if } l > r\newline \lor_{i = l}^{r — 1} \ right_{l, i} \ \land \ right_{i, r — 1} &\text{otherwise} \end{cases} \end{equation}