Can anyone share their approach for Maximum GCD , ( CP Potpourri Prelims ) .

Thank You

My Approach:

Traverse array from left to right:

- Use a set to store all possible GCD that the array can have.
- At each step A[i] of traversal, take gcd of each element of set with each of A[i], A[i-1], A[i+1] and update these in the set.

This is basically based on the assumption that the set size will never get too big. For example, if 3 variations of first number have K distinct factors in total, the set at any point of time will not have more than K elements. Note that K cannot be very large.

I would be interested to see other approaches as well.

I got WAâ€¦here is my approach

Sort the array.

Take the smallest element

Consider 3 cases.

1)smallest element remains unchanged

2)smallest element increased by 1.

3)smallest element decresed by 1.

For each case, find out the factors of that element, and check whether that factor divides the remaining numbers if the allowed operations are performed on themâ€¦if this happens then that factor is a possible gcd of the entire array.

Find out the maximum among those factors satisfying the above criteria

How do you find out all possible gcd?

We can use dynamic programming to solve this problem. The states will be as follows-

base case is if there is only one element -

dp[0][0]=ar[0];

dp[0][1]=ar[0]+1;

dp[0][2]=ar[0]-1;

dp[i][0] -> means im taking ar[i] as my current number and storing the max gcd possible from previously stored results , i.e, the transition will be

dp[i][0]=max({__gcd(ar[i],dp[i-1][0]),__gcd(ar[i],dp[i-1][1]),__gcd(ar[i],dp[i-1][2])});

Similary ,

dp[i][1] -> means im taking ar[i]+1 as my current number and storing the max gcd possible from previously stored results, i.e, the transition will be

dp[i][1]=max({__gcd(ar[i]+1,dp[i-1][0]),__gcd(ar[i]+1,dp[i-1][1]),__gcd(ar[i]+1 ,dp[i-1][2])});

similarly,

dp[i][2]-> means im taking ar[i]-1 as my current number and storing the max gcd possible from previously stored results, i.e, the transition will be

dp[i][2]=max({__gcd(ar[i]-1,dp[i-1][0]),__gcd(ar[i]-1,dp[i-1][1]),__gcd(ar[i]-1,dp[i-1][2])});

thus our final ans will be ->

ans=max({3ll,dp[n-1][0],dp[n-1][1],dp[n-1][2]});

here 3 is taken bcz i can get a minimium gcd of 3 for any array.

Interesting! Can you please share your code?

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.

I dont know â€¦there is no implementation bugâ€¦BTW thanks for your speedy response

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

Then after that how do you decide which is your final ansâ€¦?

Good debugging question

Remove the semicolon after if

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

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.

Thanks , â€¦

Can someone pls tell whatâ€™s wrong with our solution for the Boars of Armorica ?Solution: 42874189 | CodeChef. Tried doing with bitmask DP.

I think there is some bug in your implementation.

My team followed the same logic and got AC

Ya , cubercoder Sir has pointed it out

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