MINORMAX-Editorial

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();
}

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner s = new Scanner(System.in);
int t=s.nextInt();
for(int i=0;i<t;i++){
int n=s.nextInt();
int max=s.nextInt();
int min=max;
int f=0;
for(int j=0;j<n-1;j++){
int a=s.nextInt();
if(a<max && a>min){
f=1;
break;
}
if(a>max){
max=a;
}
if(a<min){
min=a;
}
}
if(f==1)
System.out.println(“NO”);
else
System.out.println(“YES”);
}
}
}

Why this solution is not working?

2 Likes

Is my solution(Given Below) Good?

#include

#include<bits/stdc++.h>

using namespace std;

int main(){

int t;

cin >> t;

while(t–)

{

int n;

cin >> n;

int b[n];

for (int i = 0; i < n; i++)

{

    cin >> b[i];

}

bool asc_sorted = true;

for (int i = 0; i < n-1; i++)

{

    if(b[i] > b[i+1]){

        asc_sorted = false;

        break;

    }

}

if(asc_sorted){

    cout << "YES" << endl;

}

else{

    bool dec_sorted = true;

    for (int i = 0; i < n-1; i++)

    {

        if(b[i] < b[i+1]){

            dec_sorted = false;

            break;

        }

    }

    if(dec_sorted){

        cout << "YES" << endl;

    }

    else{

        int a[n];

        a[0] = b[0];

        int max_till_i = a[0];

        int min_till_i = a[0];

        bool flag = true;

        for (int i = 1; i < n; i++)

        {

            if(b[i] <= min_till_i || b[i] >= max_till_i){

                max_till_i = max(b[i], max_till_i);

                min_till_i = min(b[i], min_till_i);

            }

            else{

                flag = false;

                break;

            }

            cout << max_till_i << " " << min_till_i << " ";

                           

        }

        cout << endl;

        if(flag){

            cout << "YES" << endl;

        }

        else{

            cout << "NO" << endl;

        }

       

    }

}

}

return 0;

}

Can anyone help why my code is not working.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n];
        int mini=INT_MAX,maxi=INT_MIN;
        bool flag=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            mini = min(mini,a[i]);
            maxi = max(maxi,a[i]);
            if((a[i]!=mini) && (a[i]!=maxi)){
                cout<<"NO"<<endl;
                flag=1;
                break;
            }
        }
        if(!flag) cout<<"YES"<<endl;
        
    }
}

Passing for sample cases but failing for overall.

You have to be careful on the boundary.

Hi, there is ambiguity in question making a bit, at least according to me, instead of " For all i", it should have been " For each I" this simple difference can lead to different codes. Overall the contest was good. Cheers !!