charan2628's blog

By charan2628, history, 2 months ago, In English

A car is moving on a straight line of length N meters.

The car has a fixed fuel tank capacity of K liters and it spends 1 liter per meter. There are M fuel filling stations along the straight line where the ith station is located at position a[i] and sells 1 liter of fuel for b[i] dollars.

It is given that the car can only refill the tank fully when it stops at some station for refueling. This means that if the tank contains 3 liters and its capacity was 10 liters, the car can buy exactly7 liters of fuel (otherwise the car will not stop at the fuel station for refueling).

Given that the car starts at position 0 moving in one direction to the end of the line and it can buy fuel from any fuel station it stops at. Your task is to choose which stations to buy from in order to reach the end of the line with the minimum possible cost. If it’s impossible to reach the end of the line return -1.

Note: It is guaranteed that there is always a fuel station at position 0.

Input Format The first line contains an integer, N, denoting the length of the road.
The next line contains an integer, K, denoting the tank's capacity.
The next line contains an integer, M, denoting the number of elements in a (the number of stations).
Each line i of the M subsequent lines (where 0 ≤ i < M) contains an integer describing ai (stations' locations).
Each line i of the M subsequent lines (where 0 ≤ i < M) contains an integer describing bi (the cost of one liter in each station).

Constraints
1 <= N <= 10^5
1 <= K <= 10^5
1 <= M <= 10^3
1 <= a[i] <= N
1 <= b[i] <= 10^9

Sample Input Sample Output Explanation
10
5
4
0
4
5
8
1
2
3
4 16

10
5
3
0
1
4
1
3
2 -1

This is what I tried but giving wrong answer

static long[] dp;
	
	public static long car_recur(int N,int K,int M,int[] a,int[] b){
		dp = new long[M];
		Arrays.fill(dp, -1);
		
		long ans = Long.MAX_VALUE;
		for (int i = M - 1; i >= 0; i--) {
			if (a[i] != N && N - a[i] <= K) {
				long tmp = recur(i, K, a, b);
				if (tmp != -1) {
					ans = Math.min(ans, tmp);
				}
			}
		}
		return ans == Long.MAX_VALUE ? - 1 : ans;
	}
	
	private static long recur(int fuelStop, int K, int[] a, int[] b) {
		if (dp[fuelStop] != -1) return dp[fuelStop];
		if (fuelStop == 0) return (long)b[0] * K;
		long ans = Long.MAX_VALUE;
		for (int i = fuelStop - 1; i >= 0; i--) {
			if (a[fuelStop] - a[i] <= K) {
				long tmp = recur(i, K, a, b);
				if (tmp != -1) {
					ans = Math.min(ans, tmp + b[fuelStop] * (a[fuelStop] - a[i]));
				}
			}
		}
		return dp[fuelStop] = ans == Long.MAX_VALUE ? -1 : ans;
	}
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is not from any running contest. This is a practice question from internal site which I can't share. Trying this problem from 2 days no luck at all.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

State: dp[i][k] = Minimum cost to reach point N from i if we have left with k fuel

Transition: dp[i][k] = min(b[i]*(total-k) + dp[i+1][total-(pos[i+1]-pos[i])], dp[i+1][k-(pos[i+1]-pos[i])])

base case: dp[n][anything] = 0

Final answer: dp[0][0]

But we can not create the DP matrix of $$$M * K$$$ size so we need to optimize space complexity.

Code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your comment. We have to sort the positions before using, after sorting by positions my code failed on 2 out of 13 test cases.

    I don't think we need the k variable in the dp array because as stated in the question we are filling the tank to full capacity if we stop at a station.

    Your C++ code throwing RunTime error don't know why.