Noobish_Monk's blog

How to efficiently count specific regular bracket sequences?
By Noobish_Monk, history, 11 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(n2))?

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

»
11 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
»
11 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⋅n(((...(⏟k times)
→ Reply
»
11 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 s1=s2=...sk=( and sk+1=)

→ Reply