PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: ayu_19
Testers: nishant403, satyam_343
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Finding next/previous greater element
PROBLEM:
You have an array A. The beauty of a subarray is the difference between its largest and second largest element.
Find the number of distinct beauties across all subarrays.
EXPLANATION
We only really care about the maximum and second maximum element of the subarray, so let’s fix one of them and try to find valid values for the other one.
In particular, let’s fix the second maximum of the subarray.
Let’s say that we want a subarrays where A_i is the second maximum.
For this, the subarray should definitely contain A_i, and it should certainly contain something else larger than (or at least, equal to) A_i as well.
In particular,
- Let j \lt i be the highest index such that A_j \geq A_i.
- Let k \gt i be the lowest index such that A_k \geq A_i.
Then our subarray should contain at least one of A_j and A_k (giving beauties of A_j - A_i and A_k - A_i, respectively)
In fact, these two are the only beauty values we need to care about with A_i being the second maximum!
Proof
Let’s consider a few cases:
- Suppose the subarray contains both A_j and A_k. Then, these two elements are \geq A_i, so at the very least we can ensure that A_i won’t be picked as the second maximum; and such a subarray will be taken care of when considering something else as second maximum.
- Suppose the subarray contains A_j but not A_k. Then, if A_i is the second maximum, the beauty obtained is A_j - A_i (which we do consider); and if A_i is not the second maximum this subarray will be considered when something else is chosen as second maximum.
- The same analysis applies for when it contains A_k but not A_j.
So, we have a total of (at most) 2N possible beauties, if we can compute them all quickly enough then counting the number of distinct ones is trivial: for example, put them all in a set
and find the size of the set.
Notice that all we really need to be able to do is compute the j and k mentioned above quickly enough, for a given i.
Let’s focus on computing j first; the exact same method can be used to find k.
This is a rather classical problem, often called the “previous greater element” problem; and we can find it for every i from 1 to N in \mathcal{O}(N) time total using a stack.
How?
Let \text{prev}[i] be the value of j we’re looking for.
Keep a stack S, initially empty. Then, do the following:
- Iterate i from 1 to N.
- For a fixed i,
- While S is not empty, if A_i \gt A_{S.top}, pop the stack
- Then, if S is empty set \text{prev}[i] = -1; otherwise set \text{prev}[i] = S.top
- Finally, push i onto the stack
The idea is that S will always contain a sorted list of elements (decreasing in value from bottom to top).
When adding a new element, remove things less than whatever is being added; then the first element on the stack is the nearest greater element.
Since each index is pushed once and popped at most once, this entire algorithm runs in \mathcal{O}(N) time.
You can also read about this method here.
Use the above method to compute the next and previous greater elements for each i, then find all 2N candidates and count the number of distinct elements among them.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Setter's code (C++)
#include "bits/stdc++.h"
// #include "testlib.h"
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<class T> using oset = tree<T,null_type,less_equal// for indexed_multiset */
// <T> ,rb_tree_tag,tree_order_statistics_node_update> ; // order_of_key (k) -> # of elem strictly < k .
// // *(s.find_by_order(k)) -> element at index K .
#define int long long int
using ll= long long;
#define ld long double
#define endl '\n'
#define dbg(x) cout<<#x<<" is -> "<<x<<endl
#define speed_ ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define pb push_back
#define po pop_back
#define mp make_pair
#define sab(x) x.begin(),x.end()
#define rsab(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define sp(x) fixed<<setprecision(x)
#define uni(edge) edge.erase(unique(edge.begin(),edge.end()),edge.end());
#define to_up(x) transform(sab(x),x.begin(),::toupper)
#define to_low(x) transform(x.begin(),x.end(),x.begin(),::tolower)
#define ONLINE_JUDGE
// const int M = 1000000007;
// const int MM = 998244353;
// const ld Pi= acos(-1);
// const int N=1e5+10;
// const int inf=1e18;
// const int MAXX=1e9;
vector<int>v;
int t;
int test_count=0;
void simp(){
// dp?, graph?, bs on answer?, compress/sort queries/array?, stupid observation?
test_count++;
int n;
cin>>n;
v.resize(n);
set<int>s;
stack<int>st1;
for(int i=0;i<n;i++){
cin>>v[i];
}
for(int i=0;i<n;i++){
while(st1.size() && st1.top()<=v[i]){
int curr=st1.top();
s.insert(v[i]-curr);
st1.pop();
}
st1.push(v[i]);
}
while(sz(st1)){
st1.pop();
}
reverse(sab(v));
for(int i=0;i<n;i++){
while(st1.size() && st1.top()<=v[i]){
int curr=st1.top();
s.insert(v[i]-curr);
st1.pop();
}
st1.push(v[i]);
}
int ans=sz(s);
cout<<ans;
if(test_count!=t){
cout<<endl;
}
}
signed main(){
speed_;// remove this in interactive problems
// freopen("ouput05.txt", "r", stdin);
// freopen("input05.txt", "w", stdout);
// int t;
t=1;
cin>>t;
// initialize();
// solve();
//gen_factorial(N+10);
int curr=1;
for(int i=0;i<t;i++){
#ifndef ONLINE_JUDGE
#endif
// cout<<"Case #"<<curr++<<": ";
simp();
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
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;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
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,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
#define int long long
const int MAX_T = 1e4;
const int MAX_N = 2e5;
const int MAX_SUM_N = 2e5;
const int MAX_VAL = 1e9;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_n = 0;
int max_n = 0;
int max_ans = 0;
int sum_dist = 0;
void solve()
{
int n;
n = readIntLn(2,MAX_N);
max_n = max(max_n, n);
sum_n += n;
assert(sum_n <= MAX_SUM_N);
int a[n];
for(int i=0;i<n;i++) {
if(i != n - 1) {
a[i] = readIntSp(1 , MAX_VAL);
} else {
a[i] = readIntLn(1 , MAX_VAL);
}
}
//observation : an array index can occur as second maximum element
//only twice , with first greater or equal element to left and to right
vector<int> nge(n, n),pge(n, - 1);
vector<int> st;
for(int i=0;i<n;i++) {
while(!st.empty() && a[st.back()] <= a[i]) {
nge[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
st.clear();
for(int i=n-1;i>=0;i--) {
while(!st.empty() && a[st.back()] <= a[i]) {
pge[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
set<int> vals;
for(int i=0;i<n;i++) {
if(nge[i] != n) vals.insert(a[nge[i]] - a[i]) , sum_dist += (nge[i] - i);
if(pge[i] != -1) vals.insert(a[pge[i]] - a[i]) , sum_dist += (i - pge[i]);
}
int ans = vals.size();
max_ans = max(max_ans , ans);
cout << ans << '\n';
}
signed main()
{
int t = 1;
t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths A : " << sum_n << '\n';
cerr<<"Maximum length A : " << max_n << '\n';
cerr<<"Maximum answer : " << max_ans << '\n';
cerr<<"Sum of distance : "<< sum_dist << '\n';
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
stack = []
prev_big = [-1]*n
next_big = [-1]*n
for i in range(n):
while len(stack) > 0:
if a[stack[-1]] < a[i]: stack.pop()
else: break
if len(stack) > 0: prev_big[i] = stack[-1]
stack.append(i)
stack = []
for i in reversed(range(n)):
while len(stack) > 0:
if a[stack[-1]] < a[i]: stack.pop()
else: break
if len(stack) > 0: next_big[i] = stack[-1]
stack.append(i)
difs = set()
for i in range(n):
if prev_big[i] != -1: difs.add(a[prev_big[i]] - a[i])
if next_big[i] != -1: difs.add(a[next_big[i]] - a[i])
print(len(difs))