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\).
Programming task, Advanced problem
This problem can only be submitted at Cogniterra.
Public samples
Input
0010011000100100011101010111100011110011
Example output
3731631645