You are not logged in. Please login at www.codechef.com to post your questions!

×

Max Subarray GCD - Editorial

4
2

Prerequisites : Binary Search , GCD Properties

Difficulty : Easy - Medium

Expected Complexity : O(N * logn * p) , p = max number of steps to calculate GCD.

Editorial :

The most basic property of GCD is : gcd(i , j , k) = gcd(i , gcd(j , k)). Also , gcd(i,gcd(j,k)) <= gcd(j,k). Most part of our solution is based on this.

The first thing we can see is that if a subarray of size Q has gcd value >= K , then we can for sure find a subarray of size < Q whose gcd value is >= K. Once we know this , we can binary search on the length of the subarray in the following way :

SOLVE(L , R):
    mid = (L + R + 1) / 2
    if poss(mid , K) :
        return SOLVE(mid , R)
    else :
        return SOLVE(L , mid - 1)

Now, we just need to create our poss() function , which takes in the length of subarray we are checking for and the minimum gcd value we are looking for as parameters. For every index i in [0,N - length] , we need to check if the subarray [i , i + length - 1] has a gcd value >= K. If there is any index which satisfies , we will return true. Else we return false.

To check , we could use a segment tree which stores gcd value for every segment. The overall complexity would be O(N * logn * logn * p) , which would eventually TLE as segment tree comes with a high constant factor. We can also calculate this in O(N * p) using a very simple trick.

Divide the entire array into blocks of "length of subarray". Maintain two arrays suffix and prefix. Suffix[i] denotes the value of gcd from [i .. j] , where j is the end index of the block in which i lies. Similarly , Prefix[i] denotes the value of gcd from [a .. i] , where a denotes the starting index of the block in which i lies. This can be calculated easily in linear time.

Now how does this exactly help us ? For any index i , we can calculate the GCD of the subarray [i .. i + length - 1] by calculating the gcd of [i .. j] and [j + 1 .. i + length - 1] , where j is the ending of the block in which i lies. Thus for every index i , gcd value is gcd(suffix[i] , prefix[i + length - 1]). Our poss() function works in O(N * p) and we are calling it at most logN times , hence the total time complexity is O(N * logN * p).

This question is marked "community wiki".

asked 25 Nov '15, 13:17

himanshujaju's gravatar image

6★himanshujaju
251310
accept rate: 0%

edited 26 Nov '15, 12:33

admin's gravatar image

0★admin ♦♦
19.8k350498541


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 :) https://www.codechef.com/viewsolution/8829901

link

answered 02 Dec '15, 11:42

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

edited 02 Dec '15, 11:42

@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.

link

answered 01 Dec '15, 19:31

rajat1603's gravatar image

7★rajat1603
1.0k113
accept rate: 4%

Hi

Thanks for the editorial. I am unable to understand the trick that you have mentioned which doesn't involve segment trees. Can you help me with that?

Thanks.

link

answered 26 Nov '15, 10:56

rishabhshah's gravatar image

2★rishabhshah
29311
accept rate: 0%

2

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 http://ideone.com/UKdXBa

(26 Nov '15, 19:26) rajat16037★

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

(01 Dec '15, 11:55) rishabhshah2★

I used sliding window with segment tree.

link

answered 27 Nov '15, 01:17

rahul_nexus's gravatar image

3★rahul_nexus
7741923
accept rate: 13%

Thanks for the editorial

link

answered 16 Jan '16, 03:07

google_shiva's gravatar image

0★google_shiva
21
accept rate: 0%

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

link

answered 26 Nov '15, 18:58

pranavg189's gravatar image

2★pranavg189
261
accept rate: 25%

1
(26 Nov '15, 19:24) rajat16037★

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.

link

answered 26 Nov '15, 20:55

mukul_chandel's gravatar image

2★mukul_chandel
561
accept rate: 42%

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

link

answered 26 Nov '15, 21:42

theweblover007's gravatar image

2★theweblover007
10116
accept rate: 0%

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

(27 Nov '15, 19:34) himanshujaju6★

My O(N*N) soln passed https://www.codechef.com/viewsolution/8827971
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

link

answered 26 Nov '15, 22:48

sanket407's gravatar image

4★sanket407
4849
accept rate: 10%

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

(27 Nov '15, 19:34) himanshujaju6★

I could not understand concept of Binary Search here. Why Binary search is performed here?
Can somebody explain me?

link

answered 01 Dec '15, 12:51

ankurverma1994's gravatar image

4★ankurverma1994
415114
accept rate: 8%

Please include the link to practice and contest.

link

answered 01 Dec '15, 21:17

theweblover007's gravatar image

2★theweblover007
10116
accept rate: 0%

ocenemap sataus Travel Wisata Pulau Tidung

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

link

answered 24 Dec '15, 15:51

jones13's gravatar image

0★jones13
1
accept rate: 0%

ewipelun bezoew Pulau Tidung Travel Agent

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

link

answered 24 Dec '15, 15:52

jones13's gravatar image

0★jones13
1
accept rate: 0%

omonudip sopoux Sewa Apartemen Harian Depok

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

link

answered 24 Dec '15, 15:53

jones13's gravatar image

0★jones13
1
accept rate: 0%

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

link

answered 16 Jan '16, 02:06

maverick_10's gravatar image

3★maverick_10
1
accept rate: 0%

Thanks for the editorial

link

answered 16 Jan '16, 03:06

google_shiva's gravatar image

0★google_shiva
21
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×1,672
×1,038
×319
×50
×46

question asked: 25 Nov '15, 13:17

question was seen: 5,844 times

last updated: 16 Jan '16, 03:07