PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: helloLad
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have an array A.
You can choose some non-empty subsequence of it such that any pair of elements in the subsequence are non-adjacent; then choose some x\gt 0 and add x to all of them.
Is it possible to convert A to a sorted (in non-decreasing order) array by doing this at most once?
EXPLANATION:
If A is already sorted, nothing needs to be done and the answer is Yes.
Otherwise, there’ll exist some index i such that A_{i-1} \gt A_{i}.
For this index, notice that:
- For A to be sorted in the end, we must increase A_{i}.
However, A_{i-1} and A_{i+1} (if they exist) cannot be touched, since we can’t choose adjacent elements. - So, we must choose x such that A_i+x \geq A_{i-1}, and A_i+x \leq A_{i+1}.
- Notice that this gives you lower and upper bounds on x: A_{i-1} - A_i \leq x \leq A_{i+1} - A_i.
Call an index i bad if A_i \gt A_{i-1}.
Let L = \max(A_{i-1} - A_i) across all bad indices i, and R = \min(A_{i+1} - A_i) across all bad indices i.
Then,
- If L \leq R, the answer is
Yes: you can choose any x between L and R and increase the value at all bad indices by x, at which point the array A will be sorted.- Note that for our move to be valid, we need to ensure that no two bad indices are adjacent, so that we can choose all of them simultaneously.
However, if L \leq R is indeed true, you can show that no two bad indices can be adjacent — do you see why?
- Note that for our move to be valid, we need to ensure that no two bad indices are adjacent, so that we can choose all of them simultaneously.
- If L \gt R, the answer is
No, since no matter which x you choose, some inequality at a bad index will fail.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(x) (int)(x.size())
#define ll long long
#define fi first
#define se second
#define lbd lower_bound
#define ubd upper_bound
template <typename T>
using ordered_set = tree<T, null_type,
less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;
void solve() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
int pre = v[0], x = 0;
for (int i = 1; i < n; i++) {
pre = max(pre, v[i]);
x = max(x, pre - v[i]);
}
pre = v[0];
bool okay = true;
for (int i = 1; i < n; i++) {
if (!okay && v[i] < pre) {
cout << "No";
return;
} else if (v[i] < pre) {
okay = false;
v[i] += x;
} else {
okay = true;
}
pre = max(pre, v[i]);
}
cout << (is_sorted(v.begin(), v.end()) ? "Yes" : "No");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("input.in", "rt", stdin);
// freopen("output.out", "wt", stdout);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
cout << '\n';
}
return 0;
}
Tester's code (C++)
/*
* * * *** * *****
* * * * * * * *
* * * *** ***** *
* * * * * * * * *
* * * * * * **
*
* *
*****
* *
***** * *
_* *_
| * * * * | ***
|_* _ *_| * *
* * *
***** * **
* * ***
{===* *===}
* IS * ***
* IT * * *
* RATED?* *
* * * **
* * ***
* *
***** * *
* *
* *
* *
***
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()
const ll N = 2e5 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;
ll modinverse(ll a) {
ll m = mod, y = 0, x = 1;
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += mod;
return x;
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
ll product = 1;
a %= md;
while (b) {
if (b & 1) product = (product * a) % md;
a = (a * a) % md;
b /= 2;
}
return product % md;
}
void panipuri() {
ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
string s;
bool ch = true;
cin >> n;
vl a(n);
forl(i, 0, n) {
cin >> a[i];
}
vl v;
forl(i,0,n-1){
if(a[i]>a[i+1]) v.pub(i+1);
}
m=v.size();
forl(i,0,m-1){
if(a[v[i]]>a[v[i+1]]){
yesno(0);
return;
}
}
a.pub(2e9);
ll m1=0;
forl(i,0,m){
m1=max(m1,a[v[i]-1]-a[v[i]]);
}
ll m2=1e9;
forl(i,0,m){
m2=min(m2,a[v[i]+1]-a[v[i]]);
}
yesno(m1<=m2);
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int laddu = 1;
cin >> laddu;
forl(i, 1, laddu + 1) {
// cout << "Case #" << i << ": ";
panipuri();
cout << '\n';
}
}
Editorialist's code (Python)
def solve(a):
a = [0] + a + [10**10]
lo, hi = 0, 10**10
flag = 0
for i in range(1, len(a)):
if flag == 0:
if a[i] < a[i-1]:
flag = 1
lo = max(lo, a[i-1] - a[i])
else:
if a[i] < a[i-2]:
return 'No'
flag = 0
hi = min(hi, a[i] - a[i-1])
if lo <= hi: return 'Yes'
return 'No'
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print(solve(a))