PROBLEM LINK:Author: Alei Reyes DIFFICULTY:medium PREREQUISITES:combinatorics, catalan numbers PROBLEM: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, 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. EXPLANATION: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 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 $$\dbinom{2 * n  b  2}{n  b  1} \times \frac{b + 1}{n}$$ 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 $$\frac{(n + k)! \quad (n + k  1)}{k! \quad (n + 1)!}$$ = $$\dbinom{n + k}{k} \quad \frac{n + k  1}{n + 1}$$ By putting $k = n  b$, we get $$\frac{(2 * n  b)! \quad (2 * n  b  1)}{(n  b)! \quad (n + 1)!}$$ Solving the full problems Tester's Solutions:
This question is marked "community wiki".
asked 21 Aug '16, 17:40

How I found the expression for the number of parenthesis sequences with given length and number of blocks: I instantly viewed it as a convolution of Catalan numbers, googled that phrase and found this. Just substitute $a_i$ for $2n$ and $b_j$ for $k$. answered 22 Aug '16, 00:25

An alternate and more rigorous explanation
answered 27 Aug '16, 02:54

although i havent done it yet, and hope i am right .... this can be interpreted as a knapsack problem for example if we wish make 3 sets of length 12 , we can interpret it like a + b + c = 12 and find pairs of a b and c (i would do it through knapsack , since thats the only way i know as of now ) ,here a b c are the number of '{' and '}' reqd. to make a complete parenthesis i.e '{}' is a = 2 ; '{{}}' may be b = 4 etc. Now we know x y z should be even numbers , so we divide 12 by 2 therefore we find all combination for x + y +z = 6 and proceed as follows...
Therefore ans = 3 + 6 + 1 = 10 . answered 22 Aug '16, 01:50

I still didn't get how the following two are equivalent : 1) Number of paths form (0,0) to (n,n) touching diagonal b times 2) Number of paths from (0,0) to (n,nb) not crossing the diagonal answered 25 Aug '16, 16:47

Disappointed to see so many math problems in cookoff once again! answered 22 Aug '16, 03:18

Hi all, currently my formulas are mysteriously containing off by 1 error. I will fix it. Please use the current expression in the editorial for the idea of the solution.