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

×

SUBINC - Editorial

1
2

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(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".

asked 04 Oct '15, 03:28

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%

edited 12 Oct '15, 15:04

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 12 Oct '15, 20:52

siddharths067's gravatar image

1★siddharths067
7927
accept rate: 4%

edited 12 Oct '15, 20:55

@siddharths067 I precisely expected to see that in the editorial :P

(12 Oct '15, 23:53) raunak_parijat4★

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

link

answered 26 Dec '15, 01:49

archit910's gravatar image

2★archit910
820212
accept rate: 3%

edited 26 Dec '15, 01:50

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

link

answered 13 Oct '15, 21:27

ankit15's gravatar image

2★ankit15
412
accept rate: 0%

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

link

answered 12 Oct '15, 15:07

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

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

link

answered 12 Oct '15, 16:21

teswar's gravatar image

2★teswar
1
accept rate: 0%

@teswar testcases arent released by codechef

link

answered 12 Oct '15, 16:59

atulshanbhag's gravatar image

4★atulshanbhag
22629
accept rate: 9%

                        #include<iostream>
                        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?

link

answered 15 Oct '15, 22:35

gestapo's gravatar image

0★gestapo
1
accept rate: 0%

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

(15 Oct '15, 22:38) gestapo0★

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

This is my code

link

answered 16 Oct '15, 13:13

ankit2049's gravatar image

3★ankit2049
1
accept rate: 0%

use long long instead of int

(16 Oct '15, 13:59) atulshanbhag4★
    #include<iostream>
#include<cstdio>
#include<algorithm>
#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<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; }
link

answered 18 Oct '15, 02:25

dibya1rb12_3's gravatar image

3★dibya1rb12_3
121
accept rate: 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?

link

answered 21 Oct '15, 11:51

prasadram126's gravatar image

2★prasadram126
121
accept rate: 0%

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

link

answered 04 Dec '15, 13:02

mihirpsagar611's gravatar image

3★mihirpsagar611
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;

}

}

link

answered 23 Dec '15, 00:39

vermavishal891's gravatar image

1★vermavishal891
1
accept rate: 0%

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

link

answered 24 Dec '15, 05:54

prakhar1605's gravatar image

2★prakhar1605
1
accept rate: 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."

link

answered 05 Feb '16, 19:12

lamaj's gravatar image

0★lamaj
1
accept rate: 0%

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

link

answered 08 Feb '16, 17:23

iamrajat's gravatar image

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;

}

link

answered 19 Feb '16, 20:41

priyab_95's gravatar image

1★priyab_95
1
accept rate: 0%

in the examples of first case there was no (2,3) why is it? there was (3,4) & (1,2)?

link

answered 12 Mar '16, 20:32

shreyacode123's gravatar image

0★shreyacode123
1
accept rate: 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

link

answered 23 Mar '16, 02:41

ayush07's gravatar image

2★ayush07
1
accept rate: 0%

//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

link

answered 26 Jun '16, 13:56

karanpartap96's gravatar image

3★karanpartap96
1
accept rate: 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

link

answered 10 Sep '16, 17:16

mithil_levi's gravatar image

3★mithil_levi
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;
}
link

answered 18 Oct '17, 19:48

patilnilesh_40's gravatar image

2★patilnilesh_40
1
accept rate: 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.

link

answered 19 Jun '18, 16:34

aaronq8's gravatar image

5★aaronq8
0
accept rate: 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?

link

answered 02 Aug '18, 14:08

thesmartguy's gravatar image

4★thesmartguy
665
accept rate: 9%

edited 02 Aug '18, 14:09

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
×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