Formatted 
12
7 7 12 8 7 2 4 8 11 7 5 3
The optimal answer should be 10
Optimal Solution: [7, 7, 12, 8, 7, 2, 11, 7, 5, 3]
let me correct it
how about you look for squares in the Original multiset and then remove the number whose square it is( say your set has 64 in it then look for 8 if it exists remove it)
What is there is not square?
A = [32, 16], the optimal solution can contain only one of these elements
I found the maximal independent set greedily.
starting at every possible node?
can it be done with prime sieve array by counting each prime max up to 2.
Using the method of finding the lowest degree vertex adding it to the set and deleting its neighbours ?
Yes, but its incorrect because finding MIS is a NP-hard problem. There exist graphs where it would fail. But since the graph was to be constructed based on the property of a pair of numbers, I kind of assumed it that such graph might not exist XD.
1 Like
16 is a square no. right , we can remove it also in that case. my point was if( m *n = k^3) then either m or n must be a square no. right .based on that idea we can form a solution don’t you think ? 
hmm…in that case please provide your code…
Can you please provide some code for this approach?
TreeSet<Integer> MIS(int n) {
TreeSet<Integer> is = new TreeSet<>();
TreeSet<Pair> set = new TreeSet<>();
int deg[] = new int[n + 1];
for (int i = 0; i < n; ++i) {
set.add(new Pair(graph[i].size(), i));
deg[i] = graph[i].size();
}
while (!set.isEmpty()) {
Pair v = set.pollFirst();
for (int e : graph[v.y]) {
if (set.contains(new Pair(deg[e], e))) {
for (int f : graph[e]) {
if (set.contains(new Pair(deg[f], f))) {
set.remove(new Pair(deg[f], f));
set.add(new Pair(--deg[f], f));
}
}
set.remove(new Pair(deg[e], e));
}
}
is.add(v.y);
}
return is;
}
1 Like
m = 12 , n = 18 , m*n = 6^3 ??
The correct statement would be if m * n = k^3, then m = x^2 * y, n = x * y^2
anyways , this approach is not suitable i think provided the case you mentioned and also creating a separate array for all the cubes or say squares. and then checking for them is too heavy implementation.but gladly now i know this approach can’t be used in problems like these.
I think Meet in the Middle with Bitmasking . Can easily be applied here as N<=22. ,
My approach divide N into two sets containing N/2 elements each. Form all subsets possible for those n/2 elements.
, Now you have two 2^(N/2) subsets. cool
Ok , Now simply just store for every element in the array A that what is the counter element in the array which when multiplied with this element produces a perfect cube.
cool.
Now use bit masking for both N/2 partitions and store bit-masks in memory that
if out of this elements if element at index 2 is not present in this subset then store 0 at this bit and so on.
, Now you traverse one of those 2^N/2 subsets partitions, if this subset doesn’t contain any faulty pair. Now for each element present in this array find its counter element on opposite side and make a request bitmask with 1s and 0s containing 11 (N/2) elements. Now you have a bitmask in which 0 indicate that these element must not be present. among the subset that is going to be selected from the second half. cool
Now your searching of bitmasks must be efficient enough to pass heavy cases. I cant write more but this can be my core ides about solving the problem,