Problem link: http://www.lightoj.com/volume_showproblem.php?problem=1018
Verdict: TLE — O(n^2 * 2^n) solution
Code: http://ideone.com/7JjcIX
I transformed the problem into this. The idea is to given N integer 0 <= N < 2^M where M <= 16, find the minimum number of integer needed to make 2^M-1 by the operation bitwise-OR. My solution is a variation of subset sum as it is the only DP algorithm I know. But, The test cases are huge, 1000. Can you suggest a better approach? Thanks for your attention.
Hmm I can think of an optimisation to bring you down to N * 2^N.
Suppose you have satisfied bitmask M of the points. Let the lowest index dust point which hasn't been cleaned yet be x. Note that you are going to have to clean x eventually. Therefore you lose nothing by assuming you definitely clean x now. Then at each state you narrow down to N edges because you have one point which must be on the line. I'm not sure if that is enough though.
Update: I'm getting WA... I'll let you know if I figure it out. I am worried my idea is incorrect :(
Update2: Solution accept. You can see code here.
Thank you. Your solution is very instructive to me. Instead of solving blindly, I have to be careful next time. Can you suggest any tips which may have helped me to get this idea beside practice?
Also, I had solved this problem using top-down memorization with your idea.
CODE: http://ideone.com/NrFCLK
I'll do my best to detail my thought process.
First the key decision is if you need to have a state of 2^N. In the case of a greedy solution, then you don't need to actually consider all bitmasks. However, I was unable to find greedy solution: so we move on (and assume 2^N).
Now we try to find O(2^N) solution. I like to think of a DP problem as actually a graph of states. A "node" is a bitmask. An "edge" is basically one line of dusting — it lets you move from one bitmask to the next bitmask. Now you want shortest path in this graph (it is actually a DAG which lets you do DP).
Because you have so many options I gave up on 2^N * N. 2^N * N^2 is too slow so I think: why do I have to have N^2 edges on every state? It seems like such a waste. So I tried to reduce number of edges from each state: and realised that you don't have to consider all N^2, only N.
My tip would be to analyse problems that you can't solve and figure out why you couldn't — but you are already doing this :) So I think you are already on a good track to success.
Thanks, that was a very nice explanation. :)