SUBINC - Editorial

[xcwgf666]

Problem Link

Practice

Contest

Difficulty

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(N³).

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(N²).

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 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[]:

• 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 i^th element without loss of non-decreasingness and one more non-decreasing subarray that ends at the i^th 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 i^th 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

[dragonemperor]

@admin Please don’t change test files during the contest. Especially during the last days.

[teswar]

Since the contest has finished. Where can the testcase for the problem evaluation be accessed ???

[atulshanbhag]

@teswar testcases arent released by codechef

[siddharths067]

For every Non-Decreasing segment of length N add N(N+1)/2* to ans

[raunak_parijat]

@siddharths067 I precisely expected to see that in the editorial

[ankit15]

Check this video editorial : https://www.youtube.com/watch?v=lWXGv813xSY

[gestapo]

#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<n;i++)
{
cin>>arr[i];
}
sum = 0;
for(i = 0;i<n;i++)
B[i] = 1;
for(i = 0;i < n ;i++)
{
if(i != 0)
{
if(arr[i] >= arr[i-1])
B[i] = B[i] + B[i-1];
}
sum = sum + B[i];
}
cout<<sum<<endl;
}
return(0);
}

What is wrong with my submission? why does it not pass all test cases?

[gestapo]

It passed! Need to declare sum as long long int !

[ankit2049]

Can please anyone tell what is wrong in my code? It’s passing all the test cases but one.

This is my code

[atulshanbhag]

use long long instead of int

[dibya1rb12_3]

#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 longn;
long long i,c=0,ans=0,flag=0,x=0;
for(i=0;i<n;i++)
{
a[i]=read();
}
for(i=0;i<n-1;i++)
{
if(a[i]<=a[i+1])
{
c++;
flag=1;
vis[i]=1;
vis[i+1]=1;
}
else{
if(c!=0)
{
ans+=((c+1)(c+2))/2;
}
c=0;
}
}
x=count(vis,vis+n,0);
if(c!=0)
{
ans+=((c+1)(c+2))/2;
}
cout<<ans+x<<endl;
delete[] a;
delete[] vis;
}
return 0; }

[prasadram126]

@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?

[mihirpsagar611]

Hi,
Can anyone explain me where I’m going wrong?
It’s passing all test cases except for one…
link text

[vermavishal891]

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

include

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;

}

}

[prakhar1605]

please give me a bunch of test samples so that i can check my code and debug it.

[archit910]

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

[lamaj]

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.”

[iamrajat]

what is the meaning of time 1 second…?
can any one tell me?

[priyab_95]

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;

}