#include <bits/stdc++.h>
using namespace std;
 
int a[55],b[55];
 
void solve(){
    int n;cin>>n;
    set<int> sa,sb;
    for(int i=1;i<=n;i++)cin>>a[i],sa.insert(a[i]);
    for(int i=1;i<=n;i++)cin>>b[i],sb.insert(b[i]);
    if(sa.size()+sb.size()<4){
        cout<<"NO\n";
    }else{
        cout<<"YES\n";
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;cin>>t;
    while(t--){
        solve();
    }
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, k;
    cin >> n >> k;
    k /= 2;
    vector<int> a(n);
    for (auto &it: a) cin >> it;
    if (2 * k == n) {
        for (int i = 1; i < n; i += 2) {
            if (a[i] != (i + 1) / 2) {
                cout << (i + 1) / 2 << '\n';
                return;
            }
        }
        cout << k + 1 << '\n';
    } else {
        for (int i = 1; i <= n - 2 * k + 1; i++) {
            if (a[i] != 1) {
                cout << "1\n";
                return;
            }
        }
        cout << "2\n";
    }
}
 
int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

#include <bits/stdc++.h>
using namespace std;
 
const int N=305;
 
int a[N][N],suff[N];
 
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        suff[i]=0;
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=n;j>=1;j--){
            if(a[i][j]!=1)break;
            suff[i]++;
        }
    }
    multiset<int> s;
    for(int i=1;i<=n;i++){
        s.insert(suff[i]);
    }
    int ans=1;
    while(!s.empty()){
        int cur=*s.begin();
        if(cur>=ans){
            ans++;
        }
        s.extract(cur);
    }
    cout<<min(ans,n)<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;cin>>t;
    while(t--){
        solve();
    }
 
    return 0;
}

#include "bits/stdc++.h"
using namespace std;
 
#define int long long
#define eb emplace_back
 
const int INF = 1e18;
 
void solve() {
    int n, s1, s2;
    cin >> n >> s1 >> s2;
    s1--, s2--;
    vector<vector<int>> g1(n), g2(n);
    vector<bool> good(n);
    set<pair<int, int>> edges;
    int m1;
    cin >> m1;
    for (int i = 0; i < m1; i++) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        if (v > u)
            swap(v, u);
        edges.insert({v, u});
        g1[v].eb(u);
        g1[u].eb(v);
    }
    int m2;
    cin >> m2;
    for (int i = 0; i < m2; i++) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        if (v > u)
            swap(v, u);
        if (edges.find({v, u}) != edges.end())
            good[v] = true, good[u] = true;
        g2[v].eb(u);
        g2[u].eb(v);
    }
    vector<vector<int>> d(n, vector<int> (n, INF));
    d[s1][s2] = 0;
    set<pair<int, pair<int, int>>> st;
    st.insert({0, {s1, s2}});
    while (!st.empty()) {
        auto [v, u] = st.begin()->second;
        st.erase(st.begin());
        for (auto to1 : g1[v]) {
            for (auto to2 : g2[u]) {
                int w = abs(to1 - to2);
                if (d[to1][to2] > d[v][u] + w) {
                    st.erase({d[to1][to2], {to1, to2}});
                    d[to1][to2] = d[v][u] + w;
                    st.insert({d[to1][to2], {to1, to2}});
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; i++) {
        if (!good[i])
            continue;
        ans = min(ans, d[i][i]);
    }
    if (ans == INF)
        ans = -1;
    cout << ans << '\n';
}
 
signed main() {
    //cout << fixed << setprecision(5);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    //cin >> G;
    while (T--)
        solve();
    return 0;
}

Для минимизации количества операций нужно оставить как можно больше элементов в исходном массиве. Что это за элементы?

Эти элементы должны формировать префикс массива элементов изначально и подпоследовательность конечного массива.

Какое ещё условие нужно наложить на префикс элементов, чтобы добавлениями можно было получить конечный массив?

#include "bits/stdc++.h"
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n * m + 1), b(n * m + 1);
    vector<deque<int>> mat(n + 1, deque<int> (m));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            int ind = j + 1 + (i - 1) * m;
            mat[i][j] = ind;
            cin >> a[ind];
        }
    }
    for (int i = 1; i <= n * m; i++)
        cin >> b[i];
    map<int, int> mp;
    for (int i = 1; i <= n * m; i++)
        mp[b[i]] = i;
    vector<int> s(n * m + 1), pos(n * m + 1, -1);
    for (int i = 1; i <= n * m; i++) {
        if (mp.find(a[i]) != mp.end())
            pos[i] = mp[a[i]];
        else
            break;
    }
    pos[0] = 0;
    int skipped = 0, pref = 0;
    bool prev = true;
    for (int i = 1; i <= n * m; i++) {
        if (pos[i - 1] > pos[i])
            break;
        int d = pos[i] - pos[i - 1] - 1;
        if (prev)
            skipped += d;
        else if (d > 0)
            break;
        if (skipped >= m - 1)
            prev = true;
        else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
            prev = true;
        else
            prev = false;
        if (prev)
            pref = i;
    }
    cout << n * m - pref << '\n';
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

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

#define eb emplace_back
#define int long long
#define all(x) x.begin(), x.end()
#define fi first
#define se second

const int INF = 1e9 + 1000;
 
struct segtree {
    vector<pair<int, int>> tree;
    vector<int> ass;
    int size = 1;
 
    void init(vector<int> &a) {
        while (a.size() >= size) {
            size <<= 1;
        }
        tree.assign(2 * size, {});
        ass.assign(2 * size, 0);
        build(0, 0, size, a);
    }
 
    void build(int x, int lx, int rx, vector<int> &a) {
        if (rx - lx == 1) {
            tree[x].se = lx;
            if (lx < a.size()) {
                tree[x].fi = a[lx];
            } else {
                tree[x].fi = INF;
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(2 * x + 1, lx, m, a);
        build(2 * x + 2, m, rx, a);
        tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
    }
 
    void push(int x, int lx, int rx) {
        tree[x].fi += ass[x];
        if (rx - lx == 1) {
            ass[x] = 0;
            return;
        }
        ass[2 * x + 1] += ass[x];
        ass[2 * x + 2] += ass[x];
        ass[x] = 0;
    }
 
    void update(int l, int r, int val, int x, int lx, int rx) {
        push(x, lx,  rx);
        if (l <= lx && rx <= r) {
            ass[x] += val;
            push(x, lx, rx);
            return;
        }
        if (rx <= l || r <= lx) {
            return;
        }
        int m = (lx + rx) / 2;
        update(l, r, val, 2 * x + 1, lx, m);
        update(l, r, val, 2 * x + 2, m, rx);
        tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
    }
 
    void update(int l, int r, int val) {
        update(l, r + 1, val, 0, 0, size);
    }
 
    int req(int x, int lx, int rx) {
        push(x, lx, rx);
        if (rx - lx == 1) {
            return tree[x].se;
        }
        int m = (lx + rx) / 2;
        push(2 * x + 1, lx, m);
        push(2 * x + 2, m, rx);
        if (tree[2 * x + 2].fi == 0) {
            return req(2 * x + 2, m, rx);
        } else {
            return req(2 * x + 1, lx, m);
        }
    }
 
    int req() {
        return req(0, 0, size);
    }
};
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n * m + 1), b(n * m + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            int ind = j + 1 + (i - 1) * m;
            cin >> a[ind];
        }
    }
    for (int i = 1; i <= n * m; i++)
        cin >> b[i];
    map<int, int> mp;
    for (int i = 1; i <= n * m; i++)
        mp[b[i]] = i;
    vector<int> s(n * m + 1), pos(n * m + 1, -1);
    for (int i = 1; i <= n * m; i++) {
        if (mp.find(a[i]) != mp.end())
            pos[i] = mp[a[i]];
        else
            break;
    }
    pos[0] = 0;
    int skipped = 0, pref = 0;
    bool prev = true;
    for (int i = 1; i <= n * m; i++) {
        if (pos[i - 1] > pos[i])
            break;
        int d = pos[i] - pos[i - 1] - 1;
        if (prev)
            skipped += d;
        else if (d > 0)
            break;
        if (skipped >= m - 1)
            prev = true;
        else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)
            prev = true;
        else
            prev = false;
        if (prev)
            pref = i;
    }
    for (int i = 1; i <= pref; i++) {
        s[i - 1] = pos[i] - pos[i - 1] - 1;
    }
    s[pref] = n * m - pos[pref];
 
    vector<pair<int, int>> ans;
 
    int res = 0;
    for (int i = 0; i <= n * m; i++) {
        res += s[i];
    }
    vector<int> ost(pref + 1);
    for (int i = 1; i <= pref; i++) {
        ost[i] = (m - i % m) % m;
    }
    for (int i = 0; i <= pref; i++) {
        if (s[i] == 0) {
            ost[i] = INF;
        }
    }
    vector<int> gol(pref + 1);
    gol[0] = 1;
    for (int i = 1; i <= pref; i++) {
        gol[i] = (i + m - 1) / m + 1;
    }
 
    segtree tree;
 
    tree.init(ost);
 
    for (int step = 0; step < res; step++) {
        int chel = tree.req();
        ans.eb(gol[chel], b[pos[chel] + s[chel]]);
        tree.update(chel + 1, pref, -1);
        s[chel]--;
        if (s[chel] == 0) {
            tree.update(chel, chel, INF);
        }
    }
 
    cout << ans.size() << '\n';
    for (auto [i, col] : ans) {
        cout << i << " " << col << '\n';
    }
}
 
signed main() {
    //cout << fixed << setprecision(5);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    //cin >> G;
    while (T--)
        solve();
    return 0;
}