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

9 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: CodeChef: Practical coding for everyone

8 Likes
4

Getting a runtime error SIGSEGV

Can anyone please tell me the reason for that?

Code : QCJXzv - Online C Compiler & Debugging Tool - Ideone.com

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) 

}
2 Likes
7

Why did i get a TLE with exact same solution ?

8

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

9

setterā€™s and testerā€™s solution link is not working.

10

Iā€™m always getting TLEā€¦help to optimize the code would be appreciatedā€¦please tell me what to do. Code Link:CodeChef: Practical coding for everyone

11

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

12

why problem is not visible in practice section :frowning:

13

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

1 Like
14

It is okā€¦ so did I .-.

15

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

16

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:

17

#include <bits/stdc++.h>

using namespace std;

#define maxn 100000
int arr[maxn], pre[maxn], suf[maxn];

int main()
{
int t, sum=0;
cin >> t;

assert(t>=2 && t<=100000);

while(t--)
{
	int n, q, l, r;
	cin>> n >> q;
	sum += n;
	assert(n>=2 && n<=100000);
	assert(q>=1 && q<=n);
	int i;
	for(i=0;i<n;i++)
	{
	    cin>>arr[i];
	    assert(arr[i]>= 1 && arr[i]<=100000);
	}
    
	pre[0] = arr[0];
	suf[n-1] = arr[n-1];
	
	for(i=1;i<n;i++)
	{
		pre[i] = __gcd(pre[i-1], arr[i]);
	}
	for(i=n-2;i>=0;i--)
	{
		suf[i] = __gcd(suf[i+1], arr[i]);
	}
	while(q--)
	{
		cin >> l >> r;
		assert(l <= r);
		assert(l>=1 && l<=n);
		assert(r>=1 && r<=n);
		assert(r-l+1 != n);
		cout << __gcd(pre[l-1], suf[r+1])<<"\n";
	}
}
assert(sum <= 1000000);
return 0;

}

what is wrong in my code? it is just according to the explanation.

18

Iā€™m getting Runtime Error ( SIGABRT). Below is my code. Can anyone help?

       #include<bits/stdc++.h>
       using namespace std;
      #define eff ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      #define vi vector<int>

      int main(){
        eff;
        int t;
        cin>>t;
        
         while(t--)
         {
            int n,q;
            cin >> n >> q;

            vi v(n+1);

            for (int i = 1; i <= n; i++)
                cin >> v[i];

            vi pre(n+1);
            vi suff(n+1);
            pre[0] = suff[n+1] = 0;
            pre[1] = v[1];
           
            for(int i = 2; i <= n; i++)
            {
                    pre[i] = __gcd(pre[i-1],v[i]);
            }
         
             suff[n] = v[n];
            for(int i = n-1 ; i >= 1; i--)
            {
                    suff[i] = __gcd(suff[i+1],v[i]);
            }

            while(q--)
            {
                int l,r;
                cin >> l >> r;
                cout<< __gcd(pre[l-1] , suff[r+1]) <<"\n";
            }    

         }
        return 0;
    }
2 Likes
20

Try declaring Arrays Globally. I just declared them globally and got that accepted take a look
https://www.codechef.com/viewsolution/48517685