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.
1 Like
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
1 Like
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.
1 Like
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
https://www.codechef.com/viewsolution/42870637-This is my code
It is not commented… 
I hope you can find the bug in my code
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.
1 Like
Thanks , …
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.
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