CHKAR - Editorial

array
chkar
editorial
flfi2016
hard
stock-span

#1

PROBLEM LINK :

contest

practice

Author : Vibhor Gupta

Tester : Vibhor Gupta

Editorialist : Vibhor Gupta

DIFFICULTY :

Hard

PREREQUISITES :

stock span algorithm, Sub-array

PROBLEM :

Rahul has another problem to solve, he is given an array A now he has to increase its every element by its own index(1 - based).

Then he has to find the sum of the maximum elements of the resultant array in every possible sub-array.

As the answer can be large, output it modulo 10^9 + 7.

Flawed Code :

#include

#define Ull long long

using namespace std;

Ull mod=1e9+7;

int main(){

int t;

cin>>t;

while(t–){

int n;

cin>>n;

Ull ar[n],x,ans;

int b[n],a[n];

stack s;

for(int i=0;n>i;i++){cin>>ar*;ar* = (ar* + i + 1)%mod;}

a[0]=0;

s.push(0);

for(int i=1;n>i;i++){

while(!s.empty() && ar* > ar[s.top()]){

b[s.top()] = i-s.top();

s.pop();}

a* = (s.empty())? i : i-s.top();

s.push(i);}

while(!s.empty()){

b[s.top()] = n-s.top();

s.pop();}

ans=1;

for(int i=0;n>i;i++){

x = (a* + b* + 1)%mod;

x = (x * ar*)%mod;

ans = (ans + x)%mod;}

printf("%lld
",ans);

}}

EXPLANATION :

In this question, our main objective is to find the range in which a* is maximum.

We use the stock span algorithm to calculate the range in which a* is maximum. L* = represents the length of sub-array, with elements smaller than a* to its left. Similarly to the right.

The main error in the code, was in the calculation of the sub arrays, L and R.The corrected code can be view at, Corrected Solution.


#2

3
3 3 1
for the above input your code in giving output 23
but it should be 28.
pls explain if I am wrong.