Hi,↵
Recently i was solving a problem on codechef related to GCD (https://www.codechef.com/JUNE19A/problems/SUMAGCD). I developed an algorithm using Greedy Approach as follows:↵
I created two placeholders, x and y, for the final result to be obtained. Since we have to bifurcate the numbers into sets, for which x will represent the GCD of all elements in set 1 and similarly y will represent the GCD of all elements in set 2.↵
Now as per the question statement, any number can be in set 1 or set 2.↵
My approach is to traverse the array linearly and for every element, try the following three possibilities:↵
Let the element by J:↵
Case 1: J is attached to set 1 and set 2 remains as it is. Let the new GCD of two sets be X1 and Y1.↵
Case 2: J is attached to set 2 and set 1 remain as it is. Let the new GCD be X2 and Y2.↵
Case 3: We concatenate set 1 and set 2 and replace it with set 1 and create new set 2 with only J in it. Let the new GCD be X3, and Y3.↵
Now of all the three cases, we choose the case with the highest sum.↵
At the end of the traversal, we should have the result with the maximum sum.↵
↵
↵
But this approach is giving an incorrect answer for one of the subtest.↵
↵
Can anyone point out the flaw in this approach?↵
Thanks in advance.
Recently i was solving a problem on codechef related to GCD (https://www.codechef.com/JUNE19A/problems/SUMAGCD). I developed an algorithm using Greedy Approach as follows:↵
I created two placeholders, x and y, for the final result to be obtained. Since we have to bifurcate the numbers into sets, for which x will represent the GCD of all elements in set 1 and similarly y will represent the GCD of all elements in set 2.↵
Now as per the question statement, any number can be in set 1 or set 2.↵
My approach is to traverse the array linearly and for every element, try the following three possibilities:↵
Let the element by J:↵
Case 1: J is attached to set 1 and set 2 remains as it is. Let the new GCD of two sets be X1 and Y1.↵
Case 2: J is attached to set 2 and set 1 remain as it is. Let the new GCD be X2 and Y2.↵
Case 3: We concatenate set 1 and set 2 and replace it with set 1 and create new set 2 with only J in it. Let the new GCD be X3, and Y3.↵
Now of all the three cases, we choose the case with the highest sum.↵
At the end of the traversal, we should have the result with the maximum sum.↵
↵
↵
But this approach is giving an incorrect answer for one of the subtest.↵
↵
Can anyone point out the flaw in this approach?↵
Thanks in advance.
