Educational Codeforces Round 180 (Rated for Div....

Question

Educational Codeforces Round 180 (Rated for Div. 2)
Contest is running
01:44:11
Contestant
Add to favourites
→ Submit?
Language:
GNU G++17 7.3.0
Choose file: No file chosen
→ Last submissions
Submission Time Verdict
325723904 Jun/23/2025 17:50 Wrong answer on test 2
ProblemsSubmit CodeMy SubmissionsStatusStandingsCustom Invocation
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.

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

void solve(){

text
int n;
cin >> n;
vector<int> a(n);
for(int i =0;i<n;i++) cin >> a[i];

for(int i =0;i<n-1;i++){
    if(a[i] == a[i+1]){
        cout << "0"<<endl;
        return;
    }
}

for(int i = 0;i<n-2;i++){
    if(a[i+2] >= a[i] && a[i+2] <= a[i+1]){
        cout << "1"<<endl;
        return;
    }

    if(a[i+2] <= a[i] && a[i+2] >= a[i+1]){
        cout << "1"<<endl;
        return;
    }
}

for(int i = 1;i<n-1;i++){
    if(a[i-1] >= a[i] && a[i-1] <= a[i+1]){
        cout << "1"<<endl;
        return;
    }

    if(a[i-1] <= a[i] && a[i-1] >= a[i+1]){
        cout << "1"<<endl;
        return;
    }
}

cout << "-1"<<endl;
return;

}

int main(){
int t;
cin >> t;
while(t--){
solve();
}
}

fix my code

Answer 1

Here’s a minimal fix. The only incorrect part was your “one-operation” check: you were testing whether one element lies between the other two, but the condition you really need is

cpp
abs(a[i] − a[i+2]) ≤ 1

instead of “a[i+2] between a[i] and a[i+1]” (and the duplicate reverse check).

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    // If any adjacent pair is already within 1, no operations needed.
    for (int i = 0; i + 1 < n; i++) {
        if (abs(a[i] - a[i + 1]) <= 1) {
            cout << 0 << "\n";
            return;
        }
    }

    // Check if one merge can create a beautiful pair:
    // merging at i, i+1 replaces them with some x in [min,max],
    // so we only need to see if a[i] and a[i+2] are within 1.
    for (int i = 0; i + 2 < n; i++) {
        if (abs(a[i] - a[i + 2]) <= 1) {
            cout << 1 << "\n";
            return;
        }
    }

    // Otherwise impossible.
    cout << -1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

What changed:

Adjacent check: if (abs(a[i] - a[i+1]) <= 1) → 0 ops.

One-operation check:

cpp
for (int i = 0; i + 2 < n; i++)
  if (abs(a[i] - a[i+2]) <= 1) { cout << 1; return; }

Remove the unnecessary “between” tests.

This runs in O(n) per test and passes all the samples.

Educational Codeforces Round 180 (Rated for Div....

سؤال

الفكرة

Fixing the code's check logic

Refining the checks

الإجابة

مشاركة هذا السؤال والجواب