# April Long 2020 | Squared Subsequences | Discussion + Video editorial (Hindi)

DIV 1 : Squared Subsequences
DIV 2 : Squared Subsequences

Source Code :

1. 20 mark Brute Force (TLE) : 5DDk4G - Online IDE & Debugging Tool - Ideone.com
2. 20 mark Brute Force(AC) : LaTd71 - Online IDE & Debugging Tool - Ideone.com
3. Optimised AC : f2f4Dx - Online C++0x Compiler & Debugging Tool - Ideone.com

Approach :
The main problem is reduced to this :
Count all subarrays in which the product modulo 4 is neither 2 nor -2, bcz only a no. which can’t be represented as a difference of two squares are only whose product modulo 4 ie., pro%4 ==2 or -2
From here : What's Possible?

More Specifically we can write this too… Count all subarrays in which there is only one value whose modulo 4 is 2 or -2 , no any other even value come in that subarray.
Count all invalid and subtract it from total subarrays possible.

1 For 20 marks just count all subarrays whose product modulo 4 is neither 2 nor -2

2 For 100 marks

A). Convert array into mod 4 array and count for each postion of ‘2’ or ‘-2’ how many continous odd values are there in left hand side(let it be x ) and how many continous odd values are there in right hand side (let it be y)

B). Let we called these subarrays be invalid , so for each 2 or -2 invalid subarray is

``````   (x+1) * (y+1)
``````

C.) Sum all these.

D). Total subarrays of array of length n is : (n*(n+1)/2)

E). Good subarrays = Total subarrays - (sum of all invalid subarrays )

``````                   (n*(n+1)/2) - Σ((x+1)*(y+1))
``````
10 Likes

if u have any doubt then ask i will explain more … please like it’s my first time 3 Likes

I have applied the same logic but got WA, don’t know why
can you find what is wrong in it?
I was getting WA for both logics commented and uncommented one

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int t;
cin>>t;
while(t--)
{
long long int num;
cin>>num;
long long a[num],i,j,b[num];
for(i=0;i<num;i++)
{
cin>>b[i];
if(b[i]%2==1)
{
a[i]=0;
}
else if(b[i]%4==0)
{
a[i]=2;
}
else
{
a[i]=1;
}
}

long long int m=0;
vector<long long int> v;
for(i=0;i<num;i++)
{
if(a[i]==0)
{
m++;
}
if(a[i]==1)
{
v.push_back(m);
m=0;
}
if(a[i]==2)
{
v.push_back(m);
v.push_back(-1);
m=0;
}
}
if(a[num-1]!=2)
{
v.push_back(m);
}
long long ans=0;
for(i=1;i<v.size();i++)
{
if(v[i]==-1)
{
i++;
}
else
{
ans=ans+v[i]+v[i-1]+1+v[i]*v[i-1];
}
}

/* long long ans=0;
long long int m=0,n=0;
for(i=0;i<num;i++)
{
if(a[i]==1)
{
m=0;
n=0;
if(i==0)
{
m=0;
}
else
{
j=i-1;
while(j>=0)
{
if(a[j]>0)
break;
else
{
m++;
j--;
}
}
}
if(i==(num-1))
{
n=0;
}
else
{
j=i+1;
while(j<num)
{
if(a[j]>0)
break;
else
{
n++;
j++;
}
}
}
ans=ans+m+n+m*n+1;
}
}*/

long long an=num*(num+1)/2;
an=an-ans;
cout<<an<<endl;

}
}``````

An easier approach would be to keep a count of last two digits of products of all subarrays. Then check whether product%4==0 || product%2==1 is true and increment the result.

Code

1 Like

good approach Yes bro I also had the same approach

Detailed solution in layman language.

1 Like

store all array by doing modulo 4 and then one simple approach is to find a sub-array which have single 2 and 0 count of zeros
,and this will not be counted as good sub-array,else all will be counted…

Can anyone tell me how to find out subarray in O(n)

I have used almost same approach still got WA can u check the codes

There is no methodd to find out subarray in O(n) … but it depends on problem too @ [ssrivastava990] can you reply for the below post if you have time!!
@Help for squaredsusequences works in python but not in c++?