himanshukumar660's blog

By himanshukumar660, history, 3 weeks 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  

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by himanshukumar660 (previous revision, new revision, compare).

»
3 weeks 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
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks.. I understood my mistake.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Edit: I was wrong

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      smallest element of set is already present in the set :D

      and 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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      void solve(int m)
      {
      	vector<int> 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');
      }