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

Link:
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

Youtube : CodeChef April Long 2020 | Squared Subsequences | Hindi Editorial - YouTube

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 :slight_smile: … please like it’s my first time :slight_smile:

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 :slight_smile:

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 :slight_smile:

@ [ssrivastava990] can you reply for the below post if you have time!!
@Help for squaredsusequences works in python but not in c++?