motherofgod88's blog

permutation problems using bitmask
By motherofgod88, history, 9 years ago, In English

UPD: i found the problem here http://codeforces.me/problemset/gymProblem/100589/G

in many problems involving counting some permutations, we use state dp[mask][i] which denotes solution for subproblem where i is the last element used from a given array and the bits in mask variable are set if those values have been taken. i read somewhere that state in a DP solution should uniqely represent a subproblem. so in this case, how is this representation unique?

suppose array is 1, 2, 3, 4, 5, 6.

mask = 15(1111) and i = 4. this permutation is 1234. this will count the permutation where elements from index 1 to 4 have been taken and index 4 is the last element. but for permutation 1324 also, the state will be same. so how this state will give correct answer in such cases.

i remember seeing such a problem about counting permutations in CF GYM. but i cant find it now. it was solved using bitmask.

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

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

dp(last, mask) number of permutations if you already used the elements marked by 1 in positions of the bitmask, and the last used number is last.

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

    so permutations 1234 and 1324 both have same representations dp(4, 8). 8 == 111

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, they both have the same representation, but this is what we need to count. It's not about each permutation having an unique representation, becuase there would actualy be n! states, and the solution would be no better than generating all the permutations. It's more about the states being consistent and "exhaustive" meaning the recurence is correct and it counts all the possible outcomes.

      When devicing a dp solution, you could do something like dp(N) = number of permutations of elements 1,..,N that obey the conditions of the problem. Usually this is not enough, so you add additional dimensions, that actually partition the number of canditate solutions into disjoint(not sure about this) sets. So dp states don't actually need to represent some exact configuration, but they also can represent the cardinal of some set of solutions.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think you can reduce the state to 1 dimension just dp(mask) and from this state, you can build all states dp(mask | (1<<i)) by iterate all off-bit in mask. Anyway, It can't reduce time complexity.

    → Reply