motherofgod88's blog

By motherofgod88, history, 3 years ago, In English,

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.

 
 
 
 

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

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

»
3 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.

  • »
    »
    3 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

    • »
      »
      »
      3 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.

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

        i think you are correct. the editorial of that problem says that the sate is dp(i, j) where i(set bits in bitmask) is length of permutation and j is last element. this representation seems unique. so i think its just a different way of interpretting the state information. thank you for helping.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
           dp(i, j) where i(set bits in bitmask) is length of permutation and j is last element. this representation seems unique.
          

          this is not true. this way of interpretting is the same as the one i described above. its not unique.