You are not logged in. Please login at www.codechef.com to post your questions!

×

# MCKTUR - Editorial

Author: Alei Reyes
Editorialist: Praveen Dhinwa

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, ()(()) contains two blocks () and (()). Similarly ()() contains two blocks (() and ()) and (()()) 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.

# 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
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 )'s.

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
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.

# Tester's Solutions:

This question is marked "community wiki".

asked 21 Aug '16, 17:40 2.5k53137170
accept rate: 20%

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.

(22 Aug '16, 00:06)

 2 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 7★xellos0 5.9k●5●43●94 accept rate: 10%
 2 Practice link isn't available. answered 23 Aug '16, 15:52 7★chemthan 191●3 accept rate: 12%
 2 Please open practice! answered 26 Aug '16, 21:29 7★chemthan 191●3 accept rate: 12%
 2 An alternate and more rigorous explanation n-1 should be used instead of n in the catalan triangle formula. (To offset the starting right move in the mapped path, since a right move followed by an up move is invalid in the mapped path) answered 27 Aug '16, 02:54 6★nims11 431●1●3●5 accept rate: 20%
 0 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... x = 1 y = 1 z = 4 : total combinations 3!/2! = 3(which is the number of combos we can get with these three numbers) x = 1 y = 2 z = 3 : total combinations 3! = 6 x = 2 y = 2 z = 2 : total cobinations 3!/3! = 1 Therefore ans = 3 + 6 + 1 = 10 . answered 22 Aug '16, 01:50 1 accept rate: 0%
 0 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,n-b) not crossing the diagonal answered 25 Aug '16, 16:47 31●1 accept rate: 0%
 0 Please add this problem to practice answered 10 Sep '16, 20:47 32●4 accept rate: 11%
 -1 Disappointed to see so many math problems in cook-off once again! answered 22 Aug '16, 03:18 4★shubhiks 732●3●12 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,658
×900
×29
×12
×11

question asked: 21 Aug '16, 17:40

question was seen: 3,003 times

last updated: 18 Apr '17, 17:09