ABalobanov's blog

Bracket sequences
By ABalobanov, history, 9 years ago, In English

How to count number of bracket sequences with n opening brackets and m closing brackets so that the balance never gets negative? I came to this problem thinking about other one(D from previous Open Cup), and I can't solve it in sufficient complexity. Is there a way to do it with n <= 2000, m <= 2000, answering one query in O(1) time or somehow precomputing these values for all i, j <= 2000?

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

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

May be Catalan number can be useful for you. You can read it here.

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Non-negative partial sum

→ Reply