Problem 4 [30 pts] Greedy/Dynamic Programming Suppose that there are n gas stations along a circular route. The target i

[answerhappygod]

Problem 4 30 Pts Greedy Dynamic Programming Suppose That There Are N Gas Stations Along A Circular Route The Target I 1 (69.78 KiB) Viewed 47 times

Problem 4 [30 pts] Greedy/Dynamic Programming Suppose that there are n gas stations along a circular route. The target is to start from any potential gas station i move to i +1,i+2.... and return to the starting location i without running out of gas. Additionally, you are given two integer arrays G and C of length 1. G represents the amount of gas you refill in station i, while C indicates the amount of gas you need to consume to visit the next station i +1. Design an algorithm such that it finds a potential starting location i. Note that in cach gas station you refill the maximum amount available and the tank does not have a limit. Also, it is possible that you might not be able to complete the trip, thus your algorithm should return -1. For example, given the two arrays below, we could start the trip from i = 3. Meaning we start with 20 gallons in our tank. To move to station i = 4, we consume 5 gallons, leaving 15 gallons in the tank. In location i = 4 we refill 1 gallon increasing the tank to 16 gallons and consume 6 to visit station i = 1. Skipping a few steps, we finally arrive to our starting point i = 3 with 9 gallons left in our tank. Note that it is not possible to start from any other gas station. For example, if we start from the gas station at position i = 1 we refill 2 gallons and consume 1 gallon to visit i = 2. The tank contains 1 gallon and we refill with 3 more gallons, but to get to the next station we need 5 gallons, which is not enough since we only got 4 gallons in the tank. 1 2 3 4 G (gas refill) 2 3 201 C (gas consumption) 155 6