PROBLEM LINK:
Setter: Avisek Mondal
Tester: Manik Goenka
Editorialist: Saranya Naha Roy
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
We have K coins initially. There are N{\times}N cells and each cell requires an exact cost of A(i,j) coins to enter. We have to enter from the top-left cell and reach to the bottom-right cell. If we are at cell (i,j) we can either move to (i+1,j) or (i,j+1). Find the number of possible ways at the expense of K coins or less to go to the bottom-left cell.
QUICK EXPLANATION:
If we are at cell (i,j) with C coins, number of ways to reach the bottom-left cell can be computed using the recursive equation:
fn(i,j,C) = fn(i,j+1,C-a[i][j+1]) +fn(i+1,j,C-a[i+1][j])
Hence the solution is: fn(0,0,K-a[0][0])\ where\ K\ is\ initial\ amount\ of\ coins
EXPLANATION:
Suppose we are at cell (i,j) and we have C coins. Now we can go to either cell (i,j+1) or cell (i+1,j). To enter cell (i,j+1) we need to expend A(i,j+1) coins and to enter cell (i+1,j) we need to expend A(i+1,j) coins. Now,
number\ of\ ways\ to\ reach\ from\ cell\ (i,j)\ to\ bottomleft\ cell\ = number\ of\ ways\ to\ reach\ from\ cell\ (i,j+1)\ to\ bottomleft\ cell+number\ of\ ways\ to\ reach\ from\ cell\ (i+1,j)\ to\ bottomleft\ cell\
But we will start from each cell with different amount of coins in hand as to enter a cell we need to expend some coins. Therefore, we get a recursive equation as:
fn(i,j,C) = fn(i,j+1,C-a[i][j+1]) +fn(i+1,j,C-a[i+1][j]) \ where\ fn(i,j,C)\ is \ number\ of\ ways\ to\ reach\ the\ bottom \operatorname{-} left\ cell\ if\ we\ start\ from\ cell\ (i,j)\ with\ C\ coins.
Hence the solution is: fn(0,0,K-a[0][0])\ where\ K\ is\ initial\ amount\ of\ coins
Now, if we start from a cell with number\ of\ coins<0, it means that we are not allowed to be in that cell. So in this case we return 0 from fn. If we reach the bottom left cell, we have arrived at our destination and we return 1 from fn as there is only one way to reach from a cell to the same cell.
Also at cell (i,j) we need to check if (i+1,j) and (i,j+1) exist inside N{\times}N matrix. Example: If we are at cell (0,N-1), then (0,N) does not exist so,
fn(0,N-1,coins)=fn(1,N-1,coins-a[1,n-1])
Time Complexity: O(2^n) [time complexity of the recursive equation]
SOLUTIONS:
Setter's Solution
Language: C++17 (gcc 9.1)
#include<bits/stdc++.h>
using namespace std;
int coin(vector<vector<int> >&a,int n,int k,int i,int j,int sum){
if(i>=n || j>=n)
return 0;
sum+=a[i][j];
if(i==n-1 && j==n-1 && sum<=k)
return 1;
else if(sum>k)
return 0;
return (coin(a,n,k,i,j+1,sum)+coin(a,n,k,i+1,j,sum));
}
int main()
{int t;
cin>>t;
while(t--){
int n,k,x;
cin>>k>>n;
vector<vector<int> > myvector;
vector<int>row;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>x;
row.push_back(x);
}
myvector.push_back(row);
row.clear();
}
cout<< coin(myvector,n,k,0,0,0)<<endl;;
}
return 0;
}
Tester's Solution
Language: Python3 (python 3.6)
def mario_princess(a,n,k,i,j,sum):
if i>=n or j>=n:
return 0
sum+=a[i][j]
if i==n-1 and j==n-1 and sum<=k:
return 1
elif sum>k:
return 0
return mario_princess(a,n,k,i+1,j,sum)+mario_princess(a,n,k,i,j+1,sum)
t=int(input())
while(t>0):
k=int(input())
n=int(input())
mat=[]
row=[]
row=list(map(int,input().split()))
for i in range(n):
mat.append(row[i*n:i*n+n])
print(mario_princess(mat,n,k,0,0,0))
t-=1
Editorialist's Solution
Language: C++17 (gcc 9.1)
#include <bits/stdc++.h>
using namespace std;
typedef long long int big;
// <Global Data>
int grid[10][10];
int n;
// </Global Data>
bool reached(pair<big, big> location)
{
return (location.first == n - 1 && location.second == n - 1);
}
pair<big, big> down(pair<big, big> location)
{
return {location.first + 1, location.second};
}
pair<big, big> right(pair<big, big> location)
{
return {location.first, location.second + 1};
}
bool is_exist(pair<big, big> location)
{
return (location.first >= 0 && location.first <= n - 1 && location.second >= 0 && location.second <= n - 1);
}
big cost(pair<big, big> location)
{
return grid[location.first][location.second];
}
big try_to_reach(pair<big, big> location, int money)
{
// cout << location.first << " " << location.second << "," << money << "\n";
if (money < 0)
{
return 0;
}
if (reached(location))
{
return 1;
}
int ans = 0;
pair<big, big> right_location = right(location);
pair<big, big> down_location = down(location);
if (is_exist(right_location))
{
ans += try_to_reach(right_location, money - cost(right_location));
}
if (is_exist(down_location))
{
ans += try_to_reach(down_location, money - cost(down_location));
}
return ans;
}
int main()
{
//ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);//comment when not needed
big t = 1;
cin >> t;
while (t--)
{
big k;
cin >> k;
cin >> n;
for (big i = 0; i < n; i++)
{
for (big j = 0; j < n; j++)
{
cin >> grid[i][j];
}
}
cout << try_to_reach({0, 0}, k - cost({0, 0})) << "\n";
}
return 0;
}