SUMSUB - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

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. :slight_smile:

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. :slightly_smiling_face:

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
image
Anyone Please

What a beautiful idea , couldn’t solve in contest but it was good :slight_smile:

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