Metro Transit Planner

Easy

0/40

0 upvote

Asked in company

Problem statement

You are an engineer for a city's Metro Transit Authority, tasked with planning a maintenance route on the main circular subway line. The travel time between consecutive stations is not uniform due to track conditions.

You are given:

- An array trans of m travel times. trans[i] is the time it takes to go from station i+1 to station i+2. The final element, trans[m-1], is the time from station m back to station 1.

- An array req containing a sequence of stations that must be inspected in a specific order.

You start at Station 1. For each required inspection, you must travel from your current location to the next station in the req list. Since the track is circular, you can travel either clockwise or anti-clockwise. To be efficient, you must always choose the path that takes less time.

Your job is to calculate the total minimum time required to complete the entire sequence of inspections.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer m, the number of stations on the circular line.

The second line contains m space-separated integers for the trans array. trans[i] represents the travel time from station i+1 to station i+2 (with station m connecting back to 1).

The third line contains an integer p, the number of stations in the required inspection sequence.

The fourth line contains p space-separated integers for the req array.

Output Format:

The output should be a single integer representing the total minimum travel time.

Note:

The total time to travel around the entire circular track once is the sum of all elements in the trans array.

To find the time from a station A to a station B:
- Calculate the clockwise travel time.
- The anti-clockwise time is (Total Track Time) - (Clockwise Time).
- The time for that leg of the journey is the minimum of these two values.

The total time is the sum of these minimums for each step in the req sequence.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

Stations: 4. Times: 1->2 (10), 2->3 (20), 3->4 (15), 4->1 (5). Total track time = 50.

Requirement: Visit station 3, then station 1.

Step 1: Start at 1, go to 3.
- Clockwise (1->2->3): 10 + 20 = 30.

- Anti-clockwise (1->4->3): 5 + 15 = 20.

- Minimum is 20. Current location is now 3.

The maximum length among these is 5.

Sample Input 2:

Sample Output 2:

Explanation for Sample 2:

Stations: 5. Total track time = 2+3+4+5+6 = 20.

Requirement: Visit 2, then 3, then 4.
- Step 1 (1 -> 2): Clockwise is 2. Anti-clockwise is 20-2=18. Min is 2.

- Step 2 (2 -> 3): Clockwise is 3. Anti-clockwise is 20-3=17. Min is 3.

- Step 3 (3 -> 4): Clockwise is 4. Anti-clockwise is 20-4=16. Min is 4.

Total Time = 2 + 3 + 4 = 9.

Expected Time Complexity:

The expected time complexity is O(M + P), where M is the number of stations and P is the length of the requirement sequence.

Constraints:

2 <= m <= 10^5
1 <= p <= 10^5
1 <= trans[i] <= 1000
1 <= req[i] <= m

Time limit: 1 sec

Approaches (1)

Approach 1

Prefix Sum for Path Calculation

Time Complexity

Space Complexity

(100% EXP penalty)

Metro Transit Planner

Console