GCDQ - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu

DIFFICULTY:

EASY

PRE-REQUISITES:

GCD, Precomputation

PROBLEM:

You are given an array A of integers of size N. You will be given Q queries where each query is represented by two integers L, R. You have to find the gcd(Greatest Common Divisor) of the array after excluding the part from range L to R inclusive (1 Based indexing). You are guaranteed that after excluding the part of the array remaining array is non empty.
1 ≤ N, Q ≤ 100000

EXPLANATION:

If you do it naively(ie. calculating GCD of remaining array for each query), the worstcase complexity will be O(N * Q).
Let’s denote by G(L, R), the GCD of AL, AL+1 … AR. We can observe that for query [L, R], we need GCD of G(1, L-1) and G(R+1, N).
So, we precalculate prefix and suffix gcd arrays.
If we have:
Prefixi = GCD of A1, A2 … Ai
Suffixi = GCD of AN, AN-1 … Ai
answer to query [L, R], would be GCD of PrefixL-1 and SuffixR+1.

We can calculate prefix and suffix arrays in O(N) if we notice that:
Prefixi = GCD(Prefixi-1, Ai)
Suffixi = GCD(Suffixi+1, Ai)

Pseudo Code for building prefix and suffix arrays:

n,a=input
pre[n],suf[n]

//base case
pre[1]=a[1]
suf[n]=a[n]

for i=2 to n:
    pre[i] = gcd(pre[i-1], a[i])
    
for i=n-1 to 1:
    suf[i] = gcd(suf[i+1], a[i])

So, overall complexity would be O((N + Q) * K), where K is a constant factor for gcd calculation.

ALTERNATIVE SOLUTION:

Use segment trees for range gcd queries. But note that a factor of log N will be increased in complexity.

SOLUTIONS:

Setter’s solution
Tester’s solution

4 Likes
2

Can anybody see my solution link and tell what is the problem with it. I have used exactly the same technique written here.First I tried using Scanner but resulted in TLE in the second subtask so I switched to BufferedReader method but it keeps on giving the Runtime Error RZEC.

3

I used segment trees for this one. Now I feel like I shot a fly with a cannon. :stuck_out_tongue:

Solution: http://www.codechef.com/viewsolution/5686962

6 Likes
4

Getting a runtime error SIGSEGV

Can anyone please tell me the reason for that?

Code : http://ideone.com/QCJXzv

5

What is optimal way to calculate GCD of two number Prime factor method or division method or something else ?

6 
function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

this is the pseudo code for euclid algorithm to find the gcd of two number in logarithmic time…

you can also use inbuilt function __gcd(a,b) in cpp

here is the cpp implementation of the function

int gcd(int a,int b){

  if(b == 0)
      return a ;
    else
      return gcd(b,a%b) 

}
1 Like
7

Why did i get a TLE with exact same solution ?

8

It is ok… so did I .-.

9

no problem dude i also thought but constraints let me to drop the idea and i finally formulated the mentioned solution …

10

Well, your conditions are wrong and its clearly visible:
For example:
if(l==0 && r==n-1)
{
printf(“1\n”); //how do you know the gcd of entire array is “1”?
}

Now, perhaps you were lucky and before getting WA, some test case made upto this condition which gave you SIGSEGV:
else if(l==0)
{
printf("%d\n",suffix[r+1]); //if r == N, you will access (N+1)th element of array!
}

I didn’t went further into your code after this condition, sorry :smiley:

11

same here i did the exact same thing and got TLE…Whats the point of this explanation then??

12

setter’s and tester’s solution link is not working.

13

I’m always getting TLE…help to optimize the code would be appreciated…please tell me what to do. Code Link:http://www.codechef.com/viewsolution/7126221

14

what should be returned if low and high of segment tree have no overlap with querylow and queryhigh ?
Or
Someone give me a link to the solution using segment tree

15

why problem is not visible in practice section :frowning:

16

If in case someone want segment tree solution in c++. link-https://www.codechef.com/viewsolution/14754012