Number of Days to Enjoy

Hard
0/120
Average time to solve is 50m
profile
Contributed by
3 upvotes
Asked in companies
ShareChatIntuit

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 3
20 10 10
10 20 10
10 10 20
0 1 1
1 0 1
1 1 0
3 5
0 0 0 0 30
10 10 10 10 0
20 20 20 20 0
0 1 0
1 0 1
1 1 0
Sample Output 1 :
60 
100
Explanation For Sample Input 1 :
For test case 1 :
We will print 60 because:
Ninja will spend the first month in Country-1 and enjoy 20 days, he will then teleport to Country-2 for the second month and again spend 20 days enjoying, and for the last month, he will get transported to Country-3 and spend 20 days enjoying over there. In total he has spent 20 + 20 + 20 = 60 days enjoying himself.

For test case 2 : 
We will print 100 because:
Ninja will get himself teleported to Country-2 in the first month itself and spend the first month in Country-2 and enjoy 10 days, he will get teleported to Country-3 in the second month and enjoy 20 days in the second month, he will continue to stay in Country-3 for the 3’rd and 4’th month and spend 20 days in each of these months enjoying himself. He will finally get teleported to Country-1 in the fifth month and enjoy 30 days there. In total he has spent 10 + 20 + 20 + 20 + 30 = 100 days enjoying himself.
(Note: a better answer could have existed if he visited Country-3 in the first month, but teleportation from Country-1 to Country-3 was not possible).
Sample Input 2 :
2
1 2
10 20
0
2 1
10
20
0 1
1 0
Sample Output 2 :
30
20
Hint

Try to stimulate the moves, to visit the i’th country in the j’th month, try exploring all the options for the (j-1)’th month that will allow us to visit the i’th country in the j’th month.

Approaches (3)
Recursion

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.
Time Complexity

O( N ^ M ), where N denotes the number of countries and M denotes the number of months

 

In the worst case when all the countries can be teleported from each other, then for each month we will have an option to visit one of the N countries, and in total, we will have ~N^M ways.

Hence the time complexity is O( N^M ).

Space Complexity

O( M ), where N denotes the number of countries and M denotes the number of months

 

Recursion call will take space of order ~M.

Hence the space complexity is O( M ).

Code Solution
(100% EXP penalty)
Number of Days to Enjoy
Full screen
Console