can this problem solved by using sorting with respect to size of each subset ? pls reply
my code is
@shangjingbo 
can you please tell me how DFS is implemented here. Can you provide any good link to read this.
How to see nodes and edge’s.
Thank you.
PS : i followed author’s solution.
Can anyone explain why my solution is wrong ?.I too used DFS.
http://www.codechef.com/viewsolution/3612467
I guess my solution worked in O(N*(M^2) + (2^M) * M) … Am I wrong in my Time Complexity Analysis?
u have posted “Given N objects and M weighted subsets of them, find a combination of subsets, such that all objects are covered at most once and the sum of the weights are maximized.”
plz correct me if i’m wrong, but i think the question asks to maximize the number of subsets in the chosen combination (not the sum of weights).
when nothing come into your mind apply broutforce as i did in this problem find all possible ways and got AC My solution is Here
1 Like
Can someone pls tell me what conflict and ID arrays are storing? Also what is mask variable doing?
i used a greedy strategy for this problem, pick that offer first which has minimum no. of conflicts and if there is a tie then select that offer which has less number of stamps in it. On submitting this gives wrong answer.
Can anyone plzz give a counter example. For reference this my
[1].
[1]: http://www.codechef.com/viewsolution/4176818Shouldn’t the overall complexity be O(NM^2 + 2^M) ?
O(N * M^2) would lead to TLE, for N = 20.000 and M = 20…
I did the same, instead of finding maximum clique, I found maximum independent set.
3 Likes
by NM^2 i mean N*(M^2)
1 Like
sorry, I missed 2^M and M^2 difference O:-) …
How can you say that your complexity is O(M^4)?.
for(every node in graph) //O(M*O(clique()))
{
clique() //O(M<sup>3</sup>)
}
clique()
{
while( a node exists in sub-graph)
{
for(every node in subgraph)
{
for( evry node its connected to)
{
}
}
}
}
Hence overall complexity is O(M4)
As the problem is NP complete and you are giving a polynomial time solution of this problem. You have managed to prove P = NP 
7 Likes
No, the hack here was that the original problem required all the 2^M combinations. But for this problem we will always form a subgraph such that we can solve it in M^4.
Using the binary representation, we can do it in O(NM) rather than O(NM^2).
Oh yes, I got it !!!