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 !!!
I highly doubt your O(M^4) for a NP complete problem 
Created a dependency graph for all the offers. This graph has atmost 20 nodes. then calculated the maximum independent set using max cliques. Complexity is around NM^2 + 1.3^M
On getting AC even I thought of weak test cases but couldnât find a test case in which this approach fails. It would be great if you could tell one 
The main reason behind it getting AC was the property of subgraph, it contains a permanent node such that every other node in the subgraph is connected to it. In the removal process I never touch this permanent node. So when I remove a node from subgraph it doesnât affect the graph in the same way as it does for the Clique Problem
yes , we can solve it using it dp . We can solve it by initially getting the maximum number of non overalapping sets . Then we can use binary number to generate sets like 1100 means i took offer 1,offer 2 and rejected offer 3 and 4 . I solved it this way because i dont know much about graph
http://www.codechef.com/viewsolution/3539147
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?