shakil.ahamed's blog

Need help on a bitmask DP problem
By shakil.ahamed, history, 7 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply