Блог пользователя Homelander2003

Stuck on this problem for days!!
Автор Homelander2003, история, 14 месяцев назад, По-английски

Constraints: 1<=n<=200 1<=k<=10

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
14 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

Hint: $$$DP$$$ in $$$O(N^2*2*K)$$$

→ Ответить
  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Please elaborate the approach if possible. Will really appreciate it.

    → Ответить
    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Let $$$DP_{i j p q}$$$ the number of different strings using the first $$$i$$$ chars from the string, such that $$$j$$$ is the balance between opening and closing brackets, such that if $$$p = 0$$$ then the current char is an opening bracket and if $$$p = 1$$$ then the current char is a closing bracket, such that the last $$$q$$$ chars from the string are the same.

      I will let you think about the $$$DP$$$ transitions.

      → Ответить
»
14 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Me too , it's a dp problem , i found it on atcoder DP Educontest

→ Ответить
»
14 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

You've received a hint that the solution is DP, but that hasn't helped you, so perhaps you're missing an easy test of whether a given sequence is valid.

If you model opening brackets as +1 and closing brackets as -1, then for a sequence to be valid, each prefix sum must be non-negative, and the total sum must be 0. It is easy to derive this rule by considering how one would match the bracket pairs with a stack going left-to-right.

Given this, you should have enough hints to build a DP state and from that see the transitions and the computation.

If you are still struggling, try to write (or imagine writing) a backtracking solution that checks all possibilities (i.e. replaces each ? by 0 or 1 recursively). This is obviously an exponential solution, but the information you end up needing in your recursion is usually a great candidate for a DP state (that's a general advice for DP problems).

→ Ответить
  • »
    »
    14 месяцев назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    writing recursion solution to check all possibilities , it's quiet easy the only problem that i'm facing is How to memoize those small substrings

    example : ????(((????)))

    just from the first [????] in the beginning , how can i store it for the next [????]

    → Ответить
    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I am not sure I understand the question. If you are writing a recursion to check all possibilities, you're not remembering any strings. Any time you come to a "?" you branch out the recursion with a call that treats it as "0" and then another that treats it as "1".

      If that's the case, your recursion state should be describable with only a few integers (remember to use the +1/-1 check for validity I described, instead of keeping any substrings as state).

      → Ответить