How To Solve Maximum GCD , ( CP Potpourri Prelims )

6

Interesting! Can you please share your code?

7

I take a cartesian product, all combinations of numbers in the current set and 3 possible values of next element.
But approach suggested by kck_rocks below is much better.

In any case, your approach should also not give WA unless there is some implementation bug.

8

I dont know …there is no implementation bug…BTW thanks for your speedy response

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