//easy solution
//** aman**/
#include<bits/stdc++.h>
#define ll long long
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll fun(vector &v,ll n){
ll sum=0;
ll cnt=0;
unordered_map<ll,ll> m;
for(ll i=0;i<n;i++){
sum+=v[i];
if(sum==1)cnt++;
cnt+=m[sum-1];
m[sum]++;
}
return cnt;
}
int main(){
ios;
ll t;cin>>t;
while(t–){
ll n;cin>>n;
ll x;
vector v;
for(ll i=0;i<n;i++){
cin>>x;
if(x%4==0)v.push_back(2);
else if(x%2==0)v.push_back(1);
else v.push_back(0);
}
//cout<<fun(v,n)<<endl;
ll ans=n*(n+1)/2-fun(v,n);
cout<<ans<<endl;
}
}
can yo please share the test cases for this problem
hereis my code for the challenge but it’s returning TLE, can any body had a better optimized code/idea?
can anyone point out the mistake i have done in my submission to squared subsequences problem
[CodeChef: Practical coding for everyone]
@vijju123
Can anyone tell me what is the wrong with my code??
first we calculate those no. who have no follow pp-qq condition then to find the answer total - count
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int count=0;
while(t>0)
{
int n=sc.nextInt();
int[] arr=new int[n];
for(int j=0;j<n;j++)
{
arr[j]=sc.nextInt();
}
for(int i=0;i<n;i++)
{
int temp=1;
for(int j=i;j<n;j++)
{
temp=temp Math.abs(arr[j]);
if(temp%4==2)
{
count++;
}
}
temp=1;
}
int ans=(n(n+1)/2)-count;
System.out.println(ans);
count=0;
ans=0;
t–;
}
}
}
Whats HAPPENING IN THIS PROBLEM ?
got it…it was also integer overflow error…i was taking n as int and then calculating n*(n+1)/2
temp%4!=0 in case of temp%4==0
bro i m not able to understand your code or your approach …why so much complex approach when u can solve this in very easy manner
i have done the same mistake. take n as input and calculate n*(n+1)/2 which can be greater than int.
that is the problem. just take n as long
1 Like
Overflow 
Might come as a surprise but even python has a limit. Its around 10^{7000} or something for value of variables. Once you cross this, you get a runtime error.
3 Likes
Code 1
if (a[i] % 2 == 0)
a[i] = 1
else
a[i] = 0
Code 2
if (a[i] % 2 == 1)
a[i] = 0
else
a[i] = 1
I used Code 1 and I had AC but I used Code 2 and had WA. I’m trying to understand why. Any idea?
can anyone where I am getting wrong ,I tried a brute force approach to the problem and its giving correct outputs as per me .Link to the code is below,please help and thanks.
https://www.codechef.com/viewsolution/31680208
I did the same but it get wrong answer in two cases… Please review it… Thanks… CodeChef: Practical coding for everyone
Could you please explain it a bit more ? Why sum = 1 works ?
2,6,10,14,18,22… this is series they all no. are do not give the pp-qq result.
so all they no. if we identify then we see that all no. are devided by 4 remainder ==2
2%4==2
6%4==2
10%4==2
so why we need to calculate temp%4==0 or temp%4!=0
1 Like
Does that mean If sum = 1 then the product has only one 2 in prime factor. And that’s why It doesn’t count
How can it be N*logN?
Please help?
And how will O(N) pass the test cases?
the constraints specify that
N over all test cases does not exceed 10^6
and there are 10^3 tests cases
then for O(N) there are 10^3 * 10^6 = 10^9 operations
how will O(N ) pass the test cases?