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

×

MCKTUR - Editorial

0
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

This question is marked "community wiki".

asked 21 Aug '16, 17:40

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 22 Aug '16, 08:40

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) dpraveen ♦♦4★

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

link

answered 22 Aug '16, 00:25

xellos0's gravatar image

7★xellos0
5.9k54394
accept rate: 10%

Practice link isn't available.

link

answered 23 Aug '16, 15:52

chemthan's gravatar image

7★chemthan
1913
accept rate: 12%

Please open practice!

link

answered 26 Aug '16, 21:29

chemthan's gravatar image

7★chemthan
1913
accept rate: 12%

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)

link

answered 27 Aug '16, 02:54

nims11's gravatar image

6★nims11
431135
accept rate: 20%

edited 27 Aug '16, 02:58

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 .

link

answered 22 Aug '16, 01:50

kush8singh's gravatar image

2★kush8singh
1
accept rate: 0%

edited 22 Aug '16, 01:56

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

link

answered 25 Aug '16, 16:47

abhishek1995's gravatar image

3★abhishek1995
311
accept rate: 0%

Please add this problem to practice

link

answered 10 Sep '16, 20:47

vastolorde95's gravatar image

5★vastolorde95 ♦
324
accept rate: 11%

-1

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

link

answered 22 Aug '16, 03:18

shubhiks's gravatar image

4★shubhiks
732312
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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