Generation of Combinatorial Objects · Object Indices (Optional)
Lesson 7
Programming problem.
Write a program that reads a binary sequence of length 40, which encodes a valid bracket sequence (zero and one encode opening and closing brackets, respectively), and outputs the index of this sequence. (We assume all such valid bracket sequences are ordered lexicographically and indexing starts from zero.)
Hint:
It helps to precompute for each length \(n\) and each balance value \(0 \le b \le n\) the number of sequences of length \(n\) and balance \(b\).
Public samples
Input
0010000010001111110011000101110011010111
Expected output
3092146738