Блог пользователя john_hopes

Bitmask DP
Автор john_hopes, история, 9 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить