PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: rakibjoy
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given two arrays B and C of length N, and an integer D.
Find any array A such that:
- B_i = \max(A_1, A_2, \ldots, A_i) for every i.
- C_i = \min(A_1, A_2, \ldots, A_i) for every i.
- |A_i - A_{i-1}| \leq D for every 1 \leq i \lt N.
EXPLANATION:
We start off by making a few observations:
- B is the sequence of prefix maximums of A, and so must be non-decreasing.
- C is the sequence of prefix minimums, and so must be non-increasing.
- B_1 = C_1 = A_1 should hold.
If any of the above three conditions fail to hold, no A can exist. - If B_i \gt B_{i-1}, then A_i = B_i should hold, since the prefix maximum increases at this position.
- Similarly, if C_i \lt C_{i-1}, A_i = C_i should hold.
In particular, if both conditions above hold for the same index, no solution can exist, since it’s not possible for both the prefix maximum and minimum to change simultaneously.
This gives us several constraints on A.
Any index affected by one of the latter two conditions has its value fixed - we just need to figure out whether there’s a way to fill the remaining places while remaining consistent.
Let i and j (i \lt j) be two “fixed” indices, such that there’s no other fixed index between them.
A_i and A_j are fixed ,so we’ll try to fill in the values A_{i+1}, A_{i+2}, \ldots, A_{j-1}.
There are some cases to consider here:
- Suppose A_i and A_j are both prefix maximums.
Then, none of the middle elements are allowed to exceed A_i, so the best we can do is to set them all to A_i.
In this case, if A_i+D \lt A_j, no solution exists because we can’t jump by more than D. - Similarly, if both are prefix minimums we can set everything to A_i; unless A_i-D \gt A_j in which case no solution exists.
- Next, suppose A_i is a maximum but A_j is a minimum.
Let M denote the minimum before A_j.
We must go from A_i to A_j using steps of at most D, while ensuring we don’t use anything smaller than M till we reach A_j.
The best we can do is to thus use A_i-D, A_i-2D, A_i-3D, \ldots till we reach M, then make everything following that, M.
That is, set A_k := \max(M, A_i - D\cdot (k-i)) for each i \lt k \lt j.
If, after this A_{j-1}-D \gt A_j still holds, no solution can exist. - Similarly, if A_i is a minimum and A_j is a maximum, we can increase in steps of D starting from A_i while making sure not to cross the previous maximum.
Finally, if L is the last fixed index, set A_i := A_L for every i\gt L to ensure that nothing breaks.
If all the gaps were filled correctly, the array A we found is an answer; otherwise no answer exists.
The complexity of this is \mathcal{O}(N) if implemented properly, since each element is part of at most one gap between consecutive fixed elements.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
//starting with the name of almighty ALLAH
// Practice is the only shortcut to improve
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define vc vector
#define vi vc<int>
#define vl vc<ll>
#define mp(x,y) make_pair(x,y)
#define yes cout<<"YES"<<'\n';
#define no cout<<"NO"<<'\n';
#define tst int t;cin>>t;while(t--)
#define srt(v) sort(v.begin(),v.end());
#define rsrt(v) sort(v.rbegin(),v.rend());
#define rj ios::sync_with_stdio(false);cin.tie(0);
#define rvs(v) reverse(v.begin(),v.end());
#define F first
#define S second
#define MOD 1000000007
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define PI 2*acos(0.0)
#define pii pair<int,int>
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define coutv(v) for(auto it:v)cout<<it<<' ';cout<<endl;
#define cinv(v) for(auto &it:v)cin>>it;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ld long double
#define nl '\n'
const int N = 5e6;
using namespace std;
/* #ifndef ONLINE_JUDGE
#include "algo/debug.h"
#else
#define dbg(x...)
#endif */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int l, int r)
{
return uniform_int_distribution<int>(l, r) (rng);
}
int sot = 0;
void solve()
{
int n, d; //array size and max diference
cin >> n >> d;
sot += n;
assert(n >= 1 and n <= 500000);
assert(d >= 0 and d <= 1000000000);
vector<int>b(n), c(n), a(n);
queue<int>imp;//will store important elements here
for (int i = 0; i < n; i++)
{
cin >> b[i];
assert(b[i] >= -1000000000 and b[i] <= 1000000000);
}
for (int i = 0; i < n; i++)
{
cin >> c[i];
assert(c[i] >= -1000000000 and c[i] <= 1000000000);
}
if (b[0] != c[0])
{
cout << "NO" << endl;
return;
}
for (int i = 1; i < n; i++)
{
if (b[i] < b[i - 1] || c[i] > c[i - 1])
{
cout << "NO" << endl;
return;
}
if (b[i] != b[i - 1] && c[i] != c[i - 1])
{
cout << "NO" << endl;
return;
}
if (b[i] != b[i - 1])
{
imp.push(b[i]);
}
if (c[i] != c[i - 1])
{
imp.push(c[i]);
}
}
a[0] = b[0];
int cr = a[0];//current value
int mx = cr, mn = cr;
for (int i = 1; i < n; i++)
{
while (!imp.empty() && cr == imp.front())
{
imp.pop();
}
if (imp.empty())
{
a[i] = a[i - 1];
}
//else
{
int nxt = imp.front();
if (nxt >= cr)
{
nxt = min(nxt, b[i]); //maintaing the limit
int req = nxt - cr;//reqired change
req = min(req, d);//as we can change at most d
cr += req;
a[i] = cr;
}
else
{
nxt = max(nxt, c[i]);
int req = cr - nxt;
req = min(req, d);
cr -= req;
a[i] = cr;
}
}
mx = max(mx, a[i]);
mn = min(mn, a[i]);
//cheking if it is maintaining well
if (mx != b[i] || mn != c[i])
{
cout << "NO" << endl;
return;
}
}
cout << "YeS" << endl;
for (auto it : a) cout << it << ' ';
cout << endl;
}
int main()
{
/*#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE*/
rj
tst
//int t;cin>>t;fr(i,1,t) cout<<"Case "<<i<<": ",solve();
//ll t;scanf("%lld",&t);fr(i,1,t) printf("Case %lld: ",i),solve();
solve();
assert(sot <= 500000);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, d = map(int, input().split())
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a = [0]*n
a[0] = b[0]
prv = 0
for i in range(1, n):
if b[i] != b[i-1]:
a[i] = b[i]
for j in reversed(range(prv+1, i)):
a[j] = max(a[prv], a[j+1] - d)
prv = i
elif c[i] != c[i-1]:
a[i] = c[i]
for j in reversed(range(prv+1, i)):
a[j] = min(a[prv], a[j+1] + d)
prv = i
for i in range(prv+1, n): a[i] = a[prv]
pmax, pmin = a[:], a[:]
mxd = 0
for i in range(1, n):
pmax[i] = max(pmax[i], pmax[i-1])
pmin[i] = min(pmin[i], pmin[i-1])
mxd = max(mxd, abs(a[i] - a[i-1]))
if b == pmax and c == pmin and mxd <= d:
print('Yes')
print(*a)
else:
print('No')