PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Kushagra Kinger
Tester: Kushagra Kinger
Editorialist: Kushagra Kinger
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Catalan Number and their Results.
PROBLEM:
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.
QUICK EXPLANATION:
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.
EXPLANATION:
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.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mo 1000000007
ll modpow(ll x,ll n)
{
if(n==1)return(x%mo);
ll u=(modpow(x,n/2));
u=(u*u)%mo;
if(n%2!=0)u=(u*x%mo)%mo;
return u;
}
int main()
{ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
n--;
cout<<(((n-1)%mo)*modpow(n+1,mo-2))%mo<<"\n";
}
return 0;}
