### Noobish_Monk's blog

By Noobish_Monk, history, 12 days ago,

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))$?

• +3

 » 12 days ago, # | ← Rev. 3 →   +16 In this blog(https://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)
 » 12 days ago, # | ← Rev. 2 →   +8 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}})$
 » 12 days ago, # |   +8 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} = )$