redusk's blog

How to solve Max Subarray GCD (ICPC Preparatory Series by Codechef 25/11/2015)?
By redusk, history, 8 years ago, In English

Dear all,

here is the link for the problem. My solution involved using segment tree. I have read the editorial and understood the basic idea. But in the editorial it is written that we cannot use segement tree as it will result in TLE. I am unable to understand the trick(not using segment tree) that is mentioned in the editorial which runs in linear time to store the GCD of the subarrays. Could someone help me with understanding the solution of the editorial? If you have any other solution please let me know.

Thank you.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to say that there are lots of online judges these days, but no one can still match the editorials of Topcoder :(

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it +19 Vote: I do not like it

Here's a seemingly unrelated problem:

I have a stack and I want to support three operations:

  1. add a number onto the top of the stack
  2. remove a number from the top of the stack
  3. query the gcd of all numbers currently on the stack (or 0 if no numbers are on the stack).

I'll leave this problem as an exercise.

Now, I hope you're familiar with the idea of simulating a queue with two stacks (if not see here). Hopefully, that should give you an idea of how to complete the solution for this problem.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use sparse table rather than segment tree to compute gcd of a range is O(p), which reduces the total complexity to O(n * logn * p) .

you can see my submission : https://www.codechef.com/viewsolution/8828449

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Our team used segment trees in the same question with two pointers , particularly known as the sliding window algorithm . Here is the link to the solution .
Feel free to ask if something is not clear

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Hi , i am the author of the problem and here is the expected solution

We can perform a binary Search on answer 

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

the answer is l — 1

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

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.codechef.com/viewsolution/99498627

You can solve it using Binary Search and a special type of Queue that allows push() pop() and gcd() in O(1) each, it is implemented using 2 stacks, explanation is present in the submission link.

→ Reply