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?
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?
can someone please explain what is wrong with my solution
w(t) {
int n; cin >> n;
vector a(n);
f(i, n)cin >> a[i];
vector<int> t(n + 1);
t[0] = 0;
t[1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i - 1] >= a[i - 2]) {
t[i] = 2 + t[i - 1];
}
else {
t[i] = 1 + t[i - 1];
}
}
cout << t[n] << endl;
}hey example is given wrong please check it out