PROBLEM LINK:
Author: Jatin Kashyap
Tester: Pankaj Sharma
Editorialist: Jatin Kashyap
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Modular Exponentiation , Modular Multiplicative Inverse
PROBLEM:
You have to find the number of ways of reaching [n][m] in a
n*m grid from [1][1] making exactly k turns turns
along the way for each k, 1<=k<=2*n-2.
EXPLANATION:
Subtask 1
We can use recursion to calculate number of ways.
We will start from 1,1 then we have 4 cases.
- If we are moving in right direction then continue moving in it.
- If we are moving in right direction then change direction to down and increase current number of turns by 1.
- If we are moving in down direction then continue moving in it.
- If we are moving in down direction then change direction to right and increase current number of turns by 1.
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> turnAns;
ll n, m;
// 1 means right and 0 means down
// And prev means previous
void go(int x, int y, int currentTurns, bool prevTurn) {
if (x == n && y == m) {
turnAns[currentTurns] += 1;
return;
}
if (x > n or y > m) return;
// If prev turn is down
if (prevTurn == 0) {
// Move down
go(x , y + 1, currentTurns, prevTurn);
// Move right
go(x + 1 , y , currentTurns + 1, prevTurn ^ 1);
}
// If prev turn is right
else {
// Move right
go(x + 1, y, currentTurns, prevTurn);
// Move down
go(x , y + 1, currentTurns + 1, prevTurn ^ 1);
}
}
void solve() {
ll ans = 0;
cin >> n >> m;
turnAns = vector<int>(2 * m, 0);
go(1, 2, 0, 0);
go(2, 1, 0, 1);
for (int i = 1; i <= 2 * m - 2; i++) cout << turnAns[i] << " "; cout << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Subtask 2
We can use Dynamic programming aka DP to solve this problem.
We will make a 4 dimensional dp as dp[row][column][currentNoTurns][direction]
Then we will do transitions i.e. calculate values of our dp array as mentioned in the recursion part.
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> turnAns;
ll n, m;
vector<vector<vector<vector<int>>>> dp;
const ll MOD = 1e9 + 7;
// Modular arithmetic operations
ll add(ll x, ll y) {ll ans = x + y; return (ans >= MOD ? ans - MOD : ans);}
ll mul(ll x, ll y) {ll ans = x * y; return (ans >= MOD ? ans % MOD : ans);}
ll sub(ll x, ll y) {ll ans = x - y; return (ans < 0 ? ans + MOD : ans);}
void solve() {
ll ans = 0;
cin >> n >> m;
turnAns = vector<int>(2 * m - 1, 0);
dp = vector<vector<vector<vector<int>>>>(n, vector<vector<vector<int>>>(m, vector<vector<int>>(2 * m, vector<int>(2, 0))));
// dp[row][column][currentNoTurns][direction]
// 0 means right 1 means down
// making 0 turns you can go only in right direction from a row
for (int i = 0; i < m; i++) {
dp[0][i][0][0] = 1;
}
// making 0 turns you can go only in down direction from a column
for (int i = 0; i < n; i++)
{
dp[i][0][0][1] = 1;
}
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++) {
for (int k = 1; k < 2 * m; k++)
{
// We can go right by moving in a row or by changing direction of down path.
dp[i][j][k][0] = add(dp[i][j - 1][k - 1][1] , dp[i][j - 1][k][0]);
// We can go down by moving in a column or by changing direction of right path.
dp[i][j][k][1] = add(dp[i - 1][j][k - 1][0] , dp[i - 1][j][k][1]);
}
}
}
for (int i = 1; i <= 2 * m - 2; i++) {
// Add number of ways of reaching from left and right to get final answer
turnAns[i] = add(dp[n - 1][m - 1][i][0], dp[n - 1][m - 1][i][1]);
cout << turnAns[i] << " ";
}
cout << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Subtask 3
The First Observation to make is that once you reach the final row(nth row)
or the final column(mth column), you don’t have any choice but to make a turn
towards [n][m] . Now the question reduces to finding the number of ways of reaching
the final row or the final column in k-1 steps. A turn is defined as changing you trajectory
by 90 degree towards the right(if you were moving down ) or towards the bottom (if you were
moving towards the right side). Therefore , you cannot make two top-down or left-right turns
in succession
Since you can either start towards the ride side or the bottom one and have to reach
either the nth row or the mth column , there will be 4 cases in total.
Case 1 (Starting towards the right and reaching the nth row):-
It is clear through observation that the minimum number of turns to do the same is 1
(A top down turn). Now ,since we can only make top-down and left-right turns alternatively,
to reach the nth row , every time we make a left-right turn, we also have to make a top-down
turn to shift the trajectory towards the bottom . Therefore , after the initial top-down turn
we can only add turns in multiples of 2 to have a final top-down trajectory . Now since we initially
made a top-down turn , the number of top down turns will always be one more than the left right turns.
Let number of Top-Down Turns be R , then the number of Left-Right turns will be R-1. Now Since the total number of turns was k-1 ,
R+R-1=k-1 => R=k/2.
So, you have to make k/2 top down turns and k/2-1 left-right turns. Now the question reduces to finding the number of ways of choosing k/2 cells from a total of m-2 cells to make a top-down turn and choosing k/2-1 cells from a total of n-2 cells to make left right turn . This can easily be calculated by using the formula for combinations (n-2 C k/2-1)*(m-2 C k/2).
It must also be noted that k-1 is an odd number since we started with 1 and added multiples of 2 and therefore k must be even in Case 1.
Case 2 (Starting towards the right and reaching the mth column ):-
It is clear through observation that the minimum number of turns to do the same is 0 and since you only add turns in multiples of 2 to maintain the initial trajectory , the value of k-1 must be even and the value of k must be odd . Since there will be an equal no. of top-down(say R) and left right turns(also R) ,the value of R will be (k-1)/2. Again , the question reduces to finding the number of ways of choosing (k-1)/2 cells from a total of m-2 cells to make a top-down turn and choosing (k-1)/2 cells from a total of n-2 cells to make left right turn . The answer for this case will therefore be (n-2 C (k-1)/2)*(m-2 C (k-1)/2) and k must be even.
Case 3 ( Starting towards the bottom and reaching the nth row ):-
Through a similar process , it can be proven that the value of k must be odd and the answer would be (n-2 C (k-1)/2)*(m-2 C (k-1)/2).
Case 4 ( Starting towards the bottom and reaching the mth column ):-
The value of k must be even and the answer would be (n-2 C k/2)*(m-2 C k/2-1).
The final answer would be the sum of Case 1 and Case 4 for even values of k and Case 2 and Case 3 for odd values of k .
You can easily calculate nCr for for smaller values in subtask 1 and for subtask 3, nCr for higher values can be calculated using Modular Exponentiation and Modular Multiplicative Inverse .
SOLUTIONS:
Setter's Solution
import java.util.Scanner;
class AoT {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
fact();
for(int t= sc.nextInt();t>0;t--){
int m=sc.nextInt();
int n=sc.nextInt();
long d=1,r=1; int x=1,y=0,n1=n-2,m1=m-2;
System.out.print(d+r+"");
for(int i=2;i<=2*n-2;i++){
if(i%2==0){d=C(n1,x)*C(m1,y);r=C(m1,x)*C(n1,y++);}
else{d=(C(n1,x)*C(m1,y))%mod;r=(C(m1,x++)*C(n1,y))%mod;}
System.out.print(" "+(d+r)%mod);
}
System.out.print("\n");
}
}
static long mod=1000000007;
static long fn[]=new long[10001];
static long C(int n,int r){
if(r==n)return 1;
if(r>n)return 0;
long fr=moduloExp(fn[r],mod-2,mod);
long fnr=moduloExp(fn[n-r],mod-2,mod);
long c= ((fn[n]*fr)%mod*fnr)%mod;
return c;
}
static void fact(){
fn[0]=1;
for(int i=1;i<=10000;i++)fn[i]=(fn[i-1]*i)%mod;
}
static long moduloExp(long n,long p,long m){
if(n==1||p==0)return 1;
else if(p==1)return n;
else{
long pow=1;
while(p>0){
if((p&1)==1)pow=(pow*n)%m;
p=p>>1;
n=(n*n)%m;
}
return pow;
}
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << " = " << arg1 << " | "; __f(comma + 1, args...);
}
const ll N = 1e5;
const ll MOD = 1e9 + 7;
ll add(ll x, ll y) {ll ans = x + y; return (ans >= MOD ? ans - MOD : ans);}
ll mul(ll x, ll y) {ll ans = x * y; return (ans >= MOD ? ans % MOD : ans);}
ll sub(ll x, ll y) {ll ans = x - y; return (ans < 0 ? ans + MOD : ans);}
vector<int> turnAns;
ll n, m;
vector<ll> fac, fac_inverse, num_inverse;
void preprocess() {
fac = fac_inverse = num_inverse = vector<ll>(N + 1);
num_inverse[0] = num_inverse[1] = 1;
for (ll i = 2; i <= N; i++)
num_inverse[i] = num_inverse[MOD % i] * (MOD - MOD / i) % MOD;
fac_inverse[0] = fac_inverse[1] = 1;
for (ll i = 2; i <= N; i++)
fac_inverse[i] = (num_inverse[i] * fac_inverse[i - 1]) % MOD;
fac[0] = 1;
for (ll i = 1; i <= N ; i++)
fac[i] = (fac[i - 1] * i) % MOD;
}
ll power(ll x, ll y)
{
ll ans = 1;
x = x % MOD;
while (y > 0) {
if (y & 1)
ans = (ans * x) % MOD;
y = y >> 1;
x = (x * x) % MOD;
}
return ans;
}
ll modInverse(ll n)
{
return power(n, MOD - 2);
}
ll nCr( ll n, ll r)
{
if (r > n) return 0;
if (r == 0)
return 1;
return mul(mul(fac[n], fac_inverse[r]), fac_inverse[n - r]);
}
void solve() {
ll ans = 0;
cin >> n >> m;
ll max = 10001;
if (n == 1 or m == 1) return;
assert(n >= 1 and n <= max);
assert(m >= 1 and m <= max);
assert(n > m);
ll row = 0, col = 0;
for (int i = 1; i <= 2 * m - 2; i++) {
// trace(n - 2, m - 2, row, col);
ll oneSide = mul(nCr(n - 2, row), nCr(m - 2, col));
ll otherSide = mul(nCr(n - 2, col), nCr(m - 2, row));
// trace(oneSide, otherSide);
ans = add(oneSide, otherSide);
cout << ans << " ";
i % 2 ? row++ : col++;
}
cout << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
preprocess();
cin >> t;
int max = 10;
assert(t >= 1 && t <= max);
while (t--)
solve();
return 0;
}
Editorialist's Solution
import java.util.Scanner;
class AoT {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
fact();
for(int t= sc.nextInt();t>0;t--){
int m=sc.nextInt();
int n=sc.nextInt();
long d=1,r=1; int x=1,y=0,n1=n-2,m1=m-2;
System.out.print(d+r+"");
for(int i=2;i<=2*n-2;i++){
if(i%2==0){d=C(n1,x)*C(m1,y);r=C(m1,x)*C(n1,y++);}
else{d=(C(n1,x)*C(m1,y))%mod;r=(C(m1,x++)*C(n1,y))%mod;}
System.out.print(" "+(d+r)%mod);
}
System.out.print("\n");
}
}
static long mod=1000000007;
static long fn[]=new long[10001];
static long C(int n,int r){
if(r==n)return 1;
if(r>n)return 0;
long fr=moduloExp(fn[r],mod-2,mod);
long fnr=moduloExp(fn[n-r],mod-2,mod);
long c= ((fn[n]*fr)%mod*fnr)%mod;
return c;
}
static void fact(){
fn[0]=1;
for(int i=1;i<=10000;i++)fn[i]=(fn[i-1]*i)%mod;
}
static long moduloExp(long n,long p,long m){
if(n==1||p==0)return 1;
else if(p==1)return n;
else{
long pow=1;
while(p>0){
if((p&1)==1)pow=(pow*n)%m;
p=p>>1;
n=(n*n)%m;
}
return pow;
}
}
}
For doubts, please leave them in the comment section, I’ll address them.