# SQRDSUB - Editorial

can you please send the test cases as i was unable to find the mistake in my code! it worked for almost all the sets but the last 2 showed wrong answer!

Hi so I am quite new to competitive programming, just wanted to know why brute force approach was giving a wrong answer in sub tasks, i wanted to know which cases my approach could not detect. I know it was a n^2 complexity, but i just want to know which test cases was the code failing for
here is the code, it would be really helpful if someone debugged it thanks

can you tell what’s wrong in this approach, done the same as explained in editorial except I have not converted the values of array to 0,1 and 2 and done directly instead.

I used a more direct approach.

Loop for each number i. In each pass, add the number of good subsequences ending at this i.

As we go through the loop, maintain the positions of (a) the last even number index_even, and (b) the last multiple of 4 index_four.

If the current i is odd, add the number of subsequences beginning since the last even number.

If the current i is a multiple of four, remember it as both a multiple of 4 and as an even number.

Else the current number is even. Set last multiple of 4 to the previous even number, if any.

If there has been a multiple of 4, add the number of subsequences from the start which include this multiple of 4 = (index_four + 1).

I’ve been trying this problem for days and after knowing the logic I still couldn’t able to get the AC.
I made a test Case generator and put my algorithm and tester’s solution in it. Even after thousands of test cases my algo is producing the same output as the tester solution but when I’m submitting the code I get WA. (except 2 test cases 2, 5)
while taking input of numbers I changed them,
if(num[i]%4 == 0) num[i] = 16;
else num[i] = num[i]%8;
My approach :

1. I’ve counted all the odd numbers and also if any sub array has odd as its product. A sub Array can only have odd as its product if its been multiplied by odd numbers only.(right?)
2. next, I’ve counted all the number divisible by 4 or number of sub array which is divisible by 4.
PS: sorry for my bad english.
Solution file
CodeChef: Practical coding for everyone

i am getting wrong answer in sub task 2( 3,4,5) and not in 6 can anybody help me with this (CodeChef: Practical coding for everyone)

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

Thank you for the info Sir @vijju123