How To Solve Maximum GCD , ( CP Potpourri Prelims )

9

https://www.codechef.com/viewsolution/42870637-This is my code
It is not commented… :frowning:
I hope you can find the bug in my code

10

Here is my code

#include<bits/stdc++.h>
using namespace std;
bool all_ok(int x,int arr[],int n)
{
for(int j=1;j<n;j++)
{
if((arr[j]%x)==0 || (arr[j]%x==1) || (arr[j]+1)%x==0)
continue;
else
return false;
}
return true;
}
int find_gcd(int g,int arr[],int n)
{
int ans=1;
for(int i=1;i*i<=g;i++)
{
if(g%i==0)
{
if(all_ok(i,arr,n))
{
ans=max(ans,i);
}
if(all_ok(g/i,arr,n));
{
ans=max(ans,g/i);
}
}

}
return ans;

}
int main()
{
int t;
cin>>t;
while(t)
{
int n;
cin>>n;
int arr[n];
for(auto &x:arr)
{
cin>>x;
}
sort(arr,arr+n);
int ans=find_gcd(arr[0],arr,n);
ans=max(ans,find_gcd(arr[0]+1,arr,n));
ans=max(ans,find_gcd(arr[0]-1,arr,n));
cout<<ans<<endl;
t–;
}
}

Unfortunately they are not allowing me to share my submission link…Hope you can find out my bug —>kindly follow the steps I mentioned…you will be able to grasp my approach

11

Then after that how do you decide which is your final ans…?

12

oh sure ! here it is code

1 Like
14

Good debugging question
Remove the semicolon after if
https://www.codechef.com/viewsolution/42872993

15

This is what our team did. We considered the max of gcd(m,a[i]) , gcd(m,a[i]+1), gcd(m,a[i]-1) , max of gcd(m+1,a[i]), gcd(m+1,a[i]+1), gcd(m+1,a[i]-1) and max of gcd(m-1,a[i]),gcd(m-1,a[i]+1),gcd(m-1,a[i]-1) separately, where m is the minimum element in the array. We consider the min of each of these max values separately, as i varies from 0 to n-1. And finally, the answer is the maximum of the original gcd and these three values obtained.

1 Like
16

Thanks , …

17

Can someone pls tell what’s wrong with our solution for the Boars of Armorica ?CodeChef: Practical coding for everyone. Tried doing with bitmask DP.

18

My solution got AC link

20

I think there is some bug in your implementation.
My team followed the same logic and got AC

21

Ya , cubercoder Sir has pointed it out

23

was this code accepted? If yes, can you share the link to the code

24

Can you tell me that why is taking 3 explicitly necessary , like why isnt dp itself knowing that answer cant be less than 3 , my solution in which I didnt wrote the condition of 3 gave me a Wrong Answer . Whereas the solution containing 3 gave me a right answer . Moreover can I have a Test Case where we need 3 to be the lower limit.

1 Like
25

You can have mine it is implemented with the same logic the only difference is that ans[i][0] is a[i]-1, ans[i][1] is a[i], ans[i][2] is a[i]+1
https://www.codechef.com/viewsolution/42876751

1 Like
26

Okay thanks

1 Like
27

The gcd will always be the factor of the smallest number of the array.
Let the smallest no. be X. So X-1,X,X+1 will be only three possibilities we have to consider,so find out all the factors of these three no. and sort then in dec. order.
Now we just have to check which of these factor can divide all the no. of the given array.To do this for each A[i] we have three possibilities (A[i]-1,A[i],A[i]+1) just check if the any of these three no. is a multiple of that
no. or not.
My code:CodeChef: Practical coding for everyone

28

I used loop for m to 1 and got tle :slightly_smiling_face:, thank you bhaiya for ur approach

29
31

Your solution is wrong. It got accepted because test-cases were weak.

TEST_CASE 
1
10
12 13 17 15 3 3 3 5 11 17

The answer for this test-case is 4 but your code gives 3

32

@vaibhav_717
hey can you tell me the complexity of your code if i couldn’t understand. what is the maximum no of elements we can have in the set ie factors of(a[i],a[i]-1,a[i]+1) where a[i] is smallest element which can be upto 1e9 in which case our set can have large size which may result in tle can you clear this?