SUBINC - Editorial

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

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

#include
#include
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;
}

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.

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?

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

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

1 Like

use long long instead of int

1 Like

can someone tell why this sol is giving sigtstp error

#include
#include<bits/stdc++.h>
using namespace std;

int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int a[n],b[n];
b[0]=1;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=1;i<n;i++){
if(a[i-1]<=a[i]) b[i]=b[i-1]+1;
else b[i]=1;
}
cout<<accumulate(b,b+n,0)<<endl;

}
return 0;

}

in the question it says the subarray means A\left [ i,j \right ] where 1 \leqslant i \leqslant j \leqslant N is a sequence of integers A_{i}, A_{i+1}, ..., A_{j} . so in explanation it shows A\left [ 1,1 \right] is a subarray how can \{A_{i}, A_{i}\} is called a subarray ??

why [2,3] is not mentioned as a non decreasing subarray?

/only one test case is failing and i dont know where and what is the problem in my code/

import java.util.;
import java.lang.
;
import java.io.*;

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try {
Scanner sc = new Scanner(System.in);
int t =sc.nextInt();
while(t-- > 0)
{
int n = sc.nextInt();
long a[] = new long[n];
for(int x = 0;x < n;x++)
a[x] = sc.nextLong();
int count = n;
int i = 0,j = 1;
int curr = 0;
for(int x = 1;x < n;x++) //Traversing each element pnce
{
if(a[x] >= a[x - 1])
curr++;
else
{
count += getSum(curr);
curr = 0;
}
}
count += getSum(curr);

            System.out.println(count);
        }
    } catch(Exception e) {
        e.printStackTrace();
        System.out.println("Exception occured!");
    }
}

public static int getSum(int n)         //retruns sum(if n  == 4) it returns (4 + 3 + 2 + 1))
{
    int sum = 0;
    for(int x = 1;x <= n;x++)
        sum += x;
    return sum;
}

}

Here’s my solution

#include
#include<bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int T;
cin >> T;
while(T–)
{
int N;
cin >> N;
int arr[N];

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }
    
    long int res = 0;
    //seqLen denotes the current length of non decreasing sequence 
    //while traversing through the array elements, it gets reset to 1
    //whenever an elem greater than prev elem is encountered.
    int seqLen = 0;

    if(N>0)
    {
        res = 1;
        seqLen = 1;
    }
    
    for(int j=1; j<N; j++)
    {
        if(arr[j] >= arr[j-1])
        {
            res = res+ (seqLen + 1);
            seqLen++;
        }
        else
        {
            res += 1;
            seqLen = 1;
        }
    }
    cout << res << endl;
}
return 0;

}

Try to use unsigned long long or long long for your sum variable

#include
#include
#include
#include
#include
#include<math.h>
#include
using namespace std;
typedef long long int ll;
int main()
{
ll t;
cin>>t;
while(t–){
ll n;
cin>>n;
ll arr[n];
for(ll i=0;i<n;i++)
cin>>arr[i];
ll count=1;
ll sum=0;
for(ll i=0;i<n-1;i++)
{
if(arr[i]<=arr[i+1])count++;
else
{
sum=sum+((count*(ll)(count+1))/2);
count=1;
}
}
if(count!=0)
sum=sum+((count*(ll)(count+1))/2);
cout<<sum<<endl;

}

}

can anyone help me out in figuring out error within my code. I am unable to pass test case 11. i have tried too hard till now but not able to figure out the error.

Here is my code : CodeChef: Practical coding for everyone

Thank you

I used the 2 pointer approach and I believe my code runs in O(N). The idea is almost the same as the 2 approach mentioned here except I skip a few obvious cases in my code and I also use some basic combinatorics. In the worst case, time complexity will be O(N^2) when the array is sorted in ascending order.
Below is the link to my code:
https://www.codechef.com/viewsolution/39374285

Where I am Going Wrong ?
T = int(input())
for i in range (T):
N = int(input())
arr = list(map(int, input().split(" ", N)))
ans = 0
for k in range (N):
for l in range (k+1, N):
if (arr[k]==arr[l]-1):
ans += 1
else :
pass
print(ans + len(arr))

[2,3] is a subsequence not a subarray. Elements in the subarray can be continuous. But not in the case of subsequence.

https://www.codechef.com/viewsolution/46882263
I Get Stuck In One Task Of Every SubTask.
Anybody Can Help Me Out?

@karangiri121 use unsigned long long