MAX GCD POTPOURRI

[misharta]

Why my code is not getting accepted? Can anyone help in debugging it?
Question Link : CodeChef: Practical coding for everyone
Solution Link : D4eCUM - Online C++0x Compiler & Debugging Tool - Ideone.com

[adarsh08x]

I don’t understand you code but here’s my accepted solution Link

[dhruv788]

See, I dont have an answer of why at present but after replacing you cout statement with this one

cout<<max(max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]),3);
it gives a AC
here is the link
https://www.codechef.com/viewsolution/42876886
Link to the comment from where i got to knew about this

How To Solve Maximum GCD , ( CP Potpourri Prelims )

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 s…

[misharta]

Thank You for helping me out .
But what I don’t understand is why is it necessary to take 3 in the max statement .
I think DP would take all the cases into its consideration.

[cubefreak777]

As I guessed, this solution is incorrect, it passed just cause the test-cases were weak, check this.

TEST_CASE

1
7
12 5 11 3 11 13 7

Correct output is 4 but following this approach will give 3. @misharta

[dhruv788]

Thanks mann , I got the mistake.