pyetwi's blog

Bitmask DP Problem
By pyetwi, history, 4 years ago, In English

Given a string a and b that consist of exactly the same characters, determine the minimum “cuts” required on string a such that it is possible to rearrange the segments of string a to match string b,

For instance, if a = “xxyyz” and b = “zxyxy”, the minimum cuts required on string a is 3

Illustration: x | xy | y | z --> z-xy-x-y

Constraints: |a| = |b| <= 20.

Time limit: 1 second

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pyetwi (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem link?

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

Here's an $$$O(n^22^n)$$$ solution. Try to build string b character-by-character. Let dp[mask][i] be the answer where you already took characters in mask from a, and i was the last character you took. Note you can find the prefix of b you already built by getting the number of set bits in mask. Now for every j s.t. the j'th bit of mask is off, try setting dp[mask][i] to dp[mask|(1<<j)][j] + cost[j] where $$$cost[j]$$$ is equal to $$$0$$$ if j = i+1 and $$$1$$$ otherwise. The answer is min(dp[(1<<n)-1][i]) for all $$$i \in 1...N $$$

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

    Sorry, I'm a bit confused by this solution, but if mask represents the characters you already took from a, isn't it not guaranteed that the set bits in the mask will constitute a prefix of b?

    → Reply