Reference's blog

Dp trick?
By Reference, history, 8 years ago, In English

If I have N <= 20 elements, I need to arrange them in some way to satisfy a condition(s), what is the number of arrangements mod 1e9 + 7, where an arrangement is different from another arrangement if at least on element is in different locations in the two arrangements, is there some dp trick to know if an arrangement counted before?? note: in this type of problems arrangement may be counted twice because may it's satisfy conditions in two different ways.

  • Vote: I like it
  • +13
  • Vote: I do not like it

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

Can you post the link of the problem, please?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

DP[bitmask][last_added][type]

bitmask is the mask of the chosen dominoes, last_added is the last domino added and type is where the magic should happen: 0 if you can only use the first number, 1 if you can only use the second number and 2 if you can use both numbers. The answer would be the sum 0 <= i < n of dp(1 << i, i, 2). The complexity is O(n^2 * 2^n * t) and should be enough (you can also optimize the transition quite a lot). Actually, I just tried this idea to make sure and it passed with 700ms without optimizations other than using a ternary instead of modulo operations, quite good huh.

Bonus: from this idea, you can see that if you change a number on any solution, you will be able to get a valid solution if and only if the setting where all the numbers are changed is a solution and you changed all the numbers. You can also optimize it using something like [mask][last_piece] where you have a vector with all possible pieces including "ghost" pieces with only 1 face available for matching, there'd be O(n + 6) possible pieces. The complexity is the same but you get rid of the last state. Also from this you can see that if there are pieces with repeating numbers and pieces with not repeating numbers, the answer will never be counted twice.

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

    Your solution won't count repeated configurations just because of the value 2 in the 'type' parameter, right? I was thinking in something very similar to your solution but only with states 0 and 1 in 'type' parameter, but this would lead to repeated counting.

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

      Yes. In particular, you make only 1 transition to the next piece (you don't do to 0 and 1 if you can do it to 2).

      → Reply