Sinbad's Journey

Easy

0/40

0 upvote

Asked in company

Problem statement

Sinbad is traveling along a path of N points, numbered 0 to N-1. He starts at point 0 with an initial energy E and aims to reach the final point N-1.

Along the path, there are two factors that affect his journey:

1) Energy Stations: An array energy where energy[i] is the amount of energy Sinbad gains upon arriving at point i. He can only gain energy from a station once.

2) Wind: An array wind where wind[i] is the wind speed at point i. The wind affects the cost to travel from point i to i+1.

If wind[i] is positive (helpful wind), the cost to move is 0.

If wind[i] is negative (hindering wind), the cost to move is 1 + abs(wind[i]).

If wind[i] is zero, the base cost to move is 1.

On each day, Sinbad is at a point i and attempts to move to i+1.

1) If his current energy is greater than or equal to the travel cost, he pays the cost, moves to point i+1, and then immediately gains the energy energy[i+1] from the new point.

2) If his current energy is less than the travel cost, he is stuck and cannot move. The journey fails.

Your task is to find the maximum energy Sinbad can have upon arriving at point N-1. If he can never reach the final point, return -1.

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

Input Format:

The first line contains two space-separated integers: N and E (initial energy).

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

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

Output Format:

Print a single integer representing the maximum energy at the destination.

If the destination is unreachable, print -1.

Note:

The journey is a linear simulation from left to right.

Sample Input 1:

3 5
0 0 0
0 -10 0

Sample Output 1:

-1

Explanation for Sample 1:

1.  Start at point 0: Initial energy E=5. Gains `energy[0]=0`. Current energy = 5.
2.  Move 0 -> 1: `wind[0]=0`. Cost = 1. Energy `5 >= 1`.
- Pays cost: `5 - 1 = 4`.
- Arrives at point 1, gains `energy[1]=0`. Current energy = 4.
3.  Move 1 -> 2: `wind[1]=-10`. Cost = `1 + abs(-10) = 11`.
- Sinbad's energy (4) is less than the cost (11). He cannot move.

The journey is impossible.

Sample Input 2:

4 10
0 5 0 10
0 -2 1 0

Sample Output 2:

Explanation for Sample 2:

1.  Start at point 0: Initial energy E=10. Gains `energy[0]=0`. Current energy = 10.
2.  Move 0 -> 1: `wind[0]=0`. Cost = 1. Energy `10 >= 1`.
- Pays cost: `10 - 1 = 9`.
- Arrives at point 1, gains `energy[1]=5`. Current energy = `9 + 5 = 14`.
3.  Move 1 -> 2: `wind[1]=-2`. Cost = `1 + abs(-2) = 3`. Energy `14 >= 3`.
- Pays cost: `14 - 3 = 11`.
- Arrives at point 2, gains `energy[2]=0`. Current energy = `11 + 0 = 11`.
4.  Move 2 -> 3: `wind[2]=1`. Cost = `0`. Energy `11 >= 0`.
- Pays cost: `11 - 0 = 11`.
- Arrives at point 3, gains `energy[3]=10`. Final energy = `11 + 10 = 21`.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

2 <= N <= 10^5
0 <= E <= 10^9
0 <= energy[i] <= 1000
-1000 <= wind[i] <= 1000

Time limit: 1 sec

Approaches (1)

Approach 1

Greedy

Time Complexity

Space Complexity

(100% EXP penalty)

Sinbad's Journey

Console