Links
[Contest](https://www.codechef.com/INSO2018/problems/CBS)Author: Aviroop Pal
Tester: Piyush Mehrotra
Editorialist: Aviroop Pal
DIFFICULTY:
MediumPREREQUISITES:
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.