Check official editorials
Well, no need to thank me I got those inputs from my friend, after the contest got over I was discussing this question with him along with these inputs he gave me.
Please read this post or any other editorial from where you can understand the concept.
I think these inputs covered all the corner cases, when I started solving this question during the contest I didn’t created any inputs from my side instead just worked on the logic.
I tried reading your code, damn it’s too long!.. try to keep it simple and add comments, give proper variable names etc. If you understand C++, please have a look at my solution.
Thanks for looking my code and you comment.please ask you friend to get the test cases to fail my code
please see my code in practice
https://www.codechef.com/viewsolution/24862289
Well I want you to yourself debug the error… this is a very important part of learning
Hello sir,
below is my approach
Fact 1:-GCD of a set never greater than the minimum element
Fact 2:-removing an element from the set can effect the GCD of the set
Fact 3:-Fact 2 is not always true for the max element of the set
1)finding min and max elements of the set
2)divide the set based on the GCD example:S={6,10,12} leads to two sets gcd(2)={10},gcd(6)={12}
3)gcd(1) set plays the important role
4)If the set gcd(1) conatins more than one element
then result=1+max,since we have 2 elements that leads to GCD 1,we can keep all elements with gcd 1 elemets in one set and the max element in the other set
5)if the set gcd(1) having only one element
then merge the gcd sets from step 2,after merging gcd(2) ngcd(6) it gives gcd 2
now compare the result=MAX(gcd(after merge) +max ,1+max)
6)if the gcd(1) set not exisit
then find the gcd without max element of complete set and find a element that contributing more to the gcd .
gcd without max element forms 2 sets one with only max element and other is with rest
From the Fact 3:-we are finding an element that contribute more the gcd and remove that from the set and find the gcd of the set that is not having that element
that element is need not be the second max
result is which is more
Link to the solution:-
https://www.codechef.com/viewsolution/24891558
provide input that fails my code
Regards
Samuel
Nice proof