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:
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;
}
