MCKTUR - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Alei Reyes
Tester: Hasan Jaddouh
Editorialist: Praveen Dhinwa

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, ()(()) 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:

Setter’s solution
Tester’s solution

1 Like
2

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.

3

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.

1 Like
4

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…

  1. x = 1 y = 1 z = 4 : total combinations 3!/2! = 3(which is the number of combos we can get with these three numbers)
  2. x = 1 y = 2 z = 3 : total combinations 3! = 6
  3. x = 2 y = 2 z = 2 : total cobinations 3!/3! = 1

Therefore ans = 3 + 6 + 1 = 10 .

5

Disappointed to see so many math problems in cook-off once again!

1 Like
6

Practice link isn’t available.

1 Like
7

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
8

Please open practice!

1 Like
9

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)

1 Like
10

Please add this problem to practice