### himanshukumar660's blog

By himanshukumar660, history, 12 months ago, ,

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

•
• +3
•

 » 12 months ago, # |   0 Auto comment: topic has been updated by himanshukumar660 (previous revision, new revision, compare).
 » 12 months ago, # |   0 Hi consider this case: 3 1 9 15  gcd(9, 15) => 3 but 3 is not exists in input set. He remembered that he calculated gcd(ai, ai + 1, ..., aj) for every 1 ≤ i ≤ j ≤ n and put it into a set S. to overcome this problem we can insert smallest value from set between each of two elements.so the answer would be: 6 1 1 9 1 15 1 
•  » » 12 months ago, # ^ |   0 Thanks.. I understood my mistake.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Edit: I was wrong
•  » » » 12 months ago, # ^ |   0 smallest element of set is already present in the set :Dand she/he must check if the answer exists or not (she/he asked why original set is not valid)and if answer exists the gcd of all elements is the smallest element of set
•  » » » 12 months ago, # ^ |   0 void solve(int m) { vector g(m); for (int i = 0; i < m; i++) { read_int(&g[i]); } for (int i = 0; i < m; i++) { if (g[i] % g[0] != 0) { write_int_n(-1); return; } } write_int_n(m * 2); for (auto o : g) { write_int_s(o); write_int_s(g[0]); } putchar('\n'); }