john_hopes's blog

Bitmask DP
By john_hopes, history, 8 years ago, In English

In a bitmask DP problem, there 10 digits. And for every digits I need to store three types of data ( Not used, Used and Using ). One way to solve this is using two bitmask. But for some other reasons It is not possible to use two bitmask in my case. Is there any other memory efficient way to do so? Is there any good resources for learning this?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you link the problem? It would make it easier to understand the constraints, specifics, etc.

→ Reply
»
8 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Use map or hashtable. Also you can use numeral system with base 3.
Get: digit[i] = (x / 3^i)) % 3.
Set: x = x + (value - (x / 3^i)) % 3) * 3^i
3^10 == 59049, so value of your mask will be in [0..59048].
Instead of slow division operation you can precompute modInverse(3^i, 2^32) and multiply.
x / (3^i) == x * modInverse(3^i, 2^32) In unsigned 32-bit integer type.

→ Reply