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
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
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
Okay thanks
1 Like
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
I used loop for m to 1 and got tle 
, thank you bhaiya for ur approach
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
@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?
That solution is wrong , It passed because the test cases are weak An example TC, Answer should be 4 but mine is giving 3.
1
3
12 5 3
I do not know why your code accepted but I think it is wrong to approach.Maybe I am wrong .
My solution is accepted, but this is obviously wrong solution.
It fails on the test case-
1
3
11 7 6
My output- 3
Expected output - 4
Here is my code-
Code
#include<bits/stdc++.h>
using namespace std;
int fun(int elem, int res){
int ans = __gcd(elem, res);
ans = max(ans,__gcd(elem, res - 1));
ans = max(ans,__gcd(elem, res + 1));
return ans;
}
int maxGCD(int A[] , int N)
{
int x = A[0];
int y = A[0] + 1;
int z = A[0] - 1;
for(int i = 1; i < N; i++){
x = fun(x, A[i]);
y = fun(y, A[i]);
z = fun(z, A[i]);
}
int mx = max({3, x, y, z});
return mx;
}
int main()
{
int T;
cin>>T;
while(T--){
int N;
cin>>N;
int A[N];
for(int i = 0; i < N; i++){
cin >>A[i];
}
cout << maxGCD(A, N) << "\n";
}
}
Can someone please tell, what changes do I need to make in my code or is it simply that greedy fails?
Anyone?