Noobish_Monk's blog

How to efficiently count specific regular bracket sequences?
By Noobish_Monk, history, 9 months ago, In English

I came up on a problem and got it to solving this one, but now I am stuck. Can someone help please?

How can we efficiently count the number of regular bracket sequences with length $$$2n$$$ that have first closing bracket on position $$$k + 1$$$ (any way faster than $$$O(nk)$$$ or $$$O(n^2))$$$?

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

»
9 months ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

In this blog(https://mirror.codeforces.com/blog/entry/87585) you can find number of bracket sequences with lenght 2n with a prefix on k open brackets. I belive(if i didnt missunderstand)your problem reduces to the number with a prefix of k minus the number with a prefix of k+1.(The first k will be open and the k+1th will be closed)

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

Isn't this similar to the CSES problem: https://cses.fi/problemset/task/2187 ?

But with the input:

$$$ 2\cdot n\\ \underbrace{(((...(}_{k\ \text{times}}) $$$
→ Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

if the first closing bracket is on $$$k + 1$$$, then first $$$k$$$ brackets are opening right?

if so, just solve cses bracket sequences II with $$$s_1 = s_2 = ... s_k = ($$$ and $$$s_{k+1} = )$$$

→ Reply