Sum and GCD Editorial

editorial
, , ,
1

Question : -
Divison 1
Division 2

Now first we think the basic approach and how to do that?

Now gcd of two elements is always min or equal to gcd of single element –
see gcd(4,7) < gcd(4) OR gcd(4,8) <= gcd(4) OR gcd(8)

Now most of us think that we can take max value on one side and take gcd of all values ,
ie. a= {1,2,3,4,5} so max sum will be gcd(5) + gcd(1,2,3,4) = 6

But this is wrong in many cases , lets take an example a = {10,14,15}
Now according to our approach answer will be gcd(15) + gcd(10,14) = 15+2=17 , but the correct answer is 19 how —> gcd(14)+gcd(10,15) = 14 + 5 = 19.

so for 20 marks we can try for each element and find the max answer,
Steps : -

  1. Convert given array to set, so the only unique value is present
  2. if( the set size is 1 that means it contains only same value)
    output will be twice of element.
    example : ={2,2,2,2,2,2} set = {2} answer = 4 [ gcd(2) + gcd(2,2,2,2,2) ]
    else
    try for each element
    example = {2,4,2,6,4,5,8} , set = {2,4,5,6,8}
    2+gcd(4,5,6,8) = 2 + 1 = 3
    4+gcd(2,5,6,8) = 4 + 1 = 5
    5+gcd(2,4,6,8) = 5 + 2 = 7
    6+gcd(2,4,5,8) = 6 + 1 = 7
    8+gcd(2,4,5,6) = 8 + 1 = 9
    So max answer is 9 , But the complexity of this approach is O(n^2).

See Solution : Brute Force ( O(N^2) solution)

But how to do that with O(N) complexity.
We have to calculate GCD of all element except current element (OR excluding the i’th element from an array(set))
We use concept of prefix and suffix array and we can use concept of this article also
(after my submission I found this)
see - Geeks-for-geeks

Now we can do this in O(N) complexity.
See : O(N) Solution [ prefix and suffix approach]

if u like this please upvote and if u want further explanation, I will be happy.

8 Likes
2

1)You should prove in a clear way why we always take only 1 element on 1 side.
2)You don’t need to check for all the values and create the prefix and suffix arrays, answer is simply max(gcd(max_value)+gcd_of_rest , gcd(2nd_max_value)+gcd_of_rest) :slight_smile: You should prove it :slight_smile:

10 Likes
3
  1. If we take multiple values in one side the resultant gcd is always less or equal to single element.
  2. bhai ye approach real me dimag me nhi aayi.
    BTW thanks for this , :slight_smile:
4

Thanks for @anon55659401 for another approach
here u go – Karan approach

5

@ssrivastava990 Bro is there any mathematical proof of taking 1 element on 1 side and rest in other side or its intuitive …??

6

There is another solution
let a1 be in a subsequence whose gcd is g
now g can only take values of divisors of a1, so put divisors of a1 in one subsequence and all others in other subsequence , find gcd of other subsequence , ans would be max of these over other variables.
Time complexity => N*(no. of div(a1))
Need to handle trivial case when all elements are equal

1 Like
7

You missed a very impotant point. Not to take single element on side but rather take all elements of that value together. Best achievable by removing duplicates from array first :smiley:

8

See GCD is maximum only if there are similar elements na. Adding a dissimilar element, would just decrease the GCD. Let’s say the max element is MAX. The rest elements can have any GCD from 1 to <MAX so answer will be at least MAX+1. But if you put MAX alongwith some other dissimilar element, it will make the GCD at least MAX/2 if not lesser, and now the other half would have to be at least MAX/2 + 1 if it has to surpass the previous max value of MAX+1 that we got, which is not possible.

1 Like
9

Hello,this is my greedy approach of the same problem.
this code did not pass one test case in constraint 1 and 3 test case in constraints 2.
I don’t know where is the problem, I tried almost every corner case but don’t know where is this going wrong.
Please let me know if anyone can help.

https://www.codechef.com/viewsolution/24777247

10

Are you sure about O(n),as i can see there is n*log(n) complexity.

11

brute force approach also works if used with a little “jugaad”. I am checking all possible solutions using recursion, but breaking the recursive calls as soon as I find that the answer can be found without making further recursive calls.

12

Rigorous proof… Let x = \max_1(S) + \gcd(S\setminus\{\max_1(S)\}), y = \max_2(S) + \gcd(S\setminus{\max_2(S)}), where \max_1(S), \max_2(S) are the largest and second largest elements of the set S. (Assume all the duplicates were removed.) Let A, B be an arbitrary partition of the set, and assume WLOG that \max_1(S) belongs to A. If there are no other other elements in A besides for \max_1(S), then \gcd(A) + \gcd(B) = x. Otherwise, \gcd(A) \leq \max_1(S)/2, because all other elements are < \max_1(S). Meanwhile, \gcd(B) \leq \max_2(S) because all elements of B are \leq \max_2(S). If \gcd(B) = \max_2(S), then \gcd(A) + \gcd(B) = y, otherwise \gcd(B) \leq \max_2(S)/2, so \gcd(A) + \gcd(B) \leq \max_1(S)/2 + \max_2(S)/2 < \max_1(S) < x, and this certainly doesn’t achieve the max. This proves the max is either x or y.

5 Likes
13

My thought process was slightly different, first I observed and verified that the largest and 2nd largest number in the input array can never be together. If we put the largest and 2nd largest number in the same bracket we will never be able to achieve max. sum.
I started by removing the repetitions and sorted, if there’s only single element (call it x) then print 2x.
{GCD(8,8) = 8, GCD of two same numbers is always that number}
If you get two distinct numbers then simply add them and print the result. Since we have sorted the array we will get something like this {a, b, c, d, e, f} all in ascending order.
GCD(a, b, c, d) <= a and GCD(e,f) <= e (case 1 where we’ve taken max and 2nd max together)
GCD(a, b, c, d, e) <= a and GCD(f) == f (case 2)
Now just by looking at the equations we can say that putting max and 2nd max in same bracket is not optimal.
if we just assume that case 1 produces max. results (i.e. a+e, note : when GCD(e,f) == e then f=ne where n!=1 cuz there are no repetitions) and case 2 produces min results (i.e. 1+f)
a+e < 1 + ne (f == ne)
on reducing the equation we get
a < 1 + (n-1)*e (note : n >= 2) and this equation is true
and also one of the two brackets should only contain the max or the second max element.
In cases like {10, 14, 15} we have to split it like {14} and {10, 15}.
we will simply calculate GCD from the first element to the 3rd last element (inclusive) , let’s call that g. Here v[n-1] refers to the last element or max element and v[n-2] refers to 2nd max element. we’ll use an if statement to check which combination produces maximum output.

int gcd_a = __gcd(g,v[n-2])+v[n-1];
int gcd_b = __gcd(g,v[n-1])+v[n-2];
if (gcd_a >= gcd_b)
		cout << gcd_a << '\n';
	else
		cout << gcd_b << '\n';

Link to my solution : SUMAGCD

14

I already mention to convert into set.

15

Hello Karangreat234,please review my code
please send me some test inputs to fail my code

https://www.codechef.com/viewsolution/24828838

16

please review my code
please send me some test inputs to fail my code

https://www.codechef.com/viewsolution/24828838

17

please review my code
please send me some test inputs to fail my code

https://www.codechef.com/viewsolution/24828838

18

check for :-
4, 4, 4, 4
10, 15, 14
4, 4, 7, 6
6, 12, 16, 18
3, 8, 9
100, 100, 150, 300

19

Hello Wingman_7 sir,

Thanks for you input

I forgot to clear one of my collection for every test case that is the reason it has failed

after adding that line

i got below results

6
4
4 4 4 4
3
10 15 14
4
4 4 7 6
4
6 12 16 18
3
3 8 9
4
100 100 150 300
8
19
9
22
11
350

but still 2 test cases are failing from large input can you provide that input

practice section link

https://www.codechef.com/viewsolution/24862289

one more thing they are just saying WA,if they mention NZAC then i could caught this

1 Like
20

Checking all of them can be done in O(n)
No need to prove 2nd point