logoChat01.ai

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

Criado em: 23 de junho de 2025

Respondido usando O4 Mini High por Chat01

Pergunta

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.

Pensamento

Breaking down solution

I need to implement the solution in C++ for the "Shrinking Array" problem. The goal is to reduce an array using operations until a "beautiful" array is formed (an adjacent pair where the absolute difference is <= 1), or report -1 if it's impossible.

I’ll first check if any adjacent pair already satisfies the condition. If not, the operations will step through adjacent pairs and attempt to merge elements until either a beautiful pair is found or the array becomes too small. If the length drops below 2, it's impossible.

Optimizing with merging

We want to minimize operations by merging pairs of elements until an adjacent pair with a difference of ≤1 is formed. The key insight is that merging two elements creates intermediate values closer to the neighbors. If any adjacent pair in the initial array already has a difference ≤1, the answer is 0. Otherwise, we attempt to merge pairs and check if the resulting array has any adjacent pair with the desired property. This approach reduces the problem size but still needs to be efficient, especially with the large input size.

Optimizing with merge conditions

The goal is to determine the minimum operations needed to form a "beautiful" array where adjacent elements have a difference of <=1. We merge adjacent pairs and check whether the resulting numbers create a beautiful pair. If no such pair exists initially, I merge elements and check the impact on adjacent values. We calculate the range of potential values and check for overlaps with adjacent values. This process helps determine whether 1 operation is sufficient or if it's impossible, with more extreme cases possibly requiring 2 operations.

Thought for 29 seconds

Resposta

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:

  1. 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.

  2. 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.

  3. 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)O(n) per test case, comfortably within the limits for n≤1000n\le1000 and up to 200 test cases.

Compartilhar esta Q&A