motherofgod88's blog

By motherofgod88, history, 5 years ago, In English
  • Vote: I like it
  • +55
  • Vote: I do not like it

By motherofgod88, history, 7 years ago, In English

UPD: i found the problem here

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.

Full text and comments »

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