Minimum Cost Traversal

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given two arrays, A and B, each containing N positive integers, along with two integer switch costs, X and Y.

You must construct a sequence of N choices by traversing from index 0 to N-1. At each index i, you must choose exactly one element, either A[i] or B[i]. The value of the chosen element contributes to a running total cost.

An additional "switching cost" is incurred if your choice of array at index i is different from your choice at index i-1:

Switching from array A to B (choosing A[i-1] then B[i]) costs X. Switching from array B to A (choosing B[i-1] then A[i]) costs Y. Staying on the same array (e.g., A[i-1] then A[i]) has no switching cost.

Your goal is to find the minimum possible total cost to traverse from index 0 to N-1. The total cost is the sum of all chosen elements plus the sum of all incurred switching penalties.

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

Input Format:

The first line contains three space-separated integers: N, X, and Y.

The second line contains N space-separated integers for array A.

The third line contains N space-separated integers for array B.

Output Format:

Print a single integer representing the minimum possible total cost.

Sample Input 1:

4 10 10
1 1 1 1
100 100 100 100

Sample Output 1:

Explanation for Sample 1:

The cost to switch to array B is very high (100 per element + 10 switch cost). The optimal strategy is to stay on array A for the entire traversal. The total cost is the sum of elements in A: `1 + 1 + 1 + 1 = 4`.

Sample Input 2:

4 5 5
1 100 1 100
100 1 100 1

Sample Output 2:

Explanation for Sample 2:

It is always beneficial to switch arrays to pick the cheaper element, even with the switch cost.
- Path: A[0] -> B[1] -> A[2] -> B[3].
- Cost: `A[0]` = 1.
- Cost: `+ X + B[1]` = `1 + 5 + 1` = 7.
- Cost: `+ Y + A[2]` = `7 + 5 + 1` = 13.
- Cost: `+ X + B[3]` = `13 + 5 + 1` = 19.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= N <= 10^5
0 <= X, Y <= 1000
1 <= A[i], B[i] <= 1000

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Minimum Cost Traversal

Console