Greedy Approach not working

Правка en3, от CormoranStrike, 2019-07-12 15:16:44

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.

Теги gcd, greedy, #codechef

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский CormoranStrike 2019-07-12 15:17:59 76
en3 Английский CormoranStrike 2019-07-12 15:16:44 1 Tiny change: 'Hi\nRecently' -> 'Hi,\nRecently'
en2 Английский CormoranStrike 2019-07-12 15:16:23 1
en1 Английский CormoranStrike 2019-07-12 15:15:37 1281 Initial revision (published)