PROBLEM LINK: CodeChef: Practical coding for everyone



Author: Kushagra Kinger

Tester: Kushagra Kinger

Editorialist: Kushagra Kinger




Catalan Number and their Results.


Sokka has to travel on a square grid of NxN from (0,0) to (N-1,N-1) and has to pay money each time he makes a transition ( refer the problem statement for knowing what a transition is) and moving only right or below from the current cell in the grid.


If you observe carefully , the problem can be reduced to finding number of paths in a grid from one corner to diagonally opposite corner which cross the diagonal.


We are asked the Probability that the coins are lesser than the initial value when the journey ends. If you have understood the basic question , we have to pay a coin each time the path crosses the diagonal. So we have to calculate the probability of the paths which crosses the diagonal of the grid, no matter how many times, because in all the paths which crosses the diagonal we will have to pay atleast one coin and the money in the bag after the journey will be less.

Now let’s define n=N-1. In a NxN grid if we have to move from (0,0) to (N-1,N-1) following the rules as described in the problem , we need to take n Right(R) moves and n Down(D) moves. Total number of distinct possible paths will be T=2nCn(number of permutations of a string of size 2n with n ‘R’ characters and n ‘D’ characters. If we subtract the number of paths which never cross diagonal from this total value we will get our answer i.e. the number of paths which cross the diagonal.

If you observe, a path which doesn’t cross the diagonal is either always below the diagonal or it is always above it. Let’s find out the number of paths which are always below diagonal.

If we define our path as a sequence of D and R moves , a path which is always below diagonal will be a path with the following property:
If you traverse the path sequence from left to right (1 to 2n) , at any point the number of D’s encountered till that point must be greater than or equal to the number of R’s encountered upto that point. If you treat D as ‘(’ and R as ‘)’ , the problem reduces to number of valid paranthesizations with n pairs of opening and closing braces. So, our answer is nothing but the nth Catalan number. Similarly , number of paths which are always above the diagonal will be equal( Due to symmetricity or just replace D and R in the above proof).

Thus, the number of paths which never cross the diagonal are 2x(nth Catalan Number).

So, the number of paths which cross the diagonal will be (2nCn)-2*((1/(n+1))2nCn), which will be equal to P=((n-1)/(n+1))2nCn. Thus the probability is P/T=(n-1)/(n+1) where n=N-1.

The initial value of coins in the bag 2*N is useless extra information as the maximum number of times Sokka makes a transition(or cross the diagonal) will be around half of this value, so any path is possible.


Setter's Solution
using namespace std;
typedef long long ll;
#define mo 1000000007

ll modpow(ll x,ll n)
ll u=(modpow(x,n/2));
return u;

int main()
{ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int t;
	ll n;

return 0;}

Here all the paths are not equally probable then how can we divide good paths by total paths to find the probability.

In the problem statement its clearly written :
" to any other valid location (by valid location we mean a location which exists on the world map grid i.e. for that location 0≤r<N0≤r<N and 0≤c<N0≤c<N ) just to the right (r,c+1)(r,c+1) or below (r+1,c)(r+1,c) the current location randomly"
I think its quite easy to assume that all the paths will be generated with equal probability . i guess those who got AC made the similar assumption.

(0<=r<N) and (0<=c<N)*

From a cell if we can go to down cell and right cell randomly then each will have probability =1/2 but if we can only go to either right or down then it will have 1 probability then how can all the paths have same probability ? Am I interpreting the probability asked in the question wrongly or my given argument is wrong?

Is there anything wrong with calculating these two path probabilities?


the thing is that if i ask u to move on the grid , then you can go through any of the total possible 2nCn paths, right. So , you have all those paths in your sample space and u can choose any one of them with equal probability, the problem was just this. Involving the probability at each step is not required.

Okay. Thanks for the help

1 Like