×

Simple

# Pre-requisites

Simple dynamic programming

# Problem

Count the number of non-decreasing subarrays of the given array A[].

# How to get 20 points

Let's choose the left bound, say L. After the left bound is fixed, let's choose the right bound, say R. And now, let's check that the subarray A[L, R] is non-decreasing.

In other words, let's iterate through all possible subarrays and then, for each of them, check whether it is a non-descreasing one or not.

Choosing the left bound takes O(N) operations, choosing the right bound takes O(N) operations too, and checking subarray also takes O(N) operations. Since these operations are nested, hence the total complexity will be O(N3).

This solution is good enough to solve the first subtask.

# How to get 50 points

Let's choose the left bound, say L. Let the right bound, say R, be equal to L initially. Then while the elements are non-decreasing keep increasing the right bound R. At some moment, you will certainly stop. The amount of non-decreasing subarrays with the left bound at L will be equal to R-L+1 for every fixed L. The sum of all this values is the answer to the problem.

Choosing the left bound takes O(N) operations, and finding the right bound takes O(N) operations. Since these operations are nested, the complexity of the whole solution will be O(N2).

This solution solves the first and the second subtask, but is still not good enough to get the full points.

# How to get 100 points

Let's introduce an array B[] of N elements, where the ith element of B[] defines the amount of the correct subarrays with the right bound equal to i.

Now, let's give the rules for calculating the ith element of B[]:

• if A[i-1] ≤ A[i], then B[i] = B[i-1] + 1 since every non-decreasing subarray that ends at the (i-1)th element can be continued with the ith element without loss of non-decreasingness and one more non-decreasing subarray that ends at the ith element is A[i, i].
• if A[i-1] > A[i], then B[i] = 1 since any subarray that ends at the (i-1)th element will lose its' non-decreasingness if continued with the ith element, so the only suitable subarray will be A[i, i].

So, the answer will be equal to the sum of all elements of B[]. The complexity is O(N), because the computation of the array B turns out to be a single for-loop with a condition for the computation of B[i] inside.

# Setter's Solution

Can be found here

# Tester's Solution

Can be found here

This question is marked "community wiki".

719436377
accept rate: 0%

19.8k350498541

 4 For every Non-Decreasing segment of length N add N*(N+1)/2 to ans answered 12 Oct '15, 20:52 79●2●7 accept rate: 4% @siddharths067 I precisely expected to see that in the editorial :P (12 Oct '15, 23:53)
 3 this ques can be done using COMBINATIONS .... for each such array (non decreasing) .let N is the total number of elements in such array then (n*n+1)/2 is the answer .here is my solution : https://www.codechef.com/viewsolution/8300161 answered 26 Dec '15, 01:49 820●2●12 accept rate: 3%
 1 Check this video editorial : https://www.youtube.com/watch?v=lWXGv813xSY answered 13 Oct '15, 21:27 2★ankit15 41●2 accept rate: 0%
 0 @admin Please don't change test files during the contest. Especially during the last days. answered 12 Oct '15, 15:07 893●2●11●35 accept rate: 10%
 0 Since the contest has finished. Where can the testcase for the problem evaluation be accessed ???? answered 12 Oct '15, 16:21 2★teswar 1 accept rate: 0%
 0 @teswar testcases arent released by codechef answered 12 Oct '15, 16:59 226●2●9 accept rate: 9%
 0  #include using namespace std; #define MAXN 100000 int arr[MAXN+10]; int B[MAXN+10]; int main() { long int sum = 0,t = 0,i=0,j=0; cin>>t; while(t--) { int n; cin>>n; for(i = 0;i>arr[i]; } sum = 0; for(i = 0;i= arr[i-1]) B[i] = B[i] + B[i-1]; } sum = sum + B[i]; } cout<
 0 Can please anyone tell what is wrong in my code? It's passing all the test cases but one. This is my code answered 16 Oct '15, 13:13 1 accept rate: 0% use long long instead of int (16 Oct '15, 13:59)
 0  #include #include #include #ifndef ONLINE_JUDGE #define gc getchar #else #define gc getchar_unlocked #endif // ONLINE_JUDGE using namespace std; inline long long read(){ long long num=0; char c=gc(); while(!(c>='0' && c<='9')){ c = gc(); } while(c>='0' && c<='9'){ num=(num<<3)+(num<<1)+c-'0'; c=gc(); } return (num); } int main() { int t; cin>>t; while(t--) { long long n; cin>>n; long long* a=new long long[n]; long long* vis=new long long[n](); long long i,c=0,ans=0,flag=0,x=0; for(i=0;i
 0 @siddharths067 i have implemented the same but i got WA , i couldn't figure it out what is the error in my code. So can any one please help me to give some test case to check where it's failing? answered 21 Oct '15, 11:51 12●1 accept rate: 0%
 0 Hi, Can anyone explain me where I'm going wrong? It's passing all test cases except for one.. link text answered 04 Dec '15, 13:02 1 accept rate: 0%

What is wrong with my code? Subtask #11 is wrong and all others are wright.

# include <iostream>

using namespace std; int main(){ register int t = 0, i = 0, n = 0, arr, temp = 1; register long long int sum = 0; cin>>t; while(t--){ temp = 1; sum = 0; cin>>n; arr = new int[n]; for(i = 0; i < n; i++){ cin>>arr[i]; if(i != 0){ if(arr[i] >= arr[i-1]){ temp++; } else{ if(temp != 0){ sum += ((temp)(temp+1))/2; temp = 1; } } } } if(temp != 0){ sum += ((temp)*(temp+1))/2; temp = 1; } cout<<sum<<endl;

}


}

1
accept rate: 0%

 0 please give me a bunch of test samples so that i can check my code and debug it. answered 24 Dec '15, 05:54 1 accept rate: 0%
 0 Why this one is not available for practice anymore? "The contest to which this problem belongs is not running. And hence you cannot make a submission for it." answered 05 Feb '16, 19:12 0★lamaj 1 accept rate: 0%
 0 what is the meaning of time 1 second..? can any one tell me? answered 08 Feb '16, 17:23 0★iamrajat 1 accept rate: 0%

This is my code..I have used used long long int ..still m getting one WA in subtask 3..Kindly help me..

# include <bits stdc++.h="">

using namespace std;

int main() { int t; cin>>t; while(t--) { long long n,cnt=0,temp; cin>>n;

            long long * a=new long long[n];
for(int i=0;i<n;i++)
{
cin>>temp;
if(temp<=pow(10,9));
a[i]=temp;

}

for(int i=0,loop=0;i<n-1;i++)
{

if(a[i+1]>=a[i])
loop++;

if(a[i+1]<a[i] || i==n-2)
{
cnt+=(loop *(loop+1))/2;
loop=0;
}
}
cout<<cnt+n<<endl;

}

return 0;


}

1
accept rate: 0%

 0 in the examples of first case there was no (2,3) why is it? there was (3,4) & (1,2)? answered 12 Mar '16, 20:32 1 accept rate: 0%
 0 I am getting correct answer for all but task #11. Can anyone please tell what could i be possibly missing? Link to my code: https://www.codechef.com/viewsolution/9722785 answered 23 Mar '16, 02:41 2★ayush07 1 accept rate: 0%
 0 //count subarray include using namespace std; int main() { long long int test,m,size,a[100000],count; cin >> test; while(test--) { cin >> size; m = 0; for(int i = 0;i < size;i++) { cin >> a[i]; } count = 0; for(int j = 0;j < size;j++) { if(a[j] <= a[j+1]) { count++; } else { count++; m = m + (count*(count+1))/2; count = 0; } } cout << m << endl; } return 0; } please can anyone help me finding the error in this code... its passing all the testcases except the first 3 testcases answered 26 Jun '16, 13:56 1 accept rate: 0%
 0 task # 11,12,13,14 gave WA. Code seems fine. Would anyone help me figure out boundary cases ? Thanks here's my code link text answered 10 Sep '16, 17:16 1 accept rate: 0%

this is my code,,,but its giving a test case WA in 3rd test case,,,can anyone please help me in it....

# include<iostream>

#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
long int n,i,count=0,len=1,num=0;
cin>>n;
long int a[2000000];
for( i=0;i<n;i++)
{
cin>>a[i];
}
a[n]=0;
for(int i=0;i<n;i++)
{

if(a[i]<=a[i+1])
{
len++;
}
else
{
if(len>1)
{
int j = ((len)*(len-1))/2;
count=count+j;
}
len=1;
}
}
cout<<count+n<<"\n";
}
return 0;
}


1
accept rate: 0%

 0 I think the test cases are weak for this questions, My solution is O(n^2) with a little dynamic programming, but still passed all test cases and got 100 points. Shouldn't O(n^2) give only 50 points? Here is the link to my solution HI THERE. answered 19 Jun '18, 16:34 5★aaronq8 0 accept rate: 0%
 0 I am not able to understand why my one solution got AC while other got PA I just changed (j - i) with a count_ variable, will someone please explain? answered 02 Aug '18, 14:08 66●5 accept rate: 9%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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
×2,172
×1,173
×103
×10

question asked: 04 Oct '15, 03:28

question was seen: 11,259 times

last updated: 02 Aug '18, 14:08