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\).
This problem can only be submitted at Cogniterra.
Public sample 1
Public samples
Input
0001000010101010100001010111011011111011
Expected output
1815943959