When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

himanshukumar660's blog

By himanshukumar660, history, 6 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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