Homelander2003's blog

Stuck on this problem for days!!
By Homelander2003, history, 13 months ago, In English

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

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

Comments Comments (8)
| Write comment?
»
13 months ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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

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

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

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

      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.

      → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    Plz mention if possible the contest where you encountered such question or similar question.

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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).

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 [????]

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

      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).

      → Reply