PROBLEM LINK:
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. 
