permutation problems using bitmask
Difference between en1 and en2, changed 86 character(s)
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.↵

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)