### Links

[Contest](https://www.codechef.com/INSO2018/problems/CBS)** Author:** Aviroop Pal

** Tester:** Piyush Mehrotra

** Editorialist:** Aviroop Pal

### DIFFICULTY:

Medium### PREREQUISITES:

Path Programming, Catalan Numbers.### Problem Statement:

Given two numbers**N**and

**K**, find the probability that a

**N**length correct bracket sequence can be converted to a good correct bracket sequence in atmax

**K**'good' swaps. A swap is good if the sequence after the swap is a correct bracket sequence.

### Explanation:

The problem basically reduces to finding the number of correct bracket sequence having less than or equal to K closing brackets in the first half of the sequence. Finding the number of such correct bracket sequences can be done using Path Programming.Let the length of the sequence be 2*n. So finding the total number of correct bracket sequences is equivalent to finding the number of paths from (0,0) to (n,n) which does not touch y = x+1 line. Now consider those paths which touch the line y=x+1. If any such path is reflected along the line y=x+1 after the first intersection, it ends at the point (n-1,n+1) which is the reflection of (n,n) about the line. So the number of paths which do not touch the line is equal to **C(2n,n)-C(2n,n-1)**.

Let the number of closing bracket sequences in the first half of the sequence be x. Those paths will pass through (n-x,x). Therefore the number of such paths is equal to **(C(n,x)-C(n,x-1))^2** where 0<=x<=min(k,n/2).So the probability turns out to be **summation(i=0 to min(n/2,k))(C(n,i)-C(n,i-1)))/(C(2n,n)-C(2n,n-1))**.

Also note that ‘good’ swaps does not affect the overall solution since a ‘)’ in the first half of the sequence can be replaced with a ‘(’ in the next half and the sequence will still remain a CBS.

For more details refer to here.