You are not logged in. Please login at www.codechef.com to post your questions!

×

CHKAR - Editorial

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[i];ar[i] = (ar[i] + i + 1)%mod;}

a[0]=0;

s.push(0);

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

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

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

s.pop();}

a[i] = (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[i] + b[i] + 1)%mod;

x = (x * ar[i])%mod;

ans = (ans + x)%mod;}

printf("%lld\n",ans);

}}

EXPLANATION :

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

We use the stock span algorithm to calculate the range in which a[i] is maximum. L[i] = represents the length of sub-array, with elements smaller than a[i] 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.

This question is marked "community wiki".

asked 30 Mar '16, 22:19

vibhor3gupta's gravatar image

4★vibhor3gupta
111
accept rate: 0%

edited 01 Apr '16, 16:44

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 08 Apr '16, 17:10

vip_yadav's gravatar image

3★vip_yadav
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×1,343
×847
×17
×6
×1

question asked: 30 Mar '16, 22:19

question was seen: 851 times

last updated: 08 Apr '16, 17:14