SQRDSUB - Editorial

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

17 Likes

Here is my alternate (and somewhat easy) version of the proof about the properties of numbers which can be written as difference of 2 squares (and a simple DP implementation)

2 Likes
  1. Convert to mod 4 array

  2. For each ‘2’ or ‘-2’ count total continous odd element in left (let it be x ) and continous odd element in right (let it be y)

  3. multiply (x+1) * (y+1)
    4.summation all

  4. subtract it from total subarrays ie., (n*(n+1)/2)

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

link broken

Right now codechef is not allowing one to see others submissions. :neutral_face:

Detailed solution of April Long Challenge.

3 Likes

The better and most easiest way to see this problem is put numbers divisible by 4 = 2, else if they are odd put them 0 else put them 1. and find number of subarrays with sum = 1, and substract them from total subarrays. then the question is standard prefix sum problem.
my submission for reference

4 Likes

Since the sum of N over all test cases doesn’t exceed 10^6, I am not able to figure out why my code got TLE for original constraints even though it’s O(N x Log(N))

Code: ideone

If I made any mistake then please point it out. Thanks! :slight_smile:

Hello,

Can you tell me what is wrong with my solution here?

I have counted odd values on the left side and right side of 2. and after that I have done this ans += total - (left + 1) * (right + 1).

What is wrong here?

#include <bits/stdc++.h>

#define int long long int
#define endl "\n"

using namespace std;

int solve(int arr[], int n)
{
	//int arr[12] = {1, 1, 1, 1, 2, 2, 1, 1, 1, 4, 2, 2};
	//int dpL[12] = {1, 2, 3, 4, 4, 0, 1, 2, 3, 0, 0, 0};
	//int dpR[12] = {4, 3, 2, 1, 0, 3, 3, 2, 1, 0, 0, 0};
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] % 4 == 0)
			arr[i] = 4;
		else if (arr[i] % 2 == 0)
			arr[i] = 2;
		else if (arr[i] % 2 == 1)
			arr[i] = 1;
	}
	
	/*Conditions for dpL*/
	int dpL[n] = { 0 };
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			if (arr[i] == 1) {
				dpL[i] = 1;
			} else if (arr[i] == 2 || arr[i] == 4) {
				dpL[i] = 0;
			}
		} else {
			if (arr[i] == 1) {
				dpL[i] = dpL[i - 1] + 1;
			} else if (arr[i] == 2) {
				if (arr[i - 1] == 1) {
					dpL[i] = dpL[i - 1];
				} else if (arr[i - 1] == 2 || arr[i - 1] == 4) {
					dpL[i] = 0;
				}
			} else if (dpL[i] == 4) {
				dpL[i] = 0;
			}
		}
	}
	
	/*Conditions for dpR*/
	int dpR[n] = { 0 };
	for (int i = n - 1; i >= 0; i--) {
		if (i == (n - 1)) {
			if (arr[i] == 1) {
				dpR[i] = 1;
			} else if (arr[i] == 2 || arr[i] == 4) {
				dpR[i] = 0;
			}
		} else {
			if (arr[i] == 1) {
				dpR[i] = dpR[i + 1] + 1;
			} else if (arr[i] == 2) {
				if (arr[i + 1] == 1) {
					dpR[i] = dpR[i + 1];
				} else if (arr[i + 1] == 2 || arr[i + 1] == 4) {
					dpR[i] = 0;
				}
			} else if (dpR[i] == 4) {
				dpR[i] = 0;
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
	 	if (arr[i] == 2) {
			sum += (dpL[i] + 1) * (dpR[i] + 1);
		}
	}
	
	return sum;
}

int32_t main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		int total = (n * (n + 1)) / 2;
		
		cin >> n;
		
		int arr[n];
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			arr[i] = abs(arr[i]);
		}
		int ans = solve(arr, n);
		cout << total - ans << endl;
	}
}

@taran_1407 An elegant and very simple proof of an odd number can be expressed as a difference of perfect square i.e. p^{2} - q^{2}:

Step-1: Pick an odd number, let’s say n = 9.

lbj1m

Step-2: Bend the above block of blocks in the middle.
part-2

Step: 3 File the void space as shown below:
part-3

The grey area is what is p^{2} - q^{2}.

For our example where n = 9 which can be written as 9 = 5^{2} - 4^{2}, in the figure above the outer square is 5 \times 5 square and the inner one is 4 \times 4.

36 Likes

Here is my approach to this problem. I handled even and odd numbers separately, and replaced odd numbers with 0, even with 1 and divisible by 4 with 2.
For even numbers: for any subarray starting at l and ending at r, if its product % 2 == 0, then ans += n - r as all subarray starting at l and ending at k , k>=r && k<N will also be a part of the solution.
For odd numbers: found a starting index i and an ending index j such that arr[i:j] consists entirely of odd numbers, and updated ans += k(k+1)/2 , k = j-i+1
However, this fails for all but one test case in subtask 2. Any pointers where I am going wrong?

You are calculating total = n*(n+1)/2 without taking input n

1 Like

This is an integer overflow issue. Know that N can be maximum 10^5. Meaning answer can be upto 10^10. Change all variables to long long int.

Got AC with same approach but it took 1 day to come along this way. Here my solution CodeChef: Practical coding for everyone

Hello,
Can you tell me what is wrong with my solution…
I tried to count all the invalid sub sequences and finally i subtract it from total sub array…

Got correct ans for every possible test cases in my mind…

But got wrong ans somehow…

It will be kind if anyone find a bug here or the test cases that i am getting wrong for…

Here is my solution :
http://codepad.org/ubaSqrvy

https://www.codechef.com/viewsolution/31511874
can you please check i was getting wa in subtask 2…

Wait for 2 hrs as cf contest is starting in 5 minutes :slight_smile:

ok cool

I am also getting WA in subtask 2. There is no integer overflow issue. My approach is
1.Mark which numbers in the given array can be xpressed as p^2-q^2 in the success array.
2.calculate total number of possible contiguous subsequences that equals n*(n+1)/2.Store it in variable ans.
3.from ans subtract all those contiguous subsequences that cannot be expressed in the given form.That happens only when the subsequence contains a single 2 as one of its factors and rest are odd.
4.So I scan the array,stop at each element of the array that cannot be expressed as p^2-q^2 and check to see how many odd numbers are there to it’s left and to it’s right. The left odd number count is stored in k along with that number itself and the right odd count is stored in variable “count”. Then i subtract k and count and k*count from ans to arrive at the final answer.

Is there anything wrong with my approach??I am really unable to see through it.I provide the link to my code
CodeChef: Practical coding for everyone.

Note: I have got full marks on the problem due to some hard coding but I want to what is wrong with the given approach.
Thanks to advance to the person who will kindly help me…

Your approach is O(N^2).