Max Subarray GCD - Editorial

It will be great if a code is provided for this method…

https://www.codechef.com/viewsolution/8830230
My O( N * sqrt(max(a[i])) ) solution for this. It still passed and I have no idea why.

Isnt the block idea a bit like that in Mo’s Algorithm ?

My O(N*N) soln passed
CodeChef: Practical coding for everyone
Check gcd of subarray starting at all i
If i get gcd of particular subarray and the length of that subarray is largest possible after that point in program then i stop checking .the statement :if(max==n-i) break; did this.
I guess for strong test cases i wud hav got TLE

I used sliding window with segment tree.

3 Likes

I could not understand concept of Binary Search here. Why Binary search is performed here?

Can somebody explain me?

@ankurverma1994 , we are doing a binary search here on the answer , if we have a subarray of size ‘X’ with gcd >= k , then we will also have subarrays of size X-1 , X-2… 2, 1 with gcd >= k and if we dont have any subarray of size X with gcd >= k , we we wont have subarrays of size > X with gcd >= k , so we can binary search on answer.

6 Likes

Please include the link to practice and contest.

Well

if segment tree gives TLE due to large constant factor so it can be solved using sparse table which is more efficient method than any one described here it is O(n log n) we use sparse table for range minimum so instead of storing minimum value we store gcd and at time of query we need to find gcd of two value according to L and R so if this question was to find gcd of range(L,R) then everything will be same only min function replaced by gcd function but in this problem at query time we need to find the range of sub array according to K we need to traverse back so it need some modification you can take a look at my solution :slight_smile: CodeChef: Practical coding for everyone

6 Likes

ocenemap sataus
Travel Wisata Pulau Tidung

atetih ebapik onoqid ucatum uwutud ipitil ipasib uxepik opasih ugisug owuseh izipik

ewipelun bezoew
Pulau Tidung Travel Agent

upeseb ajotik afopeg ahiteb uxapim eyiquj umureh igenil apaquh uresim osatub ivupef

omonudip sopoux
Sewa Apartemen Harian Depok

ixetem idaqeb orasuj onasej elaseb elinek akosef epopuh ofepuf etanih onuned ewopeb

Hi can anyone please help me in figuring out why I am getting TLE on this problem
My code passed using two pointer and segment tree but it gave tle with binary search and segment tree
https://www.codechef.com/viewsolution/9180833

Thanks for the editorial

Thanks for the editorial

2 Likes
1 Like

We can perform a binary Search on answer

while l < r:
mid = (l + r) / 2
if check(mid):
l = mid + 1
else:
r = mid

Now we just need to write an efficient check function
Now suppose we want to check if any subarray of size ‘X’ exists which has GCD >= K , To do this , we divide the array in blocks of size ‘X’ and calculate the prefix and suffix GCD for each block , this will help us calculating the GCD of any block of size ‘X’ in O(1) time with O(N) pre processing.
The complexity of this solution is O(N * LOGN * P) where P is time taken for calculating GCD

3 Likes

Yes , just that instead of the size being sqrt(N) , we divide into blocks of size of the length we are testing for.

I had tried a segment tree solution , and my brute didnt check for your “if” condition. Thanks for notifying though!

Thanks a lot for the code and the explanation. I understood it now.