Problem LinkDifficultySimple PrerequisitesSimple dynamic programming ProblemCount the number of nondecreasing subarrays of the given array A[]. How to get 20 pointsLet'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 nondecreasing. In other words, let's iterate through all possible subarrays and then, for each of them, check whether it is a nondescreasing 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(N^{3}). This solution is good enough to solve the first subtask. How to get 50 pointsLet's choose the left bound, say L. Let the right bound, say R, be equal to L initially. Then while the elements are nondecreasing keep increasing the right bound R. At some moment, you will certainly stop. The amount of nondecreasing subarrays with the left bound at L will be equal to RL+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(N^{2}). This solution solves the first and the second subtask, but is still not good enough to get the full points. How to get 100 pointsLet's introduce an array B[] of N elements, where the i^{th} 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 i^{th} element of B[]:
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 forloop with a condition for the computation of B[i] inside. Setter's SolutionCan be found here Tester's SolutionCan be found here
This question is marked "community wiki".
asked 04 Oct '15, 03:28

For every NonDecreasing segment of length N add N*(N+1)/2 to ans answered 12 Oct '15, 20:52
@siddharths067 I precisely expected to see that in the editorial :P
(12 Oct '15, 23:53)

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

Check this video editorial : https://www.youtube.com/watch?v=lWXGv813xSY answered 13 Oct '15, 21:27

Since the contest has finished. Where can the testcase for the problem evaluation be accessed ???? answered 12 Oct '15, 16:21

What is wrong with my submission? why does it not pass all test cases? answered 15 Oct '15, 22:35

Can please anyone tell what is wrong in my code? It's passing all the test cases but one. answered 16 Oct '15, 13:13

answered 18 Oct '15, 02:25

@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

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[i1]){ 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;
} answered 23 Dec '15, 00:39

please give me a bunch of test samples so that i can check my code and debug it. answered 24 Dec '15, 05:54

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

what is the meaning of time 1 second..? can any one tell me? answered 08 Feb '16, 17:23

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;
} answered 19 Feb '16, 20:41

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

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

//count subarray include<bits stdc++.h=""> 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

this is my code,,,but its giving a test case WA in 3rd test case,,,can anyone please help me in it.... include<iostream>
answered 18 Oct '17, 19:48
