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)$$$.

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

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

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

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

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