Hello Users,
I had one thing to be clarified and that is related to the question in todays contest #447 (Div. 2). In the question Marco and GCD Sequence we had to print a final sequence.So, the method i employed for finding the sequence was as followed:
Since i know that 1 ≤ i ≤ j ≤ n
so, that means that the given set includes all the elements from my original sequence, in addition to that the set also includes all the gcd's obtained for different values for i and j. Thus, i ran a for loop that
for(int i=0;i<n;i++)
{
if(mv[i]!=0) //just for optimisation, mv(an vector) is the given set
for(int j=i+1;j<n;j++)
{
if(hash[gcd(mv[i],mv[j])]!=1) //A hash for finding that if gcd of two numbers doesn't exist than i would return -1
{
cout<<-1<<endl;
return 0;
}
else
mv[j] = 0;
}
}
Now if the set contains all the numbers in which for every pair of element a gcd exists in that set, than i would just be printing the original set given to me at the output. After submission, i find that my solution gives an error for test case 15 which says wrong answer Integer 3021 does not appear in the set, but is produced by the sequence.
. But how is that possible when i am printing the same set given to me at the output. Any kind of help will be appreciated. Thanks in advance. Here is the link to my submission : http://codeforces.com/contest/894/submission/32477988
Hi consider this case:
but 3 is not exists in input set.
to overcome this problem we can insert smallest value from set between each of two elements.
so the answer would be:
Edit: I was wrong