PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Satyam
Tester: Nishank Suresh, Abhinav sharma
Editorialist: Devendra Singh
DIFFICULTY:
1233
PREREQUISITES:
None
PROBLEM:
Stack has an array A of length N.
Now Stack tells Chef that he has made an array B of length N such that
- For all i(1 \leq i \leq N), B_i=max(A_1,A_2,..,A_i) or B_i=min(A_1,A_2,..,A_i)
Chef does not trust Stack.
So for a given B, Chef wants to check that whether there exists an array A from which B can be obtained.
Chef is slightly busy. So he needs your help. Can you help him?
EXPLANATION:
Let lastmin=min(B_1,B_2,..,B_{i-1}) and lastmax=max(B_1,B_2,..,B_{i-1}). Now if B_i \geq lastmax assign lastmax=B_i otherwise if B_i \leq lastmin assign lastmin=B_i. If both of these conditions are untrue, no valid array A exists.
Proof that if both of these conditions are untrue, no valid array A exists.
Suppose L=min(B_1,B_2,..,B_i) and R=max(B_1,B_2,..,B_i). Let us represent them by the segment [L, R]. All the values in A till index i lie between these 2 values. If for the index i+1 the maximum operation was done, B_{i+1}=max(A_1,A_2,..,A_{i+1}) then this operation can result in values from [R,INF]. If for the index i+1 the minimum operation was done , B_{i+1}=min(A_1,A_2,..,A_{i+1}) then this operation can result in values from [-INF,L]. Thus if for any index i+1 we get a value in the segment [L+1,R-1], where L are R are defined above, no valid array A exists for that case.
Construction of array in case the conditions are satisfied: Assign array A=B. For any index if we have B_i\geq lastmax, we can assume that the maximum value till A_i was taken otherwise the minimum value till A_i was taken. These value would be same as values of array B
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's solution
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define all(v) v.begin(),v.end()
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using muloset=tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=500500;
void solve(){
ll n; cin>>n;
vector<ll> a(n+5);
for(ll i=1;i<=n;i++){
cin>>a[i];
}
ll nax=0,nin=INF_ADD;
for(ll i=1;i<=n;i++){
nax=max(nax,a[i]);
nin=min(nin,a[i]);
if((nax!=a[i])&&(nin!=a[i])){
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(15);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, lastmin, lastmax;
cin >> n;
vll v(n);
bool flag = true;
for (int i = 0; i < n; i++)
cin >> v[i];
lastmax = lastmin = v[0];
for (int i = 1; i < n; i++)
{
if (v[i] >= lastmax)
lastmax = v[i];
else if (v[i] <= lastmin)
lastmin = v[i];
else
flag = false;
}
if (flag)
cout << "YES\n";
else
cout << "NO\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}