combinatorics, catalan numbers
A parenthesis contains k blocks if it can be represented as the concatenation of exactly k non empty parentheses, but can not be represented as the concatenation of more than k non empty parentheses For example,
()(()) contains two blocks
()() contains two blocks (
(()()) contains just a single block.
You are given to given two arrays a and b each of size n. You are given some queries. In each query you are given a range [L, R]. You have to select some i, j where L \leq i, j \leq R such that the number of parenthesis of length a_i with b_j blocks is maximized. Find the maximum number of parenthesis possible.
Please note that the editorial should be used for idea only. Currently the expression contain off by 1 error which will be fixed soon
Find the number of parenthesis of length n with b blocks
If you have tried finding number of parenthesis of length n, you would have realized this has some connection with catalan numbers. A pictorial representation of this is usually given by finding number of paths on a grid such that an
( represents going one unit in x direction, whereas
) means moving one unit in y direction. A parenthesis of length 2 * n in such a representation is denoted by a path starting from (0, 0) and ending at (n, n) such that it never crosses the diagonal, i.e. at no moment of time number of
( exceeds number of
In our problem, we want that there should be b blocks of balanced parenthesis, which means that our path should touch the diagonal exactly b times (not counting the starting point touch at (0, 0)).
Number of such parenthesis of length 2 * n with b blocks are given by
Let us try to prove this up. Number of paths of length 2 * n, not going above diagonal with each move being either right or top are given by catalan numbers. We want to find a way of mapping the paths touching diagonal b times, in some way to catalan numbers. Consider a path which touches the diagonal b times, then we can map this path to another path which starts at (0, 0) and ends at (n, n - 1). This mapping is same as decreasing value of y for a path when it touches a diagonal. So, our problem turns into finding number of paths with n right moves and n - b up moves, not crossing the diagonal. These numbers are given by catalan triangle.
Number of paths with n right and k up moves are given by
By putting k = n - b, we get
Solving the full problems
Now, we want to maximize its value. Number of paths will be maximized if we ask it to meet up the diagonal at as few points as possible. So, we find the maximum value of a_i and the minimum value of b_i. Find maximum and minimum value (RMQ) in a given range can be done by using segment tree, or precomputation with the idea of binary lifting. Please check this nice tutorial for more details.