Que : Contest Page | CodeChef
I need solution or approach for this , I tried many but still it gives me WA , I know my logic is wrong but not able to figure out. @rohitpratap311
also @admin can u please allow me to view the solution of participants.
if u r not able to access then -
@ssrivastava990 The solutions are public now you can check it now.
We will provide Editorial tomorrow .
can u share basic approach to solve this question.
Oh shit I read question wrong 
You can use sieve type algorithm. First, sort the list, now if an element occurs only once, mark all its multiples and push back to the answer list. If an element occurs multiple times and has not been marked, mark its multiples but don’t push back to the answer list. Here is my code(although I didn’t submit it).
Overall Complexity : O(M*log(log(M))), where M = 10^6.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vec(n);
int i;
for(i=0;i<n;i++)
cin >> vec[i];
sort(vec.begin(), vec.end());
int mark[1000001] = {0};
int j;
vector<int> ans;
for(i=0;i<n;i++)
{
j = i;
while(j < n && vec[j] == vec[i])
j++;
if(j == i + 1)
{
if(!mark[vec[i]])
{
ans.push_back(vec[i]);
int s = vec[i];
while(s < 1000001)
mark[s] = 1, s+=vec[i];
}
}
else
{
if(!mark[vec[i]])
{
int s = vec[i];
while(s < 1000001)
mark[s] = 1, s+=vec[i];
}
}
i = j - 1;
}
if(ans.size() == 0)
cout << -1 << '\n';
else
{
cout << ans.size() << '\n';
for(auto j : ans)
cout << j << " ";
}
}
Yup , I understand , let me tell u another question(which I actually interpret)
suppose we have an array , same as above , we have to select maximum numbers from array such that in selected number for every pair they are not multiples.
for ex : 4 6 9 8
answer is 3 {4,6,9}
Yes, your interpretation is correct. It is the same problem.
No samarth let me tell u one more example
arr = 2,4,6
now answer is 2 {4,6} as 4 is not divisible by 6 or 6 is not divisible by 4
I think answer should be 1 which is {2} because 1<=j<=n ie any value in array
Let’s say we build a graph where i and j are connected if one is multiple of other. Then in this graph we need to find size of maximum independent set which is NP-hard.
so it is very difficult?
nope @sebastian my question is slightly different, we have to select numbers such that the in selected number no two numbers are divisor or multiple of each other.
Oh you thought of another question. I was thinking about the contest ques
I think so, @everule1, @carre can you also see this? I am re-stating the problem here:
From an array where A[i] \le 10^6 , chose the maximum size subset such that there exists no pair x, y and x divides y. Example : {2, 4, 6} then answer should be {4, 6}.
I don’t see a way to avoid dealing with maximum independent set problem in that case