PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Raj Khandor
Tester: Felipe Mota
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Basic Math, Pointers.
PROBLEM:
Given an array A of length N, find the number of good contiguous subsequences of A where a contiguous subsequence is considered good if the product of values can be written as the difference of two perfect squares.
QUICK EXPLANATION
- A number can be written as the difference of two perfect squares if and only if it is odd, or a multiple of 4.
- We just need to find the number of contiguous subsequences having the product as multiple of 2 but not multiple of 4, and subtract from the total number of contiguous subsequences.
- If we replace odd values with zeroes, multiples of 4 with 2 and rest with 1, the number of contiguous subsequences to be subtracted is the number of contiguous subsequences with sum 1, which can be easily computed using pointers.
EXPLANATION
As explained in detail here, any number can be written as the difference of two perfect squares if either one of the following holds.
- The number is odd.
- The number is a multiple of 4.
Conversely, the only numbers which cannot be written as the difference of perfect squares are of the form 2*p for some odd number p. We just need to count the number of subarrays, which have the product of this form.
Another thing we can notice is that only the power of 2 in product matters, so we can replace each A_i by the exponent of 2 in A_i. In this reduced array, we need to count the number of subarrays with sum exactly 1 and subtract from total number of subarrays.
Now, this is a well-known problem, as explained here, and in this comment.
Briefly stating, we can compute prefix sums and then for each fixed right end, if the current sum is X, we find the number of positions with sum X-1 which can be found easily using a map. It can also be found using pointers since the array values are non-negative (refer tester’s solution for this).
TIME COMPLEXITY
The time complexity is O(N) or O(N*log(N)) per test case depending upon implementation.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll a[n];
for(ll i=0;i<n;i++)
cin>>a[i];
ll b[n];
for(ll i=0;i<n;i++)
{
if(a[i]%4 == 0)
b[i] = 2;
else if(a[i]%2 == 0)
b[i] = 1;
else
b[i] = 0;
}
ll pre[n];
pre[0] = b[0];
for(ll i=1;i<n;i++)
pre[i] = pre[i-1] + b[i];
ll ans=0;
for(ll i=0;i<n;i++)
{
if(b[i] == 0)
{
ll idx=upper_bound(pre,pre+n,pre[i])-pre;
ans += idx-i;
idx=lower_bound(pre,pre+n,pre[i]+2)-pre;
ans += n-idx;
}
else if(b[i] == 1)
{
ll idx=lower_bound(pre,pre+n,pre[i]+1)-pre;
ans += n-idx;
}
else
{
ans += n-i;
}
}
cout<<ans<<"\n";
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
/**
(p^2 - q^2) = (p + q) * (p - q) = A * B
We can derive that A and B have the same parity,
so the array interval can be represented if the
interval product is either odd or divisible by 4,
this can be calculated by knowing the number of 2
in some interval.
We can use two pointers and accumulated sum to
calculate the number of intervals in O(N)
* */
int t; cin >> t;
while(t--){
int n; cin >> n;
vector<int> a(n + 1, 0);
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] = abs(a[i]);
int r = 0;
while(a[i] % 2 == 0 && r < 2) r++, a[i] /= 2;
a[i] = r;
}
for(int i = 0; i < n; i++) a[i + 1] += a[i];
int p0 = 0, p1 = 0;
long long ans = 0;
for(int i = 1; i <= n; i++){
while(p0 < i && a[i] - a[p0] >= 2) p0++;
while(p1 < i && a[i] - a[p1] >= 1) p1++;
ans += i - (p1 - p0);
}
cout << ans << '\n';
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class SQRDSUB{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
int[] A = new int[n];
for(int i = 0; i< n; i++)A[i] = ni();
int[] B = new int[n];//B[i] == 2 if a[i] == 0, B[i] = 0 if a[i]%4 == 0, 1, 3, B[i] = 1 if a[i]%4 == 2
long total = (n*(long)n+n)/2;
for(int i = 0; i< n; i++){
if(A[i]%4 == 0)B[i] = 2;
else if(A[i]%2 == 0)B[i] = 1;
else B[i] = 0;
}
//We need to subtract number of subarrays with sum 1 now
int[] prefSum = new int[3*n];
prefSum[0]++;
int sum = 0;
for(int i = 0; i< n; i++){
sum += B[i];
if(sum > 0)total -= prefSum[sum-1];
prefSum[sum]++;
}
pn(total);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new SQRDSUB().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
