SEDMAX - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Bhavyesh Desai
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Observation, Stack

PROBLEM:

You are given an array A of length N. Your task is to find out the number of different possible costs that can be obtained across all possible choices for the subarray.

The cost is calculated as follows:

  • A subarray B of size at least 2 will be chosen.
  • The cost will be calculated as the difference between the maximum and the second maximum element in the subarray B.

QUICK EXPLANATION:

  • An element A_i can act as a second maximum element for at most two elements of an array, say A_L and A_R.

  • A_L is the first greater (or equal) element on the left side of A_i, whereas A_R is the first greater (or equal) element on the right side of A_i in the array.

  • Find A_L and A_R for every element of an array, which can be done in a single traversal of an array using a stack.

  • Find out the difference for every pair of the maximum and second maximum elements.

  • Finally, output the number of unique differences possible.

EXPLANATION:

Subtask 1:

Here, \sum{N} overall cases is less than or equal to 5 \cdot 10^3

What really matters in the subarray is the maximum and the second maximum element. Suppose we have a subarray [A_L, A_{L+1},......, A_R] and the maximum element be max and the second maximum element is smax.

What happens when a new element A_{R+1} is added to this subarray?

Case 1: A_{R+1} is greater than than the maximum element max.

  • Since A_{R+1} is the maximum element in the new subarray hence max becomes equal to A_{R+1}. And the previous max will become smax as now the previous max will be the second maximum element of the new subarray.

Case 2: A_{R+1} is smaller than the maximum element max but greater than the second maximum element smax.

  • Now max is still the maximum element in the new subarray hence max will remain as it is. But smax will no longer remain the second maximum element as A_{R+1} > smax, hence smax becomes equal to A_{R+1}.

Case 2: A_{R+1} is smaller than both maximum element max and second maximum element smax.

  • In this case, the max and smax will remain as it is as they are still the maximum and the second maximum element of the new subarray respectively.

As every element of an array can be the starting point of the subarray except the last element of the subarray since the minimum length needs to be 2.

Hence taking every element as the starting point of the subarray and keep on adding the elements on this subarray till we reach the rightmost element of the array. Every time we add the element to the subarray, find the maximum and the second maximum element for this new subarray as explained in the cases above. Every time we calculate the difference between the maximum and the second maximum element. Finally, we output the number of unique differences possible.

Time Complexity

O(N^2) per test case

Solution
// Subtask 1
 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int mxN=1e5+5;
int a[mxN];
int n;
 
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin>>t;
 
  while(t--)
  {
    cin>>n;
 
    for(int i=1;i<=n;i++)
    {
      cin>>a[i];
    }
 
    set <int> ans;
 
    for(int i=1;i<n;i++)
    {
      int ma1=max(a[i],a[i+1]);
      int ma2=min(a[i],a[i+1]);
 
      ans.insert(ma1-ma2);
 
      for(int j=i+2;j<=n;j++)
      {
        if(a[j]>ma1)
        {
          ma2=ma1;
          ma1=a[j];
        }
        else if(a[j]>ma2)
        {
          ma2=a[j];
        }
 
        ans.insert(ma1-ma2);
      }
    }
 
    cout<<ans.size()<<"\n";
  }
 
return 0;
}

Subtask 2:

Since the value of N is large enough, we need to optimize our solution. As the only thing that matters in the problem is to find the pairs (x,y) such that x is the maximum element of the subarray and y is the second maximum element of the subarray. If we can find all the possible pairs then we can easily find the number of unique differences possible.

Claim: There can exist at most 2 pairs where an element A_i acts as a second maximum element. Those possible pairs are (A_L, A_i) and (A_R, A_i) where A_L is the first greater (or equal) element on the left side of A_i, whereas A_R is the first greater (or equal) element on the right side of A_i in the array.

Proof

Consider an array A of N numbers such that:

A_1,....A_L,A_{L+1},....,A_i,...,A_{R-1},A_R,....A_N

Now, Suppose for A_i, the next greater (or equal) element on the left side is A_L, and the next greater (or equal) element on the right side is A_R.

Initially, we have a subarray [A_i, A_{i+1}.., A_R] such that the maximum element is A_R and the second maximum element is A_i since max(A_i, A_{i+1}.., A_R)=A_R and max(A_i, A_{i+1}.., A_{R-1})=A_i.

Now let us try adding elements on this subarray as we were doing in subtask 1.

Case 1: When A_{R+1}>A_R

  • In this case, A_i will no longer remain the second maximum element as the A_{R+1} will be the maximum element of the new subarray and A_R will be the second maximum element.

Case 1: When A_{R+1}<A_R and A_{R+1}>A_i

  • In this case, A_i will no longer remain the second maximum element as the A_{R+1} will be the second maximum element of this new subarray since A_{R+1}>A_i.

Case 3: When A_{R+1}<A_R and A_{R+1}<A_i

  • In this case, there will be no changes i.e A_i will be the second maximum element and A_R will be the maximum element.

We can clearly see for all the cases when A_i is the second maximum element then only and only A_R is the maximum element and that happens in Case 3. For other cases, A_i no longer remains the second maximum element.

  • Similarly, we can prove for the left side i.e when we have a subarray [A_L, A_{L+1}.., A_i] such that the maximum element is A_L and the second maximum element is A_i. Now when we keep adding elements on the left side of this subarray similar cases appear.

  • For all the subarray that has staring index greater than L and ending index less than R, and containing A_i as the element of the subarray. In those cases, A_i will be the maximum element as max(A_{L+1},..., A_i.., A_{R-1})=A_i

  • For such subarray that contains both A_L and A_R, then as A_i is smaller than both A_L and A_R. Hence A_i won’t be acting as the second maximum element.

Hence there can exist at most 2 pairs where an element A_i acts as a second maximum element. Those possible pairs are (A_L, A_i) and (A_R, A_i) where A_L is the first greater (or equal) element on the left side of A_i, whereas A_R is the first greater (or equal) element on the right side of A_i in the array.

So, We are left with finding A_L and A_R for every element of an array, which can be done in a single traversal of an array using a stack as explained here

Finally, find out the difference for every pair of the maximum and second maximum elements and output the number of unique differences possible.

Time Complexity

O(N) per test case

TIME COMPLEXITY:

O(N) per test case.

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) ((int)x.size())
#define endl "\n"
#define inf (1LL<<62)
#define ninf (-inf)

template<typename Tleaf>
void print(Tleaf &&leaf, int n)
{
	for(int i = 1; i <= n; i++)
		cout << leaf[i] << " \n"[i==n];
}

template<typename Tleaf>
void print(Tleaf &&leaf, int n, int m)
{
	for(int i = 1; i <= n; i++)
		print(leaf[i], m);
}

const int nax = 100005;
int a[nax];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		for(int i = 1; i <= n; i++)
			cin >> a[i];
		set<int> s;
		stack<int> p;
		for(int i = 1; i <= n; i++)
		{
			while(sz(p) && p.top() <= a[i])
			{
				s.insert(a[i]-p.top());
				p.pop();
			}
			p.push(a[i]);
		}
		while(!p.empty())
			p.pop();
		reverse(a+1, a+n+1);
		for(int i = 1; i <= n; i++)
		{
			while(sz(p) && p.top() <= a[i])
			{
				s.insert(a[i]-p.top());
				p.pop();
			}
			p.push(a[i]);
		}
		cout << sz(s) << "\n";
	}
}
Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l, long long r, char endd) {
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true) {
		char g=getchar();
		if(g=='-') {
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g&&g<='9') {
			x*=10;
			x+=g-'0';
			if(cnt==0) {
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd) {
			if(is_neg) {
				x=-x;
			}
			assert(l<=x&&x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l, int r, char endd) {
	string ret="";
	int cnt=0;
	while(true) {
		char g=getchar();
		assert(g!=-1);
		if(g==endd) {
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt&&cnt<=r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
	return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
	return readString(l,r,' ');
}
 
int sum_n=0;
pii a[100005];
int le[100005],ri[100005];
int leg[100005],rig[100005];
void solve() {
	int n=readIntLn(2,100000);
	sum_n+=n;
	assert(sum_n<=1000'000);
	fr(i,1,n) {
		if(i!=n)
			a[i].fi=readIntSp(1,1000'000'000);
		else
			a[i].fi=readIntLn(1,1000'000'000);
		a[i].se=i;
	}
	set<pii> qu,qu1;
	fr(i,1,n) {
		while(qu1.size()&&(*qu1.begin())<a[i]) {
			rig[(*qu1.begin()).se]=i;
			qu1.erase(qu1.begin());
		}
		while(qu.size()&&(*qu.begin())<a[i]) {
			ri[(*qu.begin()).se]=i;
			qu1.insert(*qu.begin());
			qu.erase(qu.begin());
		}
		qu.insert(a[i]);
	}
	while(qu.size()) {
		ri[(*qu.begin()).se]=n+1;
		qu1.insert(*qu.begin());
		qu.erase(qu.begin());
	}
	while(qu1.size()) {
		rig[(*qu1.begin()).se]=n+1;
		qu1.erase(qu1.begin());
	}
	for(int i=n; i>0; i--) {
		while(qu1.size()&&(*qu1.begin())<a[i]) {
			leg[(*qu1.begin()).se]=i;
			qu1.erase(qu1.begin());
		}
		while(qu.size()&&(*qu.begin())<a[i]) {
			le[(*qu.begin()).se]=i;
			qu1.insert(*qu.begin());
			qu.erase(qu.begin());
		}
		qu.insert(a[i]);
	}
	while(qu.size()) {
		le[(*qu.begin()).se]=0;
		qu1.insert(*qu.begin());
		qu.erase(qu.begin());
	}
	while(qu1.size()) {
		leg[(*qu1.begin()).se]=0;
		qu1.erase(qu1.begin());
	}
	int ans=0;
	set<int> anser;
	fr(i,1,n) {
		if(le[i]!=0)
			anser.insert(a[le[i]].fi-a[i].fi);
		if(ri[i]!=n+1)
			anser.insert(a[ri[i]].fi-a[i].fi);
//		trace(le[i],leg[i],ri[i],rig[i]);
//		ans+=(ri[i]-le[i]-1)*a[i].fi;
//		trace(ans);
//		ans-=((rig[i]-ri[i])*(i-le[i])*a[i].fi);
//		ans-=((le[i]-leg[i])*(ri[i]-i)*a[i].fi);
//		ans-=a[i].fi;
//		trace(ans);
	}
	cout<<sz(anser)<<endl;
//	cout<<ans<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=readIntLn(1,100000);
//	int t;
//	cin>>t;
	fr(i,1,t)
		solve();
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
 
Editorialist
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int mxN=1e5+5;
int a[mxN];
int n;
int lft[mxN];
int rght[mxN];
 
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin>>t;
 
  while(t--)
  {
    cin>>n;
 
    for(int i=1;i<=n;i++)
    {
      cin>>a[i];
    }
 
    set <int> ans;
 
    stack <int> s;
 
    for(int i=1;i<=n;i++)
    {
      while(s.size()>0 && s.top()<a[i])
        s.pop();
 
      if(s.size()>0)
        lft[i]=s.top();
      else
        lft[i]=-1;
 
      s.push(a[i]);
    }
 
    while(s.size()>0)
      s.pop();
 
    for(int i=n;i>=1;i--)
    {
      while(s.size()>0 && s.top()<a[i])
        s.pop();
 
      if(s.size()>0)
        rght[i]=s.top();
      else
        rght[i]=-1;
 
      s.push(a[i]);
    }
 
    for(int i=1;i<=n;i++)
    {
      if(lft[i]!=-1)
        ans.insert(lft[i]-a[i]);
      if(rght[i]!=-1)
        ans.insert(rght[i]-a[i]);
    }
 
    cout<<ans.size()<<"\n";
  }
 
return 0;
}

VIDEO EDITORIAL:

8 Likes

Great solution by setter in O(N), an O(N log N) solution to the (almost) exact problem is unfortunately also available on GFG https://www.geeksforgeeks.org/find-all-unique-pairs-of-maximum-and-second-maximum-elements-over-all-sub-arrays-in-onlogn/

8 Likes

Now I understand how these many AC solutions for the problem in Div2.

11 Likes

ohhh this was the solution , i was thinking it seems a little bit standard :frowning:

lol :frowning:

2 Likes

Well if you look closely both the solution are almost same , the authors one and the GFG one , there also the Complexity is O(NlogN) only because of using set , using unordered set can get it down to O(N)

1 Like

I solved it using a constructive algo in O(NLOGN). Sort in descending the values along with their indexes and iterate this array to find the left and right greater elements incrementally. Here is my solution - Solution: 43170109 | CodeChef
I was astonished to see everyone using stack all other solutions!

6 Likes
#include <iostream>
#include <vector>
#include<stack>
#include<set>
#include<cmath>
using namespace std;
int main()
{int t;
    cin>>t;
    while(t--){
      int n;
      cin>>n;
      int a[n];
      for(int i=0;i<n;i++)
        {cin>>a[i];}
        stack<int>s;set<int>u;
        for(int i=0;i<n;i++){
            if(s.size()==0){
                s.push(a[i]);
            }
            else if(s.size()==1){
                u.insert(abs(s.top()-a[i]));
                s.push(a[i]);
            }
            else if(s.top()>=a[i])
            {
                u.insert(abs(s.top()-a[i]));
                s.push(a[i]);
            }
            else{
                while( s.size()>0 && s.top()<a[i]){
                        u.insert(abs(s.top()-a[i]));
                        s.pop();
                }
                if(s.size()>0)
                u.insert(abs(s.top()-a[i]));
                s.push(a[i]);
            }}
        cout<<(int)u.size()<<endl;}}

Can someone please help me figure out the flaw in this implementation? If possible, please provide a test case that would fail on this.

Will you please explain how you reached upto this conclusion …
Thanks in advance

1 Like

next level

I did exactly same.

@aniket_0206 The concept is basically the same (fixing the second max). You can sort descending order the values and iteratively fix the second max element. Meanwhile, you have an indices array of elements greater than the current element (because you are iterating descending thats possible, initially that array is empty). You can do a binary search and find the indices greater and smaller than the element in iteration and that would produce new diffs needed. Update the current element’s index in the indices array (in sorted order) and proceed for the next iteration.

explain with eg?

Tester is writing the shittiest code possible.

3 Likes

This is not a easy-medium level problem. It is at least medium level problem as we first have to observe that every element can be second maximum at most 2 times and then know the trick to find the two maximum elements of each element in O(N) time.

1 Like
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI 3.141592653589793238
typedef long long int ll;

using namespace std;

const ll N = 1e9+7;

ll nextgreater[100000+5]; 
ll previousgreater[100000+5]; 

void solve()
{
  memset(nextgreater,-1,sizeof(nextgreater)); 
  memset(previousgreater,-1,sizeof(previousgreater)); 
  ll n; 
  cin>>n; 

  vector<ll> v(n); 
  for(int i=0;i<n;i++){
    cin>>v[i]; 
  }

  stack<ll> selement;
  stack<ll> sindex;  
  for(int i=0;i<n;i++){
    if(selement.empty()){
      selement.push(v[i]); 
      sindex.push(i); 
    }
    else{
      if(v[i] > selement.top()){
        while(!selement.empty() && v[i] >= selement.top()){
          ll index = sindex.top(); 
          nextgreater[index] = v[i]; 
          selement.pop(); 
          sindex.pop(); 
        }
        selement.push(v[i]); 
        sindex.push(i); 
      }
      else{
        selement.push(v[i]); 
        sindex.push(i); 
      }
      
      
    }
  }
  while(!selement.empty()){
    selement.pop(); 
  }
  while(!sindex.empty()){
    sindex.pop(); 
  }


  for(int i=n-1;i>=0;i--){
    if(selement.empty()){
      selement.push(v[i]); 
      sindex.push(i); 
    }
    else{
      if(v[i] > selement.top()){
        while(!selement.empty() && v[i] >= selement.top()){
          ll index = sindex.top(); 
          previousgreater[index] = v[i]; 
          selement.pop(); 
          sindex.pop(); 
        }
        selement.push(v[i]); 
        sindex.push(i); 
      }
      else{
        selement.push(v[i]); 
        sindex.push(i); 
      }
      
      
    }
  }

  set<ll> ansset; 
  for(int i=0;i<n;i++){
    if(nextgreater[i] != -1){
      ansset.insert(nextgreater[i] - v[i]); 
    }
    if(previousgreater[i] != -1){
      ansset.insert(previousgreater[i] - v[i]); 
    }
  }

  cout<<ansset.size(); 
}




int main()
{
   fast;
   ll t;
   // t = 1;
   cin>>t;

   while(t--)
   {
       solve();
       cout<<endl;
   }

}

Can someone tell what is wrong in my solution plz

Consider

tc

2
1 1

1 Like
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI 3.141592653589793238
typedef long long int ll;

using namespace std;

const ll N = 1e9+7;

ll nextgreater[100000+5]; 
ll previousgreater[100000+5]; 

void solve()
{
  memset(nextgreater,-1,sizeof(nextgreater)); 
  memset(previousgreater,-1,sizeof(previousgreater)); 
  ll n; 
  cin>>n; 

  vector<ll> v(n); 
  for(int i=0;i<n;i++){
    cin>>v[i]; 
  }

  // cout<<"hello world"; line; 

  stack<ll> selement;
  stack<ll> sindex;  

  for(int i=0;i<n;i++){
    if((int)selement.size() == 0){
      selement.push(v[i]); 
      sindex.push(i); 
    }
    else{
      if(v[i] >= selement.top()){
        while((int)selement.size() > 0 && v[i] >= selement.top()){
          nextgreater[sindex.top()] = v[i]; 
          selement.pop(); 
          sindex.pop(); 
        }
     }

     selement.push(v[i]); 
     sindex.push(i); 
   }
  }

  // cout<<"next greater is done: "; line; 

  while((int)selement.size() > 0){
    selement.pop(); 
  }
  while((int)selement.size() > 0){
    sindex.pop(); 
  }

  // cout<<"made empty: "; line; 

  for(int i=n-1;i>=0;i--){
    if((int)selement.size() == 0){
      selement.push(v[i]); 
      sindex.push(i); 
    }
    else{
      if(v[i] >= selement.top()){
        while((int)selement.size() > 0 && v[i] >= selement.top()){
          previousgreater[sindex.top()] = v[i]; 
          selement.pop(); 
          sindex.pop(); 
        }
      }

      selement.push(v[i]); 
      sindex.push(i); 
      
    }
  }
  // cout<<"previous greater id one: ";line; 

  unordered_set<ll> ansset; 
  for(int i=0;i<n;i++){
    if(nextgreater[i] != -1){
      ansset.insert(nextgreater[i] - v[i]); 
    }
    if(previousgreater[i] != -1){
      ansset.insert(previousgreater[i] - v[i]); 
    }
  }

  cout<<ansset.size(); 
}




int main()
{
   fast;
   ll t;
   // t = 1;
   cin>>t;

   while(t--)
   {
       solve();
       cout<<endl;
   }

}

I have modified the soluntion just a bit
2
1 1
this test I’m getting ans 1

this is also getting TLE on some case in subtask 2, but the solution is almost identical to author’s solution

That’s what the correct solution supposed to get.

1 Like

Yes for the test case you suggested I’m getting correct ans for above solution , but after submitting it m getting TLE on 1 testcase of subtask 2