Last Updated: 14 Oct, 2021
Number of Days to Enjoy
Hard
Asked in companies
After a hectic schedule at the office, Ninja has decided to take off for the next ‘M’ months (each month has exactly 30 days). There are ‘N’ countries that he can visit during his vacations.
But there is a restriction on every country, a person can only stay outside for limited days in a month in a particular country, you are given a matrix ‘Restriction’ where 'Restriction[i][j]' denotes that the i’th country allows a person to enjoy only 'Restriction[i][j]' days in the j’th month.
There is a magical teleportation tunnel that can directly transfer Ninja from one country to another, this tunnel only operates on the first day of each month and can be only used once a month. You are given a matrix ‘Teleport’ of size N*N where Teleport[i][j] = 1 denotes that a person can be teleported from i’th country to the j’th country.
You need to help Ninja by telling him the maximum days that he can enjoy during his vacations.
For Example :
If N = 3 and M = 3
Restriction = { { 20, 10, 10 }, { 10, 20, 10 }, { 10, 10, 20 } }
Teleport = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 0 } }
Then the Ninja can spend the first month in Country-1 and spend 20 days of the first month by going outside and enjoying himself, and the remaining 10 days of the first month will need to be spent inside his house (without enjoying).
As there is a teleportation path from Country-1 to Country-2 so Ninja will get himself teleported to Country-2 in the second month and spend 20 days there enjoying himself.
For the third month, as there is a teleportation path from Country-2 to Country-3 so Ninja will get himself teleported to Country-3 in the third month and spend 20 days there enjoying himself.
In total, he will spend 20 + 20 + 20 = 60 days enjoying his three months vacation.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains two integers ‘N’ and ‘M’ denoting the countries and number of vacation months respectively.
The next N lines each contain M integers, each denoting Restriction[i][j] (maximum days that a person can enjoy in i’th country in j’th month).
The next N lines each contain N integers, each denoting Teleport[i][j] (possibility of getting teleported from i’th country to j’th country).
Output Format :
For each test case, print the maximum days that Ninja can enjoy during his vacations.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 25
1 ≤ M ≤ 100, each month consists of exactly 30 days
Restriction.length = N
Restriction[i].length = M
0 ≤ Restriction[i][j] ≤ 30
Teleport.length = N
Teleport[i].length = N
0 ≤ Teleport[i][j] ≤ 1, Teleport[i][i] = 0
Time limit: 1 sec
Approaches
If you want to see the detailed explanation skip to Approach-3 directly.
To solve this problem, we need to find the country we will be visiting in the last month of our vacation, we can simply calculate the answer for each of the N countries when visited in the last month and return the maximum one out of them.
If we want to find the answer for the spending the j’th month in the i’th country, we will recursively calculate the answer from all the options we have to visit in the (j-1)’th month such that we can then spend the j’th month in the i’th country. Here we can only visit those countries in the (j-1)’th month that allows teleportation to the i’th country, also a trivial case of spending the (j-1)’th month in the i’th country should not be missed as also have an option to not teleport and remain in the current country.
The steps are as follows :
- Mark the countries that cannot be visited in the initial month, these countries don’t allow teleportation from the 0’th country, this will be used as our base condition to end the recursion.
- Explore all the countries to be visited in the last month, that is: make the initial recursive call by passing the value of the current month equal to M-1(last month).
- In the recursive function, check the base condition and return the recursion call if we are currently at the initial month. Else calculate the value using a variable ‘var’ by making a recursive call for the j-1’th month from all the countries that be visited according to the logic discussed above.
- Finally, return the optimal answer corresponding to the country visited in the last month.
If you want to see the detailed explanation skip to Approach-3 directly.
To solve this problem, we need to find the country we will be visiting in the last month of our vacation, we can simply calculate the answer for each of the N countries when visited in the last month and return the maximum one out of them.
If we want to find the answer for the spending the j’th month in the i’th country, we will recursively calculate the answer from all the options we have to visit in the (j-1)’th month such that we can then spend the j’th month in the i’th country. Here we can only visit those countries in the (j-1)’th month that allows teleportation to the i’th country, also a trivial case of spending the (j-1)’th month in the i’th country should not be missed as also have an option to not teleport and remain in the current country.
Further for all the (i, j) store the value computed in a DP matrix so that we don’t have to recompute these values again and again. This is a standard memoization technique and helps us to convert an exponential time complexity into a polynomial time.
The steps are as follows :
- Initialize a ‘dp’ matrix of size equal to N * M to avoid recomputation.
- Mark the countries that can be visited in the initial month, these countries allow teleportation from the 0’th country, this will be used as our base condition to end the recursion.
- Explore all the countries to be visited in the last month, that is: make the initial recursive call by passing the value of the current month equal to M-1(last month).
- In the recursive function, check the base condition and return the recursion call if we are currently at the initial month. Also check if the current value for (i, j) has been precomputed or not, in case it has already been precomputed then simply return the value, no need to recalculate it, if the value is not calculated till now then calculate the value by making a recursive call for the j-1’th month from all the countries that be visited according to the logic discussed above store the calculated value in the ‘dp’ matrix so that we don’t have to recompute it again.
- Finally, return the optimal answer corresponding to the country visited in the last month.
It is easy to notice that a simple greedy approach won’t work here as you might end up going to a country that has no further teleportation possible and you will get stuck in that country which might not result in an optimal answer.
In situations like these, dynamic programming comes in handy. How to get intuition? Try to think of the DP states in such a way that you can easily find the value of that state by using some transitions, once you are able to figure out the DP states then it is quite easy to figure out the transitions. For example, assume that there is a condition that you compulsorily have to visit the i’th country in the j’th month, then the maximum days you can enjoy in the first ‘j’ months will be stored in dp[i][j]. Now once we have defined our states, we can easily build up the logic of DP transitions, to reach the i’th country in the j’th month we can come from one of the countries that can teleport us to the i’th country after spending the (j-1)’th month over there, or we can continue to stay in the i’th country after spending the (j-1)’th month.
Finally, we can return the maximum value after spending the M’th month in one of the countries. Why? Because we will visit at least one of the countries in the last month!
The steps are as follows :
- Declare ‘dp’ matrix of N rows and M columns and initialize all the values to INT_MIN, dp[i][j] denotes the maximum days a person can enjoy in the first ‘j’ months if he compulsorily spends j’th month in the i’th country.
- To mark the countries that can be visited int he initial month, update dp[0][0] to Restriction[0][0], now fill up the first column (first month) of the dp matrix. For all ‘i’ in range 0 to N-1, if Teleport[0][i] equal to 1, then update dp[i][0] to Restriction[i][0].
- Now, to fill the remaining matrix, run an outer loop for variable ‘j’ from 1 to M-1 and run a middle loop for variable ‘i’ from 0 to N-1, to calculate the value of dp[i][j] run an innermost loop for variable ‘prev’ from 0 to N-1, now if either ‘i’ equals to ‘prev’ or Teleport[prev][i] equals to 1 then set dp[i][j] equal to maximum of dp[i][j] and dp[prev][j-1] + days[i][j].
- Finally, return the maximum value in the last column of ‘dp’ matrix.