SUMAGCD easiest Editorial

editorial
1

Editorial:

  1. Use set to store the unique elements from all the given elements.
  2. Find the GCD of all the unique elements(say X) except the last two elements i.e. maximum and second maximum elements.
  3. now find max from GCD (X, second maximum)+ maximum and GCD (X, maximum)+ second maximum.
  4. That’s it, you have got the maximum element as the ans.
8 Likes
2

And that’s not an easy editorial at all cuz you never explained why are you doing those steps :slight_smile:

27 Likes
3

How yoy reached to the above conclusion

4

Even i followed the same approach, but i understood the logic after trying to find the max GCD of various different problems, but i still was in doubt as to why that approach worked in the first place. If anyone here could provide a concrete proof as to why the following approach works, it would be great!

2 Likes
5

This proof is not very rigorous but I hope it gives some intuition. So the first thing is to realize that the highest (let’s call its value max) and the second highest unique elements cannot be in the same subsequence. Let’s say they were in the same subsequence, then the GCD of the group containing both of them can be at most the max / 2. This is because the prime factorization of the highest element might look p1 * p2 * … pk, and the GCD of the subsequence would be maximized if the second highest contained all these primes p1…pk except the smallest one (they have to be unique). In the best case that prime is 2.

Now, in the best case the other subsequence just has one element, the third highest, but since that is less than the second highest it can also only be max / 2. So overall the total can only be max, but in that case we are just better off putting the max alone in one subsequence, and the other subsequence will have gcd at least 1, which will give us max + 1.

By the same logic, we can also see that both subsequences cannot have more than 1 unique element, because if they did the highest gcd for both would be max / 2, which only yields a total of max. So, you see which one is better, putting the highest separately or the second highest and then output your solution.

9 Likes
6

first of all GCD of two no.s is always a no. less than or equal to the smaller no.
After doing some observations i got to know the exact steps.
And it is an easy editorial because complexity of a soln doesn’t depend upon its explanation.
The steps are easy to understand and might not be difficult for a top 100 coder of INDIA.

2 Likes
7

Absolutely correct explained.

1 Like
8

Bro but your editorial is not required for top coders…they solve by their own…only new coders need it so you need to explain well …
I got it and hv no issues but saying all this just to realize you what you said…

7 Likes
9

Could you please help me to find out a test case where my code for SUMAGCD fails?

code

10

What observation? Hit and trial is not observation. You gotta prove it bro.

3 Likes
11

please give some input to fail my code
https://www.codechef.com/viewsolution/24828838

12

In one subsequence,we have put either the max element or the second max element…Why are we not checking all the elements in that subsequence?

13

Yeah that easy but not an editorial

14

I have a solution which take one element in one set and rest of them in another and it is O(n) also but still what is the proof that one set will only have one value elements ?

16

what’s wrong here
give me runtime error

cook your dish here

import math
t = int(input())
while t>0 :
n = int(input())
l = set(map(int,input().split()))
l = list(l)
l.sort()
#print(l)
if(len(l)==1):
print(2*l[0])
elif(len(l)==2):
print(l[0]+l[1])
elif(len(l)>2):
fmax = l[-1]
smax = l[-2]
gcd3 = l[0]
for i in range(0,n-2):
gcd3 = math.gcd(gcd3,l[i])
gcd1 = math.gcd(gcd3,smax) + fmax
gcd2 = math.gcd(gcd3,fmax) + smax
if(gcd1>gcd2):
print(gcd1)
else:
print(gcd2)
t-=1

17

I used the same approach . But yours seems cleaner

18

Read the official editorial . The reason to put a single element in one set is explained clearly.

19

I know but it’s not in this editorial !!
It’s incomplete !!

1 Like
20

Wish !!! had a haha react option…:rofl:

21

Solution Approach :

==> Reason for two maximum distinct number not being in same set :

The easiest maximum you will get is (maximum number + 1).
Now the GCD of two distinct numbers is always <= (maximum of two numbers/ 2)

if i did so, the maximum value i can now reach is (Third maximum + 1 :: In case max two number’s gcd goes to zero) or (maximum of the given values :: How -> see this example 70,35,35,35)

But i have (maximum + 1) in my pocket already with me.

==> Reason for taking GCD of rest of the numbers and putting it in only one set :
GCD of two numbers is always <= (maximum of two numbers/ 2)

Now instead of making both the maximum number be divided by 2 halves we should make only one which suits the best for the maximum answer because again i have (maximum + 1) in my pocket already with me.

Hope this would help