CMED03-Editorial

PROBLEM NAME:

LCM ARRAY

PROBLEM LINK:

https://www.codechef.com/CMED2021/problems/CMED03

DIFFICULTY:

Medium

PREREQUISITES:

LCM and Dynamic Programming

PROBLEM:

You are given NN integers to find the length of the longest subarray whose LCM is equal to the product of elements in the subarray.

Solution:

Problem Idea: Calculating efficiently longest subarray which ends at i for each i. LCM of all integers in that subarray is equal to the product of all integers in that subarray.

Let Dp[i] denotes the length of the longest subarray ending at i and satisfying the property that the product of all integers of the subarray is LCM of the subarray.

If we know Dp[i-1] , can we calculate Dp[i] ?

Yes , Dp[i] = min ( Dp[i-1]+1 , i - Cal(i) ) (Array indexing starts from 1) , where Cal(i) calculates the last index encountered which is not co-prime to A[i] while travelling left from i. If no such index is found , then 0 is returned.

Let A[] = 2 3 5 4 9 5 10 , then Cal(i) for i=1,…7 will be 0,0,0,1,2,3,6.

Dp[] = 1 2 3 3 3 3 1

Ans=max(Dp)=3

How to calculate the Cal(i) efficiently ?

A number is not co-prime to another number if there exist a common gcd [ or a common prime factor ].

Ok, then we need to factorise A[i+1] , let say we wrote A[i+1] = p1e1 * p2e2 * p3e3 * … * pkek , where pi is prime number.

Now we need to pick up the latest index where any of these factors came.

But how can we do it efficiently ?

Look at the constraints and you will notice that A[i] <= 106 , so each prime is less than 106

We can use an array of size 106{let’s call it P[]} to find out the latest position. Look at the pseudo code for Cal(i).

Pseudo Code

	int Cal(int idx)
		int ret_val = 0
		Factors = Factorise(A[idx]) //Factorise will only return prime factors
		for(int i = 0 ;i< Factors.size() ;i++ )	//iterating through all factors
			ret_val = max( ret_val , P[Factors[i]] )  //P is an array of size 10<sup>6</sup>
			P[Factors[i]] = idx			//latest index for prime number Factors[i] is updated to idx.
		return ret_val

What will be our answer ?

Max ( dp[i] ) for all i

Some PitFalls

You need to precompute factors of each numbers [ from 1 to 106 ]. Reason : Calculating it in run time may lead to TLE because :
For factoring any number , you need to iterate over all prime numbers less than sqrt(number). In worst case this number is close to 150. Hence total number of steps will be approximately 150 * 100000 for each Test case. So, for 50 test cases this goes to 75 * 107 which will time out.

Another Way of understanding the Solution
Actually you can also interpret the solution as an application of two pointer method.

Two pointer method
Assume that [i, j] is the your current valid segment/ window. If you go from i to i + 1, and the segment [i + 1, j] still remains a valid segment, then you can apply this method.
So you can consider that when going from left to right, if you maintain a pointer for the right end of the good segment, then the right end of the segment always keeps on increasing.

Basically in other words, you can treat the segment as a window representing a valid solution. You need to support fast addition and deletion of elements from the window. But you will notice that
if your right pointer always increases then you will never need to delete the right end of the segment. You will always delete the left end and will always add the right end of the segment.

It is very easy to prove that complexity of this method is O(n), as that right pointer is always increasing and hence can make at most n iterations, So overall there could be at most n + n iterations over both left and right ends of a good segment which amounts to total O(n) operations. This method is called window two pointer method.

Sometimes this method is called sliding window algorithm too.

How to apply it in our problem
You can notice that if the segment [i, j] is a valid segment (ie. a segment containing numbers having their lcm equal to their product), then the segment [i + 1, j] is also valid.
When we want to extend the right end of our current segment (ie. we are looking at validity of segment [i, j + 1] considering that we know that segment [i, j] is valid), we need to check whether the current number has any common divisor (prime divisor will also work) with any number in the window. This check can be done easily by using the Cal array as explained above.

Overall complexity of this method is O(N).

using namespace std;

#define LL long long
const int N = 1e6 + 5;
int pre[N], prime[N];

int f(int x, int i) {
    int pos = -1;
    while(x > 1) {
        int z = prime[x];
        pos = max(pos, pre[z]);
        pre[z] = i;
        while(x % z == 0) x /= z;
    }
    return pos;
}

void solve() {
    int n, ans = 0, p = -1, x; cin >> n;
    memset(pre, -1, sizeof pre);
    for(int i = 0; i < n; i++) {
        cin >> x;
        p = max(p, f(x, i));
        ans = max(ans, i - p);
    }
    cout << (ans > 1 ? ans : -1) << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    for(LL i = 2; i < N; i++) {
        if(!prime[i]) {
            prime[i] = i;
            for(LL j = i * i; j < N; j += i) 
                if(!prime[j])
                    prime[j] = i;
        }
    }

    int tt; cin >> tt;
    
    while(tt--) solve();
}

Does this contest took place
As I registered for it earlier and at given time I came to give it but it was not present in present contest field and currently also not showing in past field
Or is it just for me

yes i took place yesterday from 8pm to 11pm

Also for now it is not visible in past contest section ?
why ?

1 Like

Hello rushi2001,
First, it was an open contest but later on, it was called as closed contest so that’s why it is not visible now
Sorry for any inconvenience!

1 Like

@uttam_singhk
Thx buddy for the update

1 Like

Your Welcome @rushi2001