give solution in cpp B. Shrinking Array time limi...

Question

give solution in cpp

B. Shrinking Array
time limit per test2 seconds
memory limit per test256 megabytes
Let's call an array b beautiful if it consists of at least two elements and there exists a position i such that |b_i - b_{i + 1}| \le 1 (where |x| is the absolute value of x).

You are given an array a, and as long as it consists of at least two elements, you can perform the following operation:

Choose two adjacent positions i and i + 1 in the array a.
Choose an integer x such that \min(a_i, a_{i + 1}) \le x \le \max(a_i, a_{i + 1}).
Remove the numbers a_i and a_{i + 1} from the array, and insert the number x in their place. Obviously, the size of the array will decrease by 1.
Calculate the minimum number of operations required to make the array beautiful, or report that it is impossible.

Input
The first line contains one integer t (1 \le t \le 200) — the number of test cases.

The first line of each test case contains one integer n (2 \le n \le 1000) — the size of the array a.

The second line contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^6) — the array a itself.

Output
For each test case, output one integer — the minimum number of operations needed to make the array a beautiful, or -1 if it is impossible to make it beautiful.

Example
InputCopy
4
4
1 3 3 7
2
6 9
4
3 1 3 7
4
1 3 5 2
OutputCopy
0
-1
1
1
Note
In the first test case, the given array is already beautiful, as |a_2 - a_3| = |3 - 3| = 0.

In the second test case, it is impossible to make the array beautiful, as applying the operation would reduce its size to less than two.

In the third test case, you can, for example, choose a_1 and a_2 and replace them with the number 2. The resulting array [2, 3, 7] is beautiful.

In the fourth test case, you can, for example, choose a_2 and a_3 and replace them with the number 3. The resulting array [1, 3, 2] is beautiful.

Answer 1

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

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // Check if already beautiful (adjacent diff <= 1)
        bool zero = false;
        for (int i = 0; i + 1 < n; i++) {
            if (abs(a[i] - a[i+1]) <= 1) {
                zero = true;
                break;
            }
        }
        if (zero) {
            cout << 0 << "\n";
            continue;
        }

        // Check if can become beautiful in one merge
        bool one = false;
        // consider merging each adjacent pair (i, i+1)
        for (int i = 0; i + 1 < n && !one; i++) {
            int L = min(a[i], a[i+1]);
            int R = max(a[i], a[i+1]);
            // left neighbor at i-1
            if (i - 1 >= 0) {
                int mn = a[i-1] - 1;
                int mx = a[i-1] + 1;
                if (max(L, mn) <= min(R, mx)) {
                    one = true;
                    break;
                }
            }
            // right neighbor at i+2
            if (i + 2 < n) {
                int mn = a[i+2] - 1;
                int mx = a[i+2] + 1;
                if (max(L, mn) <= min(R, mx)) {
                    one = true;
                    break;
                }
            }
        }

        if (one) {
            cout << 1 << "\n";
        } else {
            cout << -1 << "\n";
        }
    }

    return 0;
}

Explanation:

Check for 0 operations: We scan adjacent pairs in the original array. If any pair differs by at most 1, the array is already beautiful, so the answer is 0.
Check for 1 operation: If not already beautiful, we simulate the effect of one merge on every adjacent pair (i, i+1):
- Merging replaces a[i] and a[i+1] by some x in the interval [L, R], where L = min(a[i], a[i+1]) and R = max(a[i], a[i+1]).
- The only new adjacencies that could become “beautiful” involve x and its neighbors: either (a[i-1], x) or (x, a[i+2]).
- For each neighbor, we check whether the interval [L, R] intersects [neighbor−1, neighbor+1]. If it does, we can pick an x in that intersection to ensure the difference is at most 1, making the resulting array beautiful in one operation.
Otherwise: If neither check succeeds, it’s impossible to make the array beautiful (any further merges will reduce the array below length 2 or cannot produce a suitable adjacent pair), so we print -1.

This runs in $O(n)$ per test case, comfortably within the limits for $n\le1000$ and up to 200 test cases.

give solution in cpp B. Shrinking Array time limi...

प्रश्न

विचार

Breaking down solution

Optimizing with merging

Optimizing with merge conditions

उत्तर

इस प्रश्नोत्तर को साझा करें