permutation problems using bitmask

Revision en2, by motherofgod88, 2015-08-31 22:33:22

UPD: i found the problem here http://codeforces.com/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.

Tags bitmask, permutation, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English motherofgod88 2015-08-31 22:33:22 86
en1 English motherofgod88 2015-08-31 22:24:41 863 Initial revision (published)