PROBLEM LINK:
Author: Teja Vardhan Reddy
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia
DIFFICULTY:
Medium
PREREQUISITeES:
Difference Array, Expected Value, Prefix Sums, Next Greater Element, Rotation Trick.
PROBLEM:
Given a circular array, find the expected value of the maximum element present in every subarray of length K. Find this for all lengths 1 to N.
HINTS:
Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, go back to solving the problem.
Hint 1:
Try to solve the problem for a linear array.
Hint 2:
Each element of the array will contribute towards the expected values of subarrays of certain lengths.
Consider the sequence:
7,2,1,2,6,5,3,5,1,4,10
Let’s look at the contributions of 6.
What is the leftmost element which can be included in a subarray of which 6 is the maximum element? Which is the rightmost one?
How will you find these for every element of the array?
Hint 3:
Consider the same sequence:
7,2,1,2,6,5,3,5,1,4,10
Again, look at the contributions of 6.
Consider the subarrays of the following lengths, which has 6 as its contributor.
How many subarrays of length 1 does 6 contribute towards? Length 2? 3?
\ldots 9? Can you see some pattern? Try to come up with examples and observe the pattern.
Hint 4:
Make the array circular: a[i+N]=a[i]
First solve the problem for the original array, and then the circular one. How will you obtain the answer from these? Try to see which parts are being counted multiple times, and which are not.
QUICK EXPLANATION:
show
Find the previous greater or equal and next greater element for every element of the array. Calculate each element’s contribution by computing the contribution of the increasing, constant, and decreasing parts. Combine them to get the result. Get the result for the original array, and then for the circular array, and subtract the result of the original array from the circular one, to get the answer.
EXPLANATION
show
Let’s first understand how to solve the problem for a linear array. Later, we’ll extend this solution to solve it for a circular array.
For every K, Chef will choose K contiguous jars uniformly randomly. He will only buy the jar which has candies with maximum sweetness, every time he chooses any K contiguous jars. We want to know the expected value of sweetness, for every K, multiplied by N.
F_K = S_K*N
We need to compute this F_K for every K, from 1 to N, where S_K is the expected value for a sequence of length K.
You can read about expected value here. Let’s look at the sample case given in the question, to understand how F_K is being computed.
show
Sample case:
1, 2, 3, 4
F_K = S_K*N
When K=1,
Possible sequences that Chef can choose:
(1), (2), (3), (4).
Expected value:
\frac{1+2+3+4}{4}*4=10
When K=2,
Possible sequences that Chef can choose:
(1,2), (2,3), (3,4), (4,1).
Expected value:
\frac{2+3+4+4}{4}*4=13
When K=3,
Possible sequences that Chef can choose:
(1,2,3), (2,3,4), (3,4,1), (4,1,2).
Expected value:
\frac{3+4+4+4}{4}*4=15
When K=4,
There is only 1 sequence which Chef can choose:
(1,2,3,4).
Expected value:
\frac{4}{1}*4=16
Every element will have some contribution towards the expected values of different lengths K. How do we find which K's a particular array element is contributing towards?
For every subarray of length K, Chef will choose the jar with the maximum sweetness. For which subarrays will a particular element be the maximum of that subarray?
show
Consider the following sequence:
15, 9, 7, 10, 2, 3, 2, 6, 3, 1, 5, 4, 8,7.
For which subarrays will 6 be the maximum element?
The nearest element to the left of 6 which is greater than 6, is 10. As soon as a subarray, which has 6, also has 10, 6 will no longer be the maximum value in the subarray. Similarly, 8 is the nearest element to the right of 6, which is greater than it.
So, the subarrays which have 6 as the maximum element, should begin at or before 6, but after 10, and should end at or after 6, but before 8.
Thus, for each element, the subarrays whose expected values it contributes to, will begin after the first element to its left greater than it, and end before the first element towards its right, greater than it.
However, a subarray may contain more than one instance of the max element.
As an example, consider the sequence:
10,15,4,6,3,5,6,8,7
If we count the contribution of the first 6 here, it’s subarrays will start after 15, include it, and end before 8. Similarly for the second 6, it’s subarrays will also start after 15, include it, and end before 8. Thus, there will be some subarrays, for which the contribution of the max element 6 will be counted twice. To avoid it, for each element we’ll take one of the end limits it’s subarrays as the nearest element greater than or equal to it, while the other end limit as the nearest element greater than it. This way, we’ll avoid counting the contribution of the max element in a subarray more than once. In the above example, we’ll consider the nearest element \ge 6 as the left limit, and the nearest element >6 as the right limit. This way, the first 6 will have subarrays between 15 and 8, while the second 6 will have subarrays between the first 6 and 8.
Thus, for each element, if we know the nearest element greater than or equal to it, towards its left, and the nearest element greater than it, towards its right, we shall know which subarrays’ expected values it contributes to. The nearest element greater than (or equal to) for each element can be computed easily using a stack, as explained here.
Now that we know which subarrays a particular element will contribute to, how do we efficiently calculate the contributions?
Let the maximum number of elements to the left of A_i, including A_i, in the subarrays that A_i will contribute to, be l. Similarly, let the maximum number of elements to the right of A_i, including A_i, in the subarrays that A_i contributes to, be r.
Either (A_{i-l} \ge A_i) or (i-l<0), and
Either (A_i<A_{i+r}) or (i+r=N)
The smallest length subarray which A_i will contribute towards is a subarray of length 1, i.e., A_i itself, while the largest one is the subarray of length (l+r-1), i.e., the subarray having all elements from A_{i-l+1} to A_{i+r-1}. For our purpose, we’ll assume that l \le r. We’ll swap the values of l and r if l>r. This swapping won’t affect our calculations.
Let’s break these down into three categories of subarrays:
- Those with lengths from 1 to l
- Those with lengths from (l+1) to r, and
- Those with lengths from (r+1) to (r+l-1).
Consider the following sequence:
7,2,1,2,6,5,3,5,1,4,10
Let’s calculate the contributions of 6 in the above sequence. Here, l=4, and r=6.
Let’s look at the subarrays in category 1: (1 \le K \le l)
There is 1 subarray of length 1: (6),
There are 2 subarrays of length 2: (2,6) and (6,5).
There are 3 subarrays of length 3: (1,2,6), (2,6,5) and (6,5,3)
There are 4 subarrays of length 4: (2,1,2,6), (1,2,6,5), (2,6,5,3) and (6,5,3,5)
We see that for subarrays of category 1, we get a linear increasing function.
A_i will contribute K times to a subarray of size K, of this category.
Let’s look at the subarrays in category 2: (l+1 \le K \le r)
There are 4 subarrays of length 5: (2,1,2,6,5), (1,2,6,5,3), (2,6,5,3,5) and (6,5,3,5,1).
There are 4 subarrays of length 6: (2,1,2,6,5,3), (1,2,6,5,3,5), (2,6,5,3,5,1) and (6,5,3,5,1,4).
Thus, for the subarrays of category 2, we get a constant function.
A_i will contribute l times to every subarray of this category.
Let’s look at the subarrays in category 3: (r+1 \le K \le r+l-1)
There are 3 subarrays of length 7: (2,1,2,6,5,3,5), (1,2,6,5,3,5,1), and (2,6,5,3,5,1,4).
There are 2 subarrays of length 8: (2,1,2,6,5,3,5,1), and (1,2,6,5,3,5,1,4).
There is 1 subarray of length 9: (2,1,2,6,5,3,5,1,4).
We see that for subarrays of category 3, we get a linear decreasing function.
A_i will contribute ((r+l) -K) times to a subarray of size K, of this category.
In category 1, a subarray of length K will have A_i as its maximum element K times. So, update the solution array from indices (1 \le K \le l) with A_i*K, respectively.
In category 2, the subarrays will have A_i as their maximum element l times.
So, update the solution array from indices (l+1 \le K \le r) with A_i*l.
In category 3, the subarrays will have A_i as their maximum element ((r+l) -K) times. So, update the solution array from indices (r+1 \le K \le r+l-1) with A_i* ((r+l) -K), respectively.
Let’s maintain three arrays, which will store the coefficients of the three functions:
increasing, constant and decreasing.
Updates to solution array for subarrays of category 2 is easy: we can simply perform a range update using any suitable data structure, like segment tree, as they involved updating the whole range with the same value. So, we’ll update the constant array with A_i*l, from indices l+1 to r.
But how will we perform the updates for subarrays of categories 1 and 3, as they involve updates of different values for different length subarrays (A_i*K and A_i* ((r+l) -K) for a subarray of length K, for categories 1 and 3, respectively)?
To do this, we’ll take advantage of the fact that they are linear increasing and decreasing functions.
For the increasing function, we’ll update increasing array from 1 to l with A_i. increasing_K needs to be multiplied by K. We can do this later, after increasing has been updated for every A_i, as (A_i*K+A_j*K) is the same as (A_i+A_j) *K.
For the decreasing function, notice that A_i* ((r+l) -K) is the same as -A_i*K+A_i*(r+l). So, we’ll update the constant array from indices r+1 to r+l-1 with A_i*(r+l), and then the decreasing array with -A_i. Later, just like the increasing array, the decreasing_K too can be multiplied with K, and this, combined with the constant array with produce A_i* ((r+l) -K) for every K.
The solution array will be:
ans[i]= (increasing[i]+decreasing[i]) *i+constant[i].
Range updates can be made using any suitable data-structure. We used a difference array in our implementation, as it is fast and easy to implement, and we only needed the actual array values after all the updates had been made.
Thus, this way, we can get the answer for a linear array.
For a circular array, we just need to extend the above solution.
First, we shall extend the original array, to make it function like a circular array:
For all 1 \le i \le N:
a[i+N]=a[i]
Using this, we can get all the rotations of the array easily. The original array is from indices 1 to N. After a single rotation, the state of the array will be stored from indices 2 to N+1, then indices 3 to N+2, and so on.
To extend the solution for a circular array, we solve the problem on the array from indices 1 to N, store this result, then solve it again for the array from indices 1 to 2N, and subtract this result with the previously stored result.
Why do we do this?
The array is circular. It will have two types of subarrays: non-circular subarrays (which end before index (N+1) ) and circular subarrays (which start before index (N+1), but end after index N). The non-circular subarrays lie completely between indices 1 and N, so the result for them is counted twice, while the result for the circular ones is counted only once. When we subtract the result for our array of size 2N with the original array of size N, the extra counted result for the non-circular subarrays is subtracted, so we get the actual result.
So, to solve the problem:
- Apply array rotation trick: a[i+N] = a[i] (for all 1 \le i \le N).
- Find the previous greater than or equal to and the next greater than element for each element of the array.
- Solve the problem (compute the increasing, decreasing and constant arrays and obtain the answer array) for array indices from 1 to N and store the result.
- Solve the problem for array indices from 1 to 2N, and subtract the stored result from this, to get the answer.
TIME COMPLEXITY:
show
The time complexity is: O(N)
Why?
The operations: range-updates, next greater element, the function arrays, etc. take O (N), and are independent of each other.
Thus, the time complexity is O(N).
SOLUTIONS:
Setter
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
int a[2123456],b[1234567];
int arr[2123456],gg[2123456],haha[2123456],previ[2123456],nexti[2123456];
int solve(vi vec){
int n=vec.size();
int i;
stack<int> st;
rep(i,n){
while(!st.empty() && vec[st.top()]<vec[i]){
nexti[st.top()]=i;
st.pop();
}
st.push(i);
}
while(!st.empty()){
nexti[st.top()]=n;
st.pop();
}
fd(i,n-1,0){
while(!st.empty() && vec[st.top()]<=vec[i]){
previ[st.top()]=i;
st.pop();
}
st.push(i);
}
while(!st.empty()){
previ[st.top()]=-1;
st.pop();
}
rep(i,n+10){
arr[i]=0;
gg[i]=0;
haha[i]=0;
}
int l,r;
rep(i,n){
l=i-previ[i];
r=nexti[i]-i;
if(l>r)
swap(l,r);
arr[1]+=vec[i];
arr[l+1]-=vec[i];
gg[l+1]+=vec[i]*l;
gg[r+1]-=vec[i]*l;
haha[r+1]+=vec[i];
haha[r+l]-=vec[i];
gg[r+1]+=vec[i]*(r+l);
gg[r+l]-=vec[i]*(r+l);
}
f(i,1,n+10){
arr[i]+=arr[i-1];
gg[i]+=gg[i-1];
haha[i]+=haha[i-1];
}
f(i,1,n+1){
a[i]=(arr[i]-haha[i])*i+gg[i];
//assert(haha[i]>=0);
}
return 0;
}
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
// cerr<<t<<endl;
while(t--){
int n;
cin>>n;
int i;
vi vec,vec1;
int val;
rep(i,n){
cin>>val;
vec.pb(val);
}
solve(vec);
rep(i,n+1){
b[i]=a[i];
}
rep(i,n){
vec.pb(vec[i]);
}
solve(vec);
f(i,1,n+1){
a[i]-=b[i];
}
f(i,1,n+1){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
Tester
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
const int N=2e6+5;
int prv[N],nxt[N],a[N],ans[N],lol[N],gg[N],arr[N];
stack<int>st;
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
//t=1;
while(t--){
//cout<<N<<endl;
int n,i,p,c1,c2;
cin>>n;
rep(i,n){
cin>>a[i];
a[i+n]=a[i];
}
f(i,1,n+1){
arr[i]=0;
gg[i]=0;
lol[i]=0;
}
st.push(0);
i=1;
while(i<2*n){
if(!st.empty()){
p=st.top();
}
while(!st.empty()&&a[p]<a[i]){
st.pop();
nxt[p]=i;
if(!st.empty())
p=st.top();
}
st.push(i);
i++;
}
while(!st.empty()){
p=st.top();
st.pop();
//cout<<p<<"SDDDDDDD"<<endl;
nxt[p]=n*2;
}
st.push(2*n-1);
i=2*n-2;
while(i>=0){
if(!st.empty()){
p=st.top();
}
while(!st.empty()&&a[p]<=a[i]){
st.pop();
prv[p]=i;
if(!st.empty())
p=st.top();
}
st.push(i);
i--;
}
while(!st.empty()){
p=st.top();
prv[p]=-1;
st.pop();
}
rep(i,n){
c1=(i+n)-(prv[i+n])-1;
if(c1==n-1){
arr[1]+=a[i];
arr[n+1]-=a[i];
}
else{
c2=nxt[i]-i-1;
if(c2>=n-1){
arr[1]+=a[i];
arr[c1+1]-=a[i];
gg[c1+1]+=a[i]*(c1+1);
gg[n+1]-=a[i]*(c1+1);
}
else{
if(c1>c2){
swap(c1,c2);
}
arr[1]+=a[i];
arr[c1+2]-=a[i];
gg[c1+2]+=a[i]*(c1+1);
gg[c2+2]-=a[i]*(c1+1);
gg[c2+2]+=a[i]*(c1+c2+2);
gg[c1+c2+2]-=a[i]*(c1+c2+2);
lol[c2+2]+=a[i];
lol[c1+c2+2]-=a[i];
}
}
}
f(i,1,n+1){
gg[i]=i>1?gg[i-1]+gg[i]:gg[i];
arr[i]=i>1?arr[i-1]+arr[i]:arr[i];
lol[i]=i>1?lol[i-1]+lol[i]:lol[i];
ans[i]=gg[i]+(arr[i]-lol[i])*i;
cout<<ans[i]<<" ";
}
cout<<endl;
}
return 0;
}
Editorialist
CodeChef: Practical coding for everyone
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
private static final int lim=(int)(2e6+10);
private static long[] increasing, offset, decreasing;
private static int[] next, prev;
private static long[] arr, ans, halfAns;
private static ArrayDeque<Integer> stack;
private static StringBuilder sb;
private static void appendAns(int N)
{
for(int i=1;i<=N;i++)
sb.append(ans[i]).append(" ");
sb.append("\n");
}
private static void addRotation(int N) //rotation trick
{
for(int i=0;i<N;i++)
arr[i+N]=arr[i];
}
private static void restoreAns(int N) //stores the actual answer for cyclic array
{
for(int i=1;i<=N;i++)
ans[i]-=halfAns[i];
}
private static void storeAns(int N) //stores answer for linear array (not cyclic)
{
for(int i=1;i<=N;i++)
halfAns[i]=ans[i];
}
private static void calcAns(int N) //calculates the answer
{
for(int i=1;i<=N;i++)
ans[i]=(increasing[i]+decreasing[i])*i+offset[i];
}
private static void evaluate(int N) //finding actual array values after all the updates
{
for(int i=1;i<=N;i++)
{
increasing[i]+=increasing[i-1];
decreasing[i]+=decreasing[i-1];
offset[i]+=offset[i-1];
}
}
private static void init(long[] a, int from, int to, int val) //initialises the arrays with 0s
{
Arrays.fill(a, from, to, val);
}
private static void rangeUpdate(long[] diffArr, int i, int j, long val) //performs range update using difference array
{
diffArr[i]+=val;
diffArr[j+1]-=val;
}
private static void prevGreaterOrEqual(int N) //closest >= element to the left of this
{
for(int i=N-1;i>=0;i--)
{
while (!stack.isEmpty()&&arr[stack.peek()]<=arr[i])
prev[stack.pop()]=i;
stack.push(i);
}
while (!stack.isEmpty())
prev[stack.pop()]=-1;
}
private static void nextGreaterElement(int N) //closest > element to the right of this
{
for(int i=0;i<N;i++)
{
while (!stack.isEmpty()&&arr[stack.peek()]<arr[i])
next[stack.pop()]=i;
stack.push(i);
}
while (!stack.isEmpty())
next[stack.pop()]=N;
}
private static void solve(int N)
{
nextGreaterElement(N);
prevGreaterOrEqual(N);
init(increasing,0,N+5,0);
init(offset,0,N+5,0);
init(decreasing,0,N+5,0);
for(int i=0;i<N;i++)
{
int l=i-prev[i];
int r=next[i]-i;
if(l>r)
{
int tmp=l;
l=r;
r=tmp;
}
// part with subarray length x <= l will be updated with a[i]*x (into x will be done later)
// This will result in an increasing linear function
rangeUpdate(increasing,1,l,arr[i]);
//part with subarray length from (l+1) to r will be updated with a[i]*l
// Constant function
rangeUpdate(offset,l+1,r,arr[i]*l);
//part with subarray length from (r+1) to (r+l-1) will be first updated with (- a[i]*x )
// (into x will be done later)
// Then, updated with a[i]*(r+l)
//This will result in a decreasing linear function
rangeUpdate(decreasing,r+1,r+l-1,-arr[i]);
rangeUpdate(offset,r+1,r+l-1,arr[i]*(r+l));
}
evaluate(N);
calcAns(N);
}
private static void assign()
{
arr=new long[lim];
ans=new long[lim];
halfAns=new long[lim];
increasing=new long[lim];
decreasing=new long[lim];
offset=new long[lim];
next=new int[lim];
prev=new int[lim];
stack=new ArrayDeque<>();
sb=new StringBuilder();
}
public static void main(String[] args) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
assign();
int T=Integer.parseInt(br.readLine().trim());
while(T-->0)
{
N=Integer.parseInt(br.readLine().trim());
String s[]=br.readLine().trim().split(" ");
for(i=0;i<N;i++)
arr[i]=Integer.parseInt(s[i]);
solve(N);
storeAns(N);
addRotation(N);
solve(2*N);
restoreAns(N);
appendAns(N);
}
System.out.println(sb);
}
}
Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions 