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

• 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

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

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