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
Yes, it is number of subsets in the problem. But we can also solve it if weights are given (number is a special weight, each subset is weighted as 1)
Because it can be optimized to O(NM+2^M)
I think I have written the pseudo code of DFS in the editorial
My question was that even though my solution is M times slower, it still passed. Why?
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/4176818