B. Shrinking Array time limit per test2 seconds me...

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 |bi−bi+1|≤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(ai,ai+1)≤x≤max(ai,ai+1)
.
Remove the numbers ai
and ai+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≤t≤200
) — the number of test cases.

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

The second line contains n
integers a1,a2,…,an
(1≤ai≤106
) — 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 |a2−a3|=|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 a1
and a2
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 a2
and a3
and replace them with the number 3
. The resulting array [1,3,2]
is beautiful.

C++ code with no comments and varibels should be 2-3 characters long

Thought

Analyzing competitive programming problem
The user asked for a C++ solution for this "B. Shrinking Array" problem, with short variable names and no comments. The goal is to find the minimal number of operations needed to make the array beautiful, where the array is beautiful if there is at least one adjacent pair with a difference of 1 or less. I’ll focus on implementing an efficient algorithm to compute the minimum operations required. The logic will involve selecting adjacent pairs and reducing the array size to achieve the desired result.

Breaking down minimal operations
The goal is to find the minimal operations to make an array "beautiful" by getting at least one adjacent pair with a difference of 1 or less. Operations reduce the array's size by replacing adjacent elements with a value between them. If the array size is initially 2, it’s impossible if the difference is greater than 1. For larger arrays, we combine elements to reduce the range, checking step-by-step if we can create a pair with a difference ≤ 1 with the least operations.

Breaking down the approach
The goal is to make the array beautiful by ensuring an adjacent pair with a difference of 1 or less. Each operation merges two adjacent elements and results in a number between their original values. If the array is already beautiful, no operation is needed. Otherwise, we aim to merge segments to bring elements with differences greater than 1 closer together. In some cases, it may take several merges to adjust values effectively. For arrays where the length is 2, a large difference is impossible to resolve.

Thought for 1m 32s

Answer
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];
const int Mx=1e9;
int res=Mx;
unordered_map<int,int>mp;
for(int i=0;i<n;i++){
int v=a[i];
for(int d=-1;d<=1;d++){
auto it=mp.find(v+d);
if(it!=mp.end())res=min(res,i-it->second-1);
}
mp[v]=i;
}
cout<<(res==Mx?-1:res)<<"\n";
}
return 0;

}

reudce the time complixty and optimize it