# SUMSUB - Editorial

Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

EASY-MEDIUM

## PREREQUISITES:

Stack, Dynamic programming

## PROBLEM:

Given an array of N integers A_1, A_2, \dots , A_N, a function f(i,j) is defined as follows:
f(i,j) = A_i + max(A_i,A_{i+1}) + max(A_i,A_{i+1}, A_{i+2}) \dots + max(A_i,A_{i+1}, \dots, A_j).

We need to compute the value \sum_{i=1}^{N}\sum_{j=i}^{N} f(i,j) modulo 10^9 + 7.

## QUICK EXPLANATION:

• Let max_{i,j} be defined as max(A_i, A_{i+1}, \dots , A_j) .

• The problem can be reformulated as: \sum_{i=1}^{N}\sum_{j=i}^{N} max_{i,j} \cdot (N+1-j) .

• Let us define a dp state where dp_i = \sum_{j=i}^{N} max_{i,j} \cdot (N+1-j) for all 1 \leq i \leq N.

• dp_i = A_i \cdot \sum_{j=i}^{ind-1} (N+1-j) \hspace{1 mm} + \hspace{1 mm} dp_{ind} where ind is the nearest index greater than i where dp_i \geq dp_{ind} .

## EXPLANATION:

Let max_{i,j} be defined as max(A_i, A_{i+1}, \dots , A_j) .

Now, there are a total of N+1-j terms which have max_{i,j} component inside them. They are f(i,j), f(i,j+1), f(i,j+2) \dots , f(i,N).

Therefore, our problem can be formulated as to find the value \sum_{i=1}^{N}\sum_{j=i}^{N} g(i,j) where
g(i,j) = max_{i,j} \cdot (N+1-j).

Let us define a dp state where dp_i = \sum_{j=i}^{N} g(i,j) for all 1 \leq i \leq N .

Let us define ind as the nearest index greater than i for which A_{ind} \geq A_i. This means that for all k from i+1 to ind-1, we have max_{i,k} = A_i. Also, for all k from ind to N, we have max_{i,k} = max_{ind,k} since A_{ind} \geq A_i .

Therefore,

dp_i = \sum_{j=i}^{N} max_{i,j} \cdot (N+1-j)

\implies dp_i = \sum_{j=i}^{ind-1} A_i \cdot (N+1-j) \hspace{1 mm} + \hspace{1 mm} \sum_{j=ind}^{N} max_{ind,j} \cdot (N+1-j)

\implies dp_i = \sum_{j=i}^{ind-1} A_i \cdot (N+1-j) \hspace{1 mm} + \hspace{1 mm} dp_{ind}

\implies dp_i = A_i \cdot \sum_{j=i}^{ind-1} (N+1-j) \hspace{1 mm} + \hspace{1 mm} dp_{ind}

\sum_{j=i}^{ind-1} (N+1-j) can be simplified easily if we know the value of \sum_{j=i}^{ind-1} j which has the value equal to \frac{ind \cdot (ind-1)}{2} - \frac{i \cdot (i-1)}{2}.

The only thing left is to find the nearest index greater than i which has A_{ind} \geq A_i. This is a classic problem which can be done for all indices in O(N) using a stack.

## TIME COMPLEXITY:

O(N) for each testcase.

## SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
#define int long long int
using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
int tests;
cin >> tests;
while (tests--)
{
int n;
cin >> n;

vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];

stack<int> s;
vector<int> dp(n + 5);
int ans = 0;

for (int i = n; i >= 1; i--)
{
while (!s.empty() && a[i] > a[s.top()])
{
s.pop();
}

int ind = n + 1;
if (!s.empty())
ind = s.top();

s.push(i);

int temp1 = (n + 1) * (ind - i) % MOD;
int temp2 = ((ind * (ind - 1)) / 2 - (i * (i - 1)) / 2) % MOD;
int temp = ((temp1 - temp2) * a[i]) % MOD;
temp = (temp + MOD) % MOD;

dp[i] = (temp + dp[ind]) % MOD;

ans += dp[i];
ans %= MOD;
}

cout << ans << endl;
}
return 0;
}


Setter's solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 2e9;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
int n, a[N], ans[N];

void solve() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
stack<pair<int, int>> st;
st.push({INF, n});
ans[n] = 0;
for (int i = n - 1; i >= 0; i--) {
while (a[i] >= st.top().first) {
st.pop();
}
int idx = st.top().second;
int len = idx - i;
ans[i] = (ans[idx] + ((len * (len + 1) / 2 + len * (n - idx)) % mod * a[i]) % mod) % mod;
st.push({a[i], i});
}
int res = 0;
for (int i = 0; i < n; i++) {
res = (res + ans[i]) % mod;
}
cout << res << '\n';
}

signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}


Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md 1000000007
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
for(int i = 0; i < n; i++){
cin>>a[i];
}
ll pr[n], nx[n];
vector<int> v;
for(int i = 0 ; i < n; i++){
nx[i] = n;
if(v.size()){
if(a[v.back()] <= a[i]){
nx[v.back()] = i;
v.pop_back();
i--;
continue;
}
}
v.push_back(i);
}
v.clear();
for(int i = n - 1; i > -1; i--){
pr[i] = -1;
if(v.size()){
if(a[v.back()] < a[i]){
pr[v.back()] = i;
v.pop_back();
i++;
continue;
}
}
v.push_back(i);
}
ll ans=0;
for(int i = 0; i < n; i++){
ll temp = ((nx[i] - i) * (nx[i] - i + 1)) / 2 + (n - nx[i]) * (nx[i] - i);
temp %= md;
temp *= i - pr[i];
temp %= md;
temp *= a[i];
temp %= md;
ans += temp;
ans %= md;
}
cout<<ans<<"\n";
}
return 0;
}



Please comment below if you have any questions, alternate solutions, or suggestions.

I used binary search and sparse stable to find the interval for each index for which is it maximum and accordingly calculated the coefficient of each element.
Note : This method only works for distinct element so first you need to make all the elements distinct.
For eg if the array is 2 3 4 5 2 3 we can sort it as 2 2 3 3 4 5 and then change the values so that each of them are distinct somewhat like 1 2 3 4 5 6 and then put them back to their position so the actual array will become 1 3 5 6 2 4.
Link to submission : Solution: 52759149 | CodeChef

1 Like

Bhai aise question ka idea aate he nhi bhai . aur practise bhi bohot kare h kuch upay batao bhai

7 Likes

Can you elaborate what you have done?

If you guys prefer video editorials, here are the solutions of all the problems: Codechef Starters 16 Solutions || All Problems (Global Rank 4!) - YouTube

why we have (ind (ind-1))/2 - (i (i-1))/2. that part is not clear.
can anyone explain me what is it?

Editorialistâ€™s solution is giving me Wrong Answer.

S (j) from i to ind-1 is same as [ i+(i+1)+(i+2)+â€¦+(ind-1)] is equivalent to (sum from 1 to ind-1) - (sum from 1 to i-1), and S(j)=(j)*(j+1)/2, so replace j with ind-1 and i-1,
where S(j) is 1+2+3+4+â€¦+j

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
long long int sum(int x)
{
long long int res=1LL;
res=res*x;
res=res*(x+1);
res/=2;
return res;
}
int M= 1000000007;
void solve()
{
long long int n;
cin>>n;
long long int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
stack<int>s;
vector<long long int>next(n);
for(int i=0;i<n;i++)
{
if(s.empty()||a[s.top()]>a[i])
{
s.push(i);
}
else
{
while(!s.empty()&&a[s.top()]<=a[i])
{
next[s.top()]=i;
s.pop();
}
s.push(i);
}
}
while(!s.empty())
{
next[s.top()]=n;
s.pop();
}
vector<long long int>dp(n+1,0LL);
for(int i=n-1;i>=0;i--)
{
long long int j=next[i];
long long int temp=(j-i);
long long int first=sum(temp);
first=first*a[i];
first%=M;
long long int second=temp*a[i];
second%=M;
second*=(n-j);
second%=M;
dp[i]=((dp[j]+first)%M+second)%M;
}
long long int ans=0LL;
for(long long int i:dp)
{
ans=(ans+i)%M;
}
cout<<ans<<endl;
}


Can anyone suggest me what i am doing wrong here it is passsing all testcase except 2 no idea where it is getting wrong i converted everything to long long still wrong the idea is approx similar

What a beautiful idea , couldnâ€™t solve in contest but it was good

Here itâ€™s Another Solution

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>

using namespace std ;

#define int long long int

const int mod = 1e9 + 7 ;

int modadd(int n , int m){ return (n + m) % mod ; }

int modmul(int n , int m){ return (n * m) % mod ; }

int modsub(int n , int m){ return ((n - m) % mod + mod) % mod ; }

int modAPsum(int n){ int m = (n * (n + 1)) / 2 ; return m % mod ; }

void sunny(){
int n ;
cin >> n ;
int a[n] , l[n] , r[n] , ans = 0 ;
for(int i = 0 ; i < n ; i ++) cin >> a[i] ;
stack<int> st ;
for(int i = 0 ; i < n ; i ++){
while(not st.empty()){
if(a[st.top()] < a[i]){
r[st.top()] = i ;
st.pop() ;
}
else break ;
}
st.push(i) ;
}
while(not st.empty()){
r[st.top()] = n ;
st.pop() ;
}
for(int i = n - 1 ; i >= 0 ; i --){
while(not st.empty()){
if(a[st.top()] <= a[i]){
l[st.top()] = i ;
st.pop() ;
}
else break ;
}
st.push(i) ;
}
while(not st.empty()){
l[st.top()] = -1 ;
st.pop() ;
}
for(int i = 0 ; i < n ; i ++){
int l_ = i - l[i] , r_ = n - i , r__ = n - r[i] ;
ans = modadd(ans , modmul(a[i] , modmul(l_ , modsub(modAPsum(r_) , modAPsum(r__))))) ;
}
cout << ans << '\n' ;
}

int32_t main()
{
int t ;
cin >> t ;
while(t--) sunny() ;
return 0;
}