Last Updated: 23 Aug, 2021
Ninja's Trip
Moderate
Asked in companies
Ninja is willing to take some time off from his training and planning a year-long tour.
You are given a DAYS array consisting of ‘N’ days when Ninjas will be traveling during the year. Each Day is an integer between 1 to 365 (both inclusive).
Train tickets are sold in three different ways:
A 1-day pass is sold for 'COST'[0] coins,
A 7-day pass is sold for 'COST'[1] coins, and
A 30-day pass is sold for 'COST'[2] coins.
The passes allow for many days of consecutive travel.
Your task is to help the Ninja to find the minimum number of coins required to complete his tour.
For example,
If Ninja gets a 7-day pass on day 2, then he can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N,’ denoting the number of days Ninja wants to travel.
The second line of each test case has ‘N’ sorted integers corresponding to the DAYS.
The third line of each test case contains a 'COST' array having three integers corresponding to the 'COST' of a 1-day pass, a 7-day pass, and a 30-day pass.
Output Format:
For each test case, print a single integer corresponding to the minimum number of coins required to travel every day in the given list of days
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 365
1 <= DAYS[i] <= 365
Time Limit: 1 sec
Approaches
In this approach, we will traverse each day recursively and if we are not traveling on that day, we will wait to buy a pass. Otherwise, we have three choices to buy a pass ( a 1-day, 7-day, or 30-day pass).
We can express those choices as recursion and use dynamic programming. Let's say 'DP'[i] is the 'COST' to fulfill your travel plan from day ‘i’ to the end of the plan. Then, if you have to travel today, your 'COST' is:
'DP'[i] = min('DP'[i+1] + 'COST'[0], 'DP'[i+7] + 'COST'[1], 'DP'[i+30] + 'COST'[2])
And if ith day is not a 'TRAVELDAY':
'DP'[i] = 'DP'[i+1]
We will an array 'TRAVELDAY' to check whether the ith day is travel day or not.
Algorithm:
- We will define a recursive function helper(i, 'COST', 'TRAVELDAY') that will return the minimum 'COST' of the trip from the ith day to the end of the trip.
- Defining helper'(i, 'COST', 'TRAVELDAY', 'MEMO'):
- If i is greater than 365 (Base case of recursion), return 0.
- If 'TRAVELDAY'[i] is equal to 0, that means Ninja is not traveling on that day
- Return helper(i+1,'COST','TRAVELDAY') (Not buying any pass)
- Otherwise
- Return the minimum of helper(i+1,'COST','TRAVELDAY')+'COST'[0], helper(i+7,'COST','TRAVELDAY')+'COST'[1], helper(i+30,'COST','TRAVELDAY')+'COST'[2]. (Recursively calling for all 3 choices).
- Declare two arrays of size 366 'TRAVELDAY'.
- Initialize all the values of 'TRAVELDAY' with 0.
- For each day in ‘DAYS’ array:
- Set 'TRAVELDAY'[day] as 1.
- Declare a variable ‘ANS’ to store the answer.
- Set ‘ANS’ as helper(1,'COST','TRAVELDAY').
- Return ‘ANS’.
In this approach, we will traverse each day recursively and if we are not traveling on that day, we will wait to buy a pass. Otherwise, we have three choices to buy a pass ( a 1-day, 7-day, or 30-day pass).
We can express those choices as recursion and use dynamic programming. Let's say 'DP'[i] is the 'COST' to fulfill your travel plan from day ‘i’ to the end of the plan. Then, if you have to travel today, your 'COST' is:
'DP'[i] = min('DP'[i+1] + 'COST'[0], 'DP'[i+7] + 'COST'[1], 'DP'[i+30] + 'COST'[2])
And if ith day is not a 'TRAVELDAY':
'DP'[i] = 'DP'[i+1]
We will use two arrays one 'TRAVELDAY' to check whether the ith day is travel day or not and 'MEMO' for memoization of this recursion.
Algorithm:
- We will define a recursive function helper(i, 'COST', 'TRAVELDAY', 'MEMO') that will return the minimum cost of the trip from the ith day to the end of the trip.
- Defining helper(i, 'COST', 'TRAVELDAY', 'MEMO'):
- If i is greater than 365 (Base case of recursion), return 0.
- If the answer for helper(i,’COST’, ’MEMO’) is previously calculated, we will use that value.
- If 'MEMO'[i] is not equal to -1.
- Return 'MEMO'[i].
- If 'TRAVELDAY'[i] is equal to 0, that means Ninja is not traveling on that day
- Set 'MEMO'[i] as helper(i+1,'COST','TRAVELDAY')(Not buying any pass)
- Otherwise
- Set 'MEMO'[i] as minimum of helper(i+1,'COST','TRAVELDAY')+'COST'[0], helper(i+7,'COST','TRAVELDAY')+'COST'[1], helper(i+30,'COST','TRAVELDAY')+'COST'[2]. (Recursively calling for all 3 choices).
- Return 'MEMO'[i].
- Declare two arrays of size 366 'TRAVELDAY' and 'MEMO'.
- Initialize all the values of 'MEMO' with -1.
- Initialize all the values of 'TRAVELDAY' with 0.
- For each ‘DAY’ in ‘DAYS’ array:
- Set 'TRAVELDAY'[day] as 1.
- Declare a variable ‘ANS’ to store the answer.
- Set ‘ANS’ as helper(1,'COST','TRAVELDAY','MEMO').
- Return ‘ANS’.
In approach 1, we are traversing through all the days of the year and calculating the minimum coins required. In this approach, we will just traverse through the given days on which Ninja is traveling.
Let 'DP'[i] denotes the minimum cost from the day 'DAYS'[i] to the end of the trip.Let ‘j1’ should be the smallest index such that 'DAYS'[j1] >= 'DAYS'[i] +1.
Simlarly ‘j7’ and ‘j30’ is the smallest index such that 'DAYS'[j7]>='DAYS'[i]+7 and 'DAYS'[j30]>='DAYS'[i]+30.Then
'DP'[i] = min('DP'[j1] +'COST'[0], 'DP'[j7] +'COST'[1], 'DP'[j30] +'COST'[2]).
Algorithm:
- Declare 'DP' array of size N+1.
- Set 'DP'[n] as 0.
- For each index i in range N-1 to 0,do the following:
- Set 'DP'[i] as max_int.
- Set j as i.
- While j < length of 'DAYS' and 'DAYS'[j] is less than 'DAYS'[i] +1
- Set j as j+1
- Set 'DP'[i] as the minimum of 'DP'[i] and 'DP'[j]+'COST'[0].
- Set j as i.
- While j < length of 'DAYS' and 'DAYS'[j] is less than 'DAYS'[i] +7
- Set j as j+1
- Set 'DP'[i] as the minimum of ans and 'DP'[j] + 'COST'[1].
- Set j as i.
- While j < length of 'DAYS' and 'DAYS'[j] is less than 'DAYS'[i] +30
- Set j as j+1
- Set 'DP'[i] as the minimum of 'DP'[i] and 'DP'[j] + 'COST'[2].
- Return 'DP'[0] representing the minimum coins required from 'DAYS'[0] to the end of the tour.
In the previous approach, we will just traverse through the given days on which Ninja is traveling and storing them in a DP table.
In this approach, we will create two queues named ‘WEEK’ and ‘MONTH’.These queues will store pairs that will denote {day, cost till that day}. Then we will iterate over all traveldays and insert them into the queue and also remove elements from these queues if the pass expires. The cheapest pass price will always be the front element of the queue.
Algorithm:
- Declare a variable ANS to store the minimum cost of the whole trip.
- Set ANS as 0.
- Declare two queues ‘MONTHPASS’ and ‘WEEKPASS’.
- For all ‘DAY’ in ‘TRAVELDAY’, do the following:
- If passes in ‘MONTHPASS’ got expired, remove them.
- While ‘MONTHPASS’ is not empty and ‘MONTHPASS’ front element ‘s day +30 <= ‘DAY’:
- Remove the front element of ‘MONTHPASS’.
- If passes in ‘WEEKPASS’ got expired, remove them.
- While ‘WEEKPASS’ is not empty and ‘WEEKPASS’ front element ‘s day +7 <= ‘DAY’:
- Remove the front element of ‘WEEKPASS’.
- Insert {‘DAY’ ,ANS + COST[1]} into ‘WEEKPASS’.
- Insert {‘DAY’ ,ANS + COST[2]} into ‘MONTHPASS’.
- Set ANS as minimum of (ANS+COST[0], ’WEEKPASS’ front element’s cost ,‘MONTHPASS’ front element’s cost).
- Return ANS.
Similar problems