Minimum time to cross all checkpoints

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contains an integer 'N', denoting the index of the last checkpoint. The second line of each test case contains 'N' space-separated integers denoting the first column of the matrix 'TIME'. The third line of each test case contains 'N' space-separated integers denoting the second column of the matrix 'TIME'. The fourth line of each test case contains 'N-1' space-separated integers denoting the first column of the matrix 'CHECKPOINTS'. The fifth line of each test case contains 'N-1' space-separated integers denoting the second column of the matrix 'CHECKPOINTS'.

For the first test case : Mr. X can start his journey at Lane-0, and does not need to switch lanes at all. The total time of travel will be 4 (2+2) in this case. For the second test case: Mr. X can start his journey at Lane-0 and move to Checkpoint-1 taking 1 unit of time, then switch Lanes at Checkpoint-1 taking 1 unit of time. Now, he is at Checkpoint-2 at Lane-1. Then, he will move to Checkpoint-3 taking 1 unit of time. The total travel time will be 3 (1+1+1) in this case.

Recursive Approach

The idea is to use a recursive approach to find the minimum time to reach Ninjaland. The recursive idea is very clear that for any checkpoint at any of the two lanes, there are only two choices, either continue moving along the same lane or switch between the two lanes. Using this idea we can calculate the minimum travel time recursively.

We will define a function GET_MIN_TIME(i,j) to find the minimum time it takes to reach Checkpoint i at Lane-j. After defining the function, we can call it to find the Minimum Time it takes to reach Checkpoint ‘N’, at Lane-0 and Lane-1. Our final answer will be the Minimum among the two values.

Working of the Recursive function:

If i is equal to 1, then we will return TIME[0][j]. This will serve as the base case for our recursive function. Note that for Checkpoint-1 there is only 1 choice.
If j is equal to 0, then we will return the minimum value among GET_MIN_TIME(i-1,0) + Time[i-1][0] and GET_MIN_TIME(i-1,1) + CHECKPOINTS[i-2][1]. As we can see that to reach Checkpoint ‘i’ at Lane-0 there are only two choices, either come to Checkpoint i-1 at Lane-0, and move along the same lane, come to Checkpoint i-1 at Lane-1, and switch lanes. So, we are comparing the two results and taking the minimum value among them.
Otherwise, we will return the minimum value among GET_MIN_TIME(i-1,1)+Time[i-1][1] and GET_MIN_TIME(i-1,0)+CHECKPOINTS[i-2][0]. As we can see that to reach Checkpoint ‘i’ at Lane-1 there are only two choices, either come to Checkpoint ‘i-1’ at Lane-1, and move along the same lane, come to Checkpoint ‘i-1’ at Lane-0, and switch lanes. So, we are comparing the two results and taking the minimum value among them.

Time Complexity

O(2^N), where ‘N’ is the index of the last checkpoint.

In each recursive call to the getMinFunction we are making 2 recursive calls. Therefore, for ‘N’ checkpoints, we will be calling the getMinFunction 2^N times. Hence, the overall time complexity is O(2^N).

Space Complexity

O(N), where ‘N’ is the index of the last checkpoint.

The recursion depth will be ‘N’. Hence, the overall space complexity is O(N)).

Minimum time to cross all checkpoints

Problem statement

Sample Input 1:

Sample Output 1:

Explanation for Sample Input 1:

Sample Input 2:

Sample Output 2:

O(2^N), where ‘N’ is the index of the last checkpoint.

O(N), where ‘N’ is the index of the last checkpoint.