When is there definitely not a solution?

First, note that since relative order is preserved no matter which elements are deleted, if $$$a$$$ is originally sorted in nondecreasing order, the array cannot be a derangement no matter which elements are deleted.

If $$$a$$$ is not sorted, we can note that any two elements that form an inversion pair satisfies the requirements. The total runtime is $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n;

    cin >> n;

    vector<int> arr(n);
    for(auto &x : arr) cin >> x;

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(arr[i] > arr[j]){
                cout << "YES\n2\n";
                cout << arr[i] << " " << arr[j] << "\n";
                return;
            }
        }
    }

    cout << "NO\n";
}

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

    int t;
    cin >> t;
    while(t--) solve();
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Write some examples of arrays down.

The answer is $$$\min(a_1,a_2)+a_1$$$.

If $$$a_1 \gt a_2$$$, we can perform the operation with $$$i=1$$$ and $$$j=2$$$, so that the prefix minimum after index $$$2$$$ will always be $$$0$$$ to get $$$a_1+a_2$$$ as our answer.

If $$$a_1 \lt a_2$$$, we can perform the operation with $$$i=2$$$ and $$$j=3$$$. Since $$$a_1 \lt a_2, min(a_1,a_2)=a_1$$$. The prefix minimum will be $$$0$$$ in index $$$3$$$ and later. We should be careful about the edge case $$$n=2$$$, as there is no index $$$3$$$ we can use. However, if $$$n=2$$$, we can simply not perform the operation.

We can easily show that the above cases are optimal for this problem. The code runs in $$$O(n)$$$, bottlenecked by reading the array.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(min(2*a[0], a[0] + a[1]))

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Come up with some numbers that $$$x$$$ must be a multiple of.

Take the LCM. Prove its sufficient (optional).

First, note that in order for $$$b$$$ to be obtainable after an array $$$a$$$, each $$$a_i$$$ should be a factor of $$$b_i$$$. We can find that $$$x$$$ must be a multiple of $$$b_i/gcd(b_i, b_{i+1})$$$ for each $$$1 \leq i \lt n$$$ as a lower bound for the answer.

Let's prove that these conditions are also sufficient. To do this, let's analyze each pair $$$(i,i+1)$$$ separately. We analyze the following cases: - if $$$b_i=a_i\cdot x$$$ and $$$b_{i+1}=a_{i+1}\cdot x$$$, or $$$b_i=a_i$$$ and $$$b_{i+1}=a_{i+1}$$$: in both cases, the choice of $$$x$$$ does not matter. The array is good if $$$b_i$$$ divides $$$b_{i+1}$$$ initially. - If $$$b_i=a_i\cdot x$$$ and $$$b_{i+1}=a_{i+1}$$$, then taking the LCM over all $$$1 \leq i \lt n$$$ should ensure this case is always correct. - If $$$b_i=a_i$$$ and $$$b_{i+1}=a_{i+1}\cdot x$$$, then a larger value of $$$x$$$ cannot possibly be beneficial, as the product $$$\frac{a_{i+1}}{a_i}$$$ decreases.

Since the problem guarantees $$$x$$$ exists, taking the LCM and outputting suffices. The solution runs in $$$O(n \log{a_i})$$$.

import sys
input = sys.stdin.readline
import math
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    gcd = 0
    lcm = 1
    for i in range(n-1,-1,-1):
        gcd = math.gcd(gcd, a[i])
        lcm = math.lcm(lcm, a[i] // gcd)
    print(lcm)

Solve the old version of this problem: given the array $$$b$$$ (where a solution is no longer guaranteed), output any array $$$a$$$ or claim it is not possible to obtain $$$b$$$ through a valid array $$$a$$$.

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Determine which elements you can delete with the operation.

Come up with a greedy solution that erases as little elements as possible.

First, let's come up with some conditions that determines whether erasing an element is possible.

Claim: as long as the $$$k-1$$$ smallest elements remain in the array, we can erase other elements in any way we want.

Proof: It is obvious why we cannot erase the $$$k-1$$$ smallest elements. If we want to erase any other element, we can simply start the following process to determine a pair of $$$(l,r)$$$ where we can erase the element: initially, start $$$l=1$$$ and $$$r=n$$$. Clearly, the element we want to erase is at least the $$$k$$$-th smallest element. After that, we can incrementally either increase $$$l$$$ or decrease $$$r$$$ until the element is exactly the $$$k$$$-th smallest. This process should always terminate because after $$$r-l+1 \lt k$$$, the element we want to delete is definitely less than the $$$k$$$-th smallest.

Let the $$$k-1$$$-th smallest element be $$$x$$$. Now, we can categorize each element in the array into three groups: elements less than $$$x$$$, elements equal to $$$x$$$, and elements greater than $$$x$$$. Note there is no point in keeping any elements in the third group, so we can erase them first (by creating a second array $$$b$$$ filled with only elements of the first and second groups). Now, we must strategically delete elements of the second group to make a palindrome. Note that we should try to erase as little elements as possible, because we must ensure the number of elements we don't erase is at least $$$k-1$$$. We can maintain this process with a two-pointers approach. Initialize $$$l=1$$$ and $$$r=|b|$$$. Then, if $$$b_l=b_r$$$, we can keep both. If $$$b_l\neq b_r$$$ and neither elements is $$$x$$$, we can conclude it's impossible. If one of $$$b_l,b_r$$$ is equal to $$$x$$$, we should flag the one equal to $$$x$$$ as being deleted and move the pointer. In the end, we can do a final check to ensure we did not erase too many elements.

The final solution runs in $$$O(n \log(n))$$$ due to sorting to find the $$$k$$$-th smallest element.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;
 
 
void solve() {
    int n; cin >> n;
    int k; cin >> k;
    vecin(aa, n);
    if (k == 1) {
        cout << "YES" << endl;
        return;
    }
 
    vector<int> bb = aa;
    sort(all(bb));
    int cutoff = bb[k - 2];
    vector<int> cc;
    for (auto a : aa)
        if (a <= cutoff)
            cc.push_back(a);
    int spare = cc.size() - k + 1;
    int L = 0, R = cc.size() - 1;
    bool bad = false;
    while (L < R) {
        if (cc[L] != cc[R]) {
            if (spare == 0) {
                bad = true; break;
            }
            if (cc[L] == cutoff) {
                L ++;
                spare --;
            } else if (cc[R] == cutoff) {
                R --;
                spare --;
            } else {
                bad = true; break;
            }
            continue;
        }
        L ++;
        R --;
    }
    if (bad) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}
 
int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;
 
    cin >> tt;
 
    while (tt--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

The answer is either $$$-1$$$, $$$1$$$, or $$$2$$$.

First, find a construction in $$$3$$$. Then, optimize that to be done in $$$2$$$ moves.

First, let's determine when the answer is $$$-1$$$. Let $$$s$$$ be the sum of all elements in the array. The answer is $$$-1$$$ if: 1. $$$s$$$ is odd, or 2. There exists an element that is greater than half of $$$s$$$.

If neither of the above conditions hold, we can definitely get a solution in finitely many moves by simply subtracting $$$1$$$ from the largest element and $$$1$$$ from an arbitrary element in one move.

Now, let's analyze a way to solve in $$$3$$$ moves. Let $$$pos$$$ be the unique position in the array where $$$a_1+a_2+\ldots+a_{pos-1} \lt \frac{s}{2}$$$ and $$$a_1+a_2+\ldots+a_{pos}\geq\frac{s}{2}$$$. Let $$$x,y,z$$$ denote $$$a_1+a_2+\ldots+a_{pos-1}$$$, $$$a_{pos}$$$, and $$$a_{pos+1}+a_{pos+2}+\ldots+a_n$$$ respectively. Our goal is to make $$$x+z=y$$$ in the first move after subtracting a non-negative integer $$$w$$$ from both $$$x$$$ and $$$y$$$, make $$$x=0$$$ and $$$z=y$$$ after the second move, and $$$x=y=z=0$$$ after the third. To prove the first move is always possible, note that $$$x+z-y$$$ is always even (since sum of all elements in the array is even), and because $$$y\leq \frac{s}{2}$$$ implies $$$x+z\geq\frac{s}{2}$$$.

Finally, to optimize this solution to $$$2$$$ moves, instead of subtracting $$$w$$$ from both $$$x$$$ and $$$z$$$ in the first move, let's subtract $$$x$$$ from the first block, $$$x-w$$$ from the second block, and $$$w$$$ from the third block. Essentially, we are combining the first two operations into one.

The solution runs in $$$O(n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
const ll MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;
 
int n;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    int T; cin >> T;
    for(int test = 1; test <= T; test++) {
        cin >> n;
        vector<ll> a(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        ll sum = 0;
        for(ll i : a) {
            sum += i;
        }
        if(sum % 2) {
            cout << "-1\n";
            continue;
        }
        ll mx = 0;
        for(ll i : a) {
            mx = max(mx, i);
        }
        if(mx * 2 > sum) {
            cout << "-1\n";
            continue;
        }
        ll cur = 0; int ind = 0;
        for(; ind < n; ind++) {
            if(cur + a[ind] > sum / 2) {
                ind--;
                break;
            }
            cur += a[ind];
        }
        if(cur == sum / 2) {
            cout << "1\n";
            for(ll i : a) {
                cout << i << " ";
            }
            cout << "\n";
        } else {
            cout << "2\n";
            vector<ll> aa(n);
            ll extra = sum - 2 * cur;
            aa[ind + 1] = extra / 2;
            a[ind + 1] -= aa[ind + 1];
            extra /= 2;
            for(int i = n - 1; i > ind + 1 && extra; i--) {
                if(a[i] >= extra) {
                    aa[i] = extra;
                    a[i] -= extra;
                    extra = 0;
                } else {
                    aa[i] = a[i];
                    extra -= a[i];
                    a[i] = 0;
                }
            }
            for(int i = 0; i < n; i++) {
                cout << a[i] << " ";
            }
            cout << "\n";
            for(int i = 0; i < n; i++) {
                cout << aa[i] << " ";
            }
            cout << "\n";
        }
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Given an integer $$$n$$$ and no restrictions, count the number of possible arrays you can form $$$(n \leq 2\cdot 10^5)$$$.

Characterize the arrays that we might overcount.

Optimize the DP using some cumulative sums.

1. Coming up with a polynomial solution

It's clear we need to do some sort of dynamic programming to count for this task. Initially, one may come up with let $$$dp_i$$$ be the number of ways to fill completely permutations with total length $$$i$$$.

Unfortunately, one downfall of the above solution is that some arrays are obtainable through many ways: for example, the array $$$[1,2,1]$$$ can be constructed with $$$[1]+[2,1]$$$ or $$$[1,2]+[1]$$$.

Upon further investigation, we can see that this occurs when we add two identity permutations of size $$$x$$$ and $$$y$$$ with $$$x \gt y$$$, as this can also be counted with a permutation of size $$$y$$$ and a shifted permutation of size $$$x$$$. We will choose to ban the second option (appending a shifted permutation that starts with $$$y+1$$$ when we just added a permutation of size $$$y$$$). We can come up with a counterexample to banning two identity permutations (a bigger one following a smaller one) with the array $$$[1,2,3,1,2,1]$$$, which can be counted as both $$$[1,2]+[3,1,2]+[1]$$$ and $$$[1]+[2,3,1]+[2,1]$$$.

This gives us a $$$O(n^4)$$$ solution. Let $$$dp(i,j)$$$ be the number of ways to make the sequence from indices $$$1$$$ through $$$i$$$, such that the last permutation added was an identity permutation of length $$$j$$$ (or not an identity permutation if $$$j=0$$$). We can build a solution by looping through (index, length of permutation, which cyclic shift to use), and checking if we can add this permutation naively.

1. Optimizing the solution to $$$O(n^2)$$$

There are several ways to do this part. Below shows one approach.

First, let's precalculate $$$chain(i,j)$$$, which returns the largest integer $$$k$$$ such that it is possible to fill numbers $$$i, i+1, \ldots, i+k-1$$$ with numbers $$$j,j+1,\ldots,j+k-1$$$. We can calculate this as $$$chain(i,j)=0$$$ if $$$a_i\neq j$$$ is a requirement, and $$$1+chain(i+1,j+1)$$$ otherwise. Let - $$$dp(i,j)$$$ be the number of ways to fill indices $$$i,i+1,\ldots,n$$$ such that $$$a_i=j$$$ - $$$dp_2(i)$$$ be the sum of $$$dp(i,j)$$$ over all $$$1 \leq j \leq n$$$. - $$$suff(i,j)$$$ be the number of ways such that we are ready to insert $$$j$$$ to complete the suffix from $$$i$$$ to $$$n$$$, but without taking into account restrictions.

We can calculate $$$suff(i,j)$$$ as $$$\sum_{x=i}^n(chain(x,1)\geq j-1)\cdot dp_2(x+j-1)$$$. Why is this helpful? Let's create an example. Suppose we fix $$$j=3$$$, and we have $$$chain(x,1)\geq 2$$$ is true for $$$x=3,4,6$$$. That is, it's possible to place $$$1$$$ and $$$2$$$ in positions $$$(3,4)$$$, $$$(4,5)$$$, and $$$(6,7)$$$. Then, we should have $$$suff(2,3)=dp_5+dp_6+dp_8$$$. Why is this helpful? Suppose we set $$$a_2=3$$$. Then our $$$suff(2,3)$$$ means that we can theoretically put $$$(3,1,2), (3,4,1,2), (3,4,5,6,1,2)$$$ starting at index $$$2$$$, assuming there are no further restrictions.

Now our actual DP loop: - Calculate $$$suff(i,j)$$$ as above - Calculate $$$dp(i,1)$$$ by looping through all identity permutations we can append at index $$$i$$$. Say we are trying to add identity permutation of length $$$x$$$. We should add $$$dp_2(i+x)$$$ and subtract $$$dp(i+x,x+1)$$$ (this is to prevent overcounting as outlined before). - Calculate $$$dp(i,j)$$$ for $$$j \gt 1$$$ as $$$suff(i+1,j)-suff(i+1+chain(i,j),j)$$$. The subtraction is to remove contribution from $$$suff$$$ that is not accessible due to constraints on $$$a_i \neq j$$$ using our chain array.

The entire solution works in $$$O(n^2+m)$$$. $$$m$$$ was kept low to allow $$$O(nm+n^2)$$$ to pass as well.

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

const int MOD = 998244353;
template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    os << "[ ";
    for(const auto& elem : vec) {
        os << elem << " ";
    }
    os << "]";
    return os;
}
struct Mint {
    int v;
    Mint(long long val = 0) {
        v = int(val % MOD);
        if (v < 0) v += MOD;
    }
    Mint operator+(const Mint &o) const { return Mint(v + o.v); }
    Mint operator-(const Mint &o) const { return Mint(v - o.v); }
    Mint operator*(const Mint &o) const { return Mint(1LL * v * o.v); }
    Mint operator/(const Mint &o) const { return *this * o.inv(); }
    Mint& operator+=(const Mint &o) { v += o.v; if (v >= MOD) v -= MOD; return *this; }
    Mint& operator-=(const Mint &o) { v -= o.v; if (v < 0) v += MOD; return *this; }
    Mint& operator*=(const Mint &o) { v = int(1LL * v * o.v % MOD); return *this; }
    Mint pow(long long p) const {
        Mint a = *this, res = 1;
        while (p > 0) {
            if (p & 1) res *= a;
            a *= a;
            p >>= 1;
        }
        return res;
    }
    Mint inv() const { return pow(MOD - 2); }
    friend ostream& operator<<(ostream& os, const Mint& m) {
        os << m.v;
        return os;
    }
};
void solve() {
    int N, K;
    cin >> N >> K;

    vector<vector<bool>> banned(N, vector<bool>(N));
    for (int i = 0; i < K; ++i) {
        int x, y;
        cin >> x >> y;
        banned[x - 1][y - 1] = true;
    }

    vector<Mint> tot(N + 1);
    tot[N] = 1;
    vector<vector<Mint>> dp(N + 1, vector<Mint>(N + 1));
    vector<vector<int>> chain(N + 1, vector<int>(N + 1));

    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j >= 0; --j) {
            chain[i][j] = 1 + chain[i + 1][j + 1];
            if (banned[i][j]) chain[i][j] = 0;
        }
    }

    vector<vector<Mint>> ssum(N + 2, vector<Mint>(N + 1));

    for (int i = N - 1; i >= 0; --i) {
        for (int j = 0; j <= N - i; ++j) {
            if (j == 0) {
                for (int len = 1; len <= N - i; ++len) {
                    bool ok = chain[i][0] >= len;
                    if (!ok) break;
                    dp[i][j] += tot[i + len];
                    dp[i][j] -= dp[i + len][j + len];
                }
            } else {
                if (chain[i][j]) {
                    dp[i][j] += ssum[i + 1][j];
                    if (i + 1 + chain[i][j] <= N) {
                        dp[i][j] -= ssum[i + 1 + chain[i][j]][j];
                    }
                }
            }
            tot[i] += dp[i][j];
        }

        for (int j = 1; j < N; ++j) {
            ssum[i][j] = ssum[i + 1][j];
            if (chain[i][0] >= j) {
                ssum[i][j] += tot[i + j];
            }
        }
    }
    // cout << dp << endl;
    // cout << ssum << endl;
    cout << tot[0].v << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Disregard cost first. Find the maximum sum of prefix minimums.

Come up with a way to have $$$O(n)$$$ $$$(i,j)$$$ pairs to test.

Let $$$f(a)=\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n)$$$. Can you come up with a way to solve $$$q$$$ queries of what $$$f(a)$$$ will be after performing the operation on $$$(i,j)$$$? (queries are not persistent here)

Let's disregard the cost part of the problem completely and try to solve the problem just for the maximum sum.

To solve this problem, we make the following observations: 1. If $$$i$$$ is not a prefix minimum, there is no point in using the operation to increase $$$a_i$$$. 2. If $$$j$$$ is not a suffix maximum, there is no point in using the operation to set $$$a_j:=0$$$. This is because we can instead use the closest suffix maximum to its right, and the final answer can only be larger.

Knowing this, let's enumerate $$$i$$$. If $$$i$$$ is not a prefix minima, we can skip it. Otherwise, there is no point to increasing $$$a_i$$$ past the previous prefix minima. Let's enumerate the number that we would like to increase $$$a_i$$$ to, and there should be a clear candidate on which suffix maximum to use as $$$j$$$. Since each $$$a_i$$$ is bounded by $$$n$$$, there is only $$$O(n)$$$ pairs of $$$(i,j)$$$ produced.

We now have to solve for what the score is after each operation. Suppose we increased $$$a_i$$$ to $$$x$$$. Let $$$k$$$ be the smallest index $$$k \gt i$$$ with $$$a_k\leq x$$$ ($$$k$$$ can be found by using a sparse table and binary search). We can now decompose $$$score(a)$$$ into the sum of the following four parts: 1. The prefix sum up to index $$$i$$$ — this can be precomputed easily 2. The score from $$$i$$$ to $$$k-1$$$ — this can be calculated easily as $$$x\cdot(k-i)$$$. 3. The score from $$$k$$$ to $$$n$$$ assuming $$$a_k$$$ is the prefix minimum. Call this $$$suffix(k)$$$. This can be precalculated as well using a monotonic stack. We can find the smallest number $$$l \gt k$$$ with $$$a_l \lt a_k$$$, then compute the answer as $$$suffix(l)+a_k\cdot(l-k)$$$. 4. Finally, we have to subtract the contribution from $$$j$$$ to $$$n$$$ since we set $$$a_j:=0$$$. Note that up to index $$$j$$$, the minimum $$$M$$$ is now $$$\min(a_1,a_2,\ldots,a_i-1, x, a_{i+1},a_{i+2},\ldots,a_{j-1})$$$. Now, we can use the same trick — binary search and sparse table to find the first $$$m\geq j$$$ with $$$a_m\leq M$$$, and subtract $$$suffix(m)+M(m-j)$$$ from our count here.

Now that we have a way to solve the full array, let's solve for all possible costs.

It can be shown that the same $$$O(n)$$$ queries from before will necessarily obtain the correct answers (proof is left as an exercise). Thus, to solve the problem, let's create an array $$$ans$$$, and while processing each $$$(i,j)$$$ pair, update $$$ans_{j-i}$$$. After that, taking the suffix maximum will suffice.

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "lib/debug.h"
#else
#define debug(...) 228
#endif
 
#define pb push_back
 
typedef long long ll;
typedef long double ld;
 
int n;
const int maxN = 1e6 + 10;
int a[maxN];
ll best[maxN];
ll pref[maxN];
int sec_mn[maxN];
ll pref_sec[maxN];
int MN[maxN];
int f[maxN];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= n - 1; i++) {
        best[i] = 0;
    }
    vector<int> suf_max;
    suf_max.reserve(n);
    for (int i = n; i >= 1; i--) {
        if (suf_max.empty() || a[i] > a[suf_max.back()]) {
            suf_max.emplace_back(i);
        }
    }
    int mn = 1e9;
    sec_mn[0] = 1e9;
    MN[0] = 1e9;
    int ind = -1;
    for (int i = 1; i <= n; i++) {
        sec_mn[i] = sec_mn[i - 1];
        if (a[i] < mn) {
            if (ind != -1) {
                f[ind] = i;
            }
            sec_mn[i] = mn;
            mn = a[i];
            ind = i;
        }
        else if (a[i] < sec_mn[i]) {
            sec_mn[i] = a[i];
        }
        MN[i] = mn;
        pref[i] = pref[i - 1] + mn;
        pref_sec[i] = pref_sec[i - 1] + sec_mn[i];
    }
    assert(ind != -1);
    f[ind] = n + 1;
    best[0] = pref[n];
    vector<int> st{n + 1};
    a[n + 1] = -1e9;
    for (int i = n; i >= 1; i--) {
        if (MN[i - 1] > a[i]) {
            for (int id: suf_max) {
                if (id <= i) break;
                int cur_mn = min(a[i] + a[id], MN[i - 1]);
                int l = 0;
                int r = st.size();
                while (r - l > 1) {
                    int mid = (l + r) / 2;
                    if (a[st[mid]] <= cur_mn) l = mid;
                    else r = mid;
                }
                int upto = min(id - 1, st[l] - 1);
                ll val = pref[i - 1] + cur_mn * 1LL * (upto - i + 1);
//                if (i == 3 && id == 5) {
//                    cout << " HI " << endl;
//                    cout << val << " " << cur_mn << " " << upto << endl;
//                }
                if (upto + 1 < id) {
                    int upup = min(f[i], id);
//                    if (i == 1 && id == 4) {
//                        cout << val << " ???? " << upup << endl;
//                    }
                    assert(upup - 1 >= upto);
                    val += pref_sec[upup - 1] - pref_sec[upto];
                    val += pref[id - 1] - pref[upup - 1];
                }
                best[id - i] = max(best[id - i], val);
                if (a[i] + a[id] >= MN[i - 1]) break;
            }
        }
        while (!st.empty() && a[i] <= a[st.back()]) st.pop_back();
        st.emplace_back(i);
    }
    for (int i = n - 2; i >= 0; i--) best[i] = max(best[i], best[i + 1]);
    for (int i = 0; i < n; i++) cout << best[i] << " ";
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = std::chrono::high_resolution_clock::now();
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Characterize what a good subsequence is.

Use a range DP approach and some greedy techniques to find the answer

Let's first determine whether a given sequence can be good. We claim that a sequence $$$b$$$ is good if for each index $$$1 \leq i \leq |b|$$$, if $$$b_i=x$$$, then one of the following must be true: 1. $$$x=i$$$ 2. $$$b_x=x$$$ and $$$min(b_x,b_{x+1},\ldots,b_i)\geq x$$$.

To prove this, we can note that this is necessary by transitivity of $$$ \gt $$$, and sufficient as we can construct a permutation (the method of doing so is left as an exercise to the reader).

Now, to find the length of the longest good subsequence, let's use range DP. Let $$$dp(i,j)$$$ be the length of the longest subsequence you can obtain if $$$b_i=i$$$, $$$b_j=i$$$, and $$$j$$$ is the last occurrence of $$$b_i$$$ in the sequence. We can enumerate $$$i$$$ from the back, and calculate the answer for each possible $$$j$$$. As we travel from $$$dp(i,j-1)$$$ to $$$dp(i,j)$$$, there are a few cases to consider: 1. $$$a_j=a_i$$$: we can simply add $$$1$$$ to $$$dp(i,j-1)$$$ to get $$$dp(i,j)$$$ as we can append it to our sequence for no cost. 2. $$$a_j \lt a_i$$$: we cannot append this due to the definition of good, so $$$dp(i,j)=dp(i,j-1)$$$. 3. $$$a_j \gt a_i$$$: Let's use a greedy approach to find where the segment beginning with $$$a_j$$$ should start. Clearly, it should start as soon as possible (since the starting point must have length $$$j$$$ already, and we cannot append anything less than $$$j$$$ before we begin). To do this, maintain a new array $$$first$$$ such that $$$first_k$$$ holds the smallest index $$$y$$$ where $$$a_y=y$$$ and $$$dp(i,y)\geq y$$$. Then, we can make the transition $$$dp(i,j)=\max(dp(i,j-1), dp(i,y-1)+dp(y,j))$$$.

The problem is solved in $$$O(n^2)$$$ time.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    
    for (int i = n; i >= 1; i--){
        vector <int> good(n + 1, -1);
        int curr = a[i];
        
        dp[i][i] = curr;
        
        for (int j = i + 1; j <= n; j++){
            if (a[j] < a[i]){
                continue;
            }
            
            if (a[j] == a[i]){
                curr += 1;
                dp[i][j] = curr;
                continue;
            }
            
            if (good[a[j]] == -1 && a[j] <= curr + 1){
                good[a[j]] = j;
            }
            
            if (good[a[j]] != -1){
                int idx = good[a[j]];
                curr = max(curr, dp[idx][j]);
            }
        }
    }
    
    // for (int l = 1; l <= n; l++){
    //     for (int r = l; r <= n; r++){
    //         if (dp[l][r])
    //         cout << l << " " << r << " " << dp[l][r] << "\n";
    //     }
    // }
    
    int curr = 0;
    vector <int> good(n + 1, -1);
    for (int j = 1; j <= n; j++){
        if (good[a[j]] == -1 && a[j] <= curr + 1){
            good[a[j]] = j;
        }
        
        if (good[a[j]] != -1){
            int idx = good[a[j]];
            curr = max(curr, dp[idx][j]);
        }
    }
    
    cout << curr << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Solve the inverse of this problem first. That is, given a permutation $$$p$$$, output $$$f(p)$$$.

Think very carefully why you can reconstruct for $$$[1,2,3,2,3]$$$ but not $$$[1,2,2,3,3]$$$.

Let's first come up with an algorithm to find $$$b$$$ given $$$p$$$.

Let $$$i$$$ be the first index with $$$p_i \lt p_1$$$. We can easily prove that the first subarray cannot go up to index $$$i$$$. This is because otherwise, the first element in $$$b$$$ will decrease, and this will be lexicographically smaller than a partition that does not include $$$i$$$.

Now, if $$$i=2$$$, then of course we should partition $$$p_1$$$ by itself. Otherwise, we should find the index $$$j$$$ with $$$1 \leq j \leq i$$$ and $$$p_j$$$ is the maximum element in the segment $$$[1,i]$$$, and partition up to $$$j-1$$$ (since this maximises the second element, which is what we want to do after maximising the first). We can now continue the process recursively, but assuming that $$$p_j$$$ is the front of the array.

Let's solve the actual problem now. Suppose we have $$$x_i=k$$$. Let $$$j$$$ be the largest index with $$$j \lt i$$$ and $$$x_j=k-1$$$. We can show that the sequence we obtain up to $$$i$$$ is the sequence up to $$$j$$$, plus $$$p_i$$$. This means that we can see the input array $$$b$$$ as the depths in a tree, where $$$j$$$ is the parent of $$$i$$$. We make the following observations: 1. If $$$x_i-x_{i-1} \gt 1$$$, then this is a trivial impossible case (the sequence up to $$$i$$$ or $$$i-1$$$ is invalid). 2. What does it mean if $$$i-j \gt 1$$$? This means that the sequence up to $$$i$$$ is an extension of $$$j$$$ (which is more than $$$1$$$ index ago), plus one number. From our analysis above, we know this means that all of $$$p_{j+1},p_{j+2},\ldots,p_i$$$ is greater than $$$p_j$$$, and $$$p_i$$$ is the largest of them all. 3. What does it mean if $$$i-j=1$$$? In this case, we cannot make any conclusions about the comparison of $$$p_i$$$ and $$$p_{i-1}$$$. Because index $$$i$$$ will be included no matter the comparison. 4. What does point $$$2$$$ mean? Observe the $$$[1,2,2,3,3]$$$ case again. Here, we should have $$$p_1 \lt p_2 \lt p_3$$$ and $$$p_3 \lt p_4 \lt p_5$$$. This implies $$$p_1 \lt p_2 \lt p_3 \lt p_4 \lt p_5$$$, but if this were the case then the array $$$x$$$ would be $$$[1,2,2,2,2]$$$ instead. More formally, looking at the tree, if node $$$i$$$ has more than one children, all of its children must have at most one children, or this contradiction will occur.

Using this, let's come up with a recursive function that traverses this tree and finds the permutation. Let $$$f(i,j,a,b)$$$ fill in $$$p_i,p_{i+1},p_{i+2},\ldots,p_j$$$ with numbers $$$a,a+1,a+2,\ldots,b$$$, where $$$i$$$ to $$$j$$$ is one full subtree, assuming that $$$i$$$ is already filled. First, let's find all direct children of node $$$i$$$ — that is all of the indices with $$$x_k=x_i+1$$$. If $$$i$$$ has more than one child and any of its children has more than one child, this is the impossible case as above. If $$$i$$$ has more than one child, then each of its children should have at most one child. First, let's assume that $$$p_i$$$ is already the smallest in the entire subtree. Let the sizes of subtrees of children be $$$b_1,b_2,\ldots,b_y$$$. We can reserve $$$b_i$$$ numbers for each subtree, and set each direct child to the largest number possible in each interval, and call our function recursively. Finally, if there is only one direct child, we can assume that $$$p_i$$$ is the largest number in the subtree, and we can assign the direct child to either be the largest or smallest number, depending on the number of children. We can first assign $$$p_1$$$ to be either $$$1$$$ or $$$n$$$ depending on how many indices $$$x_i=2$$$ there are, then call the recursive function. This will create the valid permutation.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define add push_back 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define trav(a,x) for (auto& a: x)
#define vt vector
#define endl "\n"
#define double long double
const ll mod = 998244353;
ll inf = 1e18;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
vt<int> solve(vt<int> &b, vt<vt<int>> &inv) {
    int n = b.size();
    stack<array<int,4>> s;
    if(n==1) {
        return {1};
    }
    vt<int> a(n);
    // cout << inv << endl;
    if(inv[2].size()>1) {
        a[0]=1;
        s.push({0,n-1,2,n});
    } else {
        a[0]=n;
        s.push({0,n-1,1,n-1});
    }
    while(s.size()) {
        auto tp = s.top();
        // cout << tp << endl;
        s.pop();
        if(tp[0]==tp[1]) continue;
        vt<int> nxt;
        int num = b[tp[0]]+1;
        while(inv[num].size() && inv[num].back()>tp[0]) {
            nxt.add(inv[num].back());
            inv[num].pop_back();
        }
        if(nxt.size()==1) {
            if(inv[num+1].size()>1 && inv[num+1][inv[num+1].size()-2]>tp[0]) {
                a[nxt[0]]=tp[2]++;
            } else {
                a[nxt[0]]=tp[3]--;
            }
            s.push({tp[0]+1, tp[1], tp[2], tp[3]});
        } else {
            tp[3]-=nxt.size();
            int nx = tp[3]+1;
            reverse(begin(nxt),end(nxt));
            // int prev = tp[0]+1;
            F0R(i, nxt.size()) {
                a[nxt[i]]= nx++;
                int nextInd;
                if(i!=nxt.size()-1) nextInd = nxt[i+1]-1;
                else nextInd = tp[1];

                int sz = nextInd-nxt[i]-1;
                // cout << nxt[i] << " " << nextInd << " " << sz << endl;
                s.push({nxt[i], nextInd, tp[2], tp[2]+sz});
                tp[2]+=sz+1;
            }
        }
    }
    return a;
}
signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    // freopen("input.txt" , "r" , stdin);
    // freopen("output.txt" , "w", stdout);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vt<int> x(n);
        F0R(i, n) cin >> x[i];
        vt<vt<int>> inv(n+2);
        F0R(i, n) inv[x[i]].add(i);
        if(inv[1].size()>1) {
            cout << "NO" << endl;
            continue;
        }
        bool ok = true;
        stack<array<int,3>> s;
        s.push({0,n-1,1});
        while(s.size()) {
            auto tp = s.top();
            s.pop();
            if(tp[0]==tp[1]) continue;
            if(x[tp[0]+1]!=x[tp[0]]+1) {
                ok=false;
                break;
            }
            vt<int> nxt;
            int num = x[tp[0]]+1;
            while(inv[num].size() && inv[num].back()>tp[0]) {
                nxt.add(inv[num].back());
                inv[num].pop_back();
            }
            reverse(begin(nxt),end(nxt));
            if(tp[2]==0 && nxt.size()!=1) {
                ok=false;
                break;
            }
            if(nxt.size()==1) {
                s.push({tp[0]+1, tp[1], 1});
            } else {
                F0R(i, nxt.size()) {
                    int nextInd;
                    if(i!=nxt.size()-1) nextInd = nxt[i+1]-1;
                    else nextInd = tp[1];
                    s.push({nxt[i], nextInd, 0});
                }
            }
        }
        inv = vt<vt<int>>(n+3);
        F0R(i, n) inv[x[i]].add(i);
        if(!ok) {
            cout << "NO" << endl;
            // assert(false);
        } else {
            auto a = solve(x,inv);
            cout << "YES\n";
            F0R(i, n) cout << a[i] << " ";

            cout << endl;
        }
    }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve