# CARPTUN - Editorial

Author: Abizer Lokhandwala
Tester: Hanlin Ren
Editorialist: Hanlin Ren

SIMPLE

Simple Math

### PROBLEM:

C cars are going through N tunnels. Each two consecutive tunnels are separated by a distance of D, and the speed of every car is S (the same). The i-th tunnel takes A[i] time to process a car, and if a new car enters a tunnel which is processing another car, it will wait until that car gets processed. If multiple cars enter, they line up as a queue. Initially, all N cars are in the queue of the first tunnel, and the first car is going to be processed. Suppose the first car exits tunnel N at time t_1 and the last car exits tunnel N at time t_2, compute t_2-t_1. The length of cars and tunnels are negligible.

### QUICK EXPLANATION:

(\max_{i=1}^nA[i])\cdot (C-1).

### EXPLANATION:

Let’s prove that the answer is (\max_{i=1}^nA[i]) \cdot (C-1). Consider the following scenario where n=C=2:

• There are two cars, Reziba and Chef. Chef exits the first tunnel A seconds later than Reziba.
• If A < A, when Chef arrives the second tunnel, Reziba’s car is still being(or, waiting to be) processed. In this case, Chef and Reziba exit the second tunnel at a time difference A.
• If A > A, when Chef arrives the second tunnel, Reziba has already left. In this case, the time difference is A.
• In conclusion, Chef exits the second tunnel \max(A,A) seconds later than Reziba.

Let f[i][j] be the time that the i-th car exits from the j-th tunnel. Then f[k]-f[k]=\max(f[k-1]-f[k-1],A[k]). Thus f[n]-f[n]=\max_{i=1}^nA[i]. By the same reasoning, f[j][n]-f[j-1][n]=\max_{i=1}^nA[i] for all j>1. That’s why the answer being simply

(\max_{i=1}^nA[i])\cdot(C-1).

## a dp solution

Recall the definition of f[i][j] above. For the first car, f[j] is easy to compute:

f[j]=f[j-1]+D/S+A[j].

For the i-th car, we have

f[i][j]=\max(f[i][j-1]+D/S,f[i-1][j])+A[j],

since if the (i-1)-th car already exited the j-th tunnel, it doesn’t affect the i-th car, and the answer is f[i][j-1]+D/S+A[j]; otherwise the i-th car has to wait for him, and the answer is f[i-1][j]+A[j].

This solution has time complexity O(nC).

In fact, the exit time for C cars form an arithmetic progression, so we only need to compute f[\cdot] and f[\cdot], and the answer is

(C-1)(f[n]-f[n]).

This is, in principle, correct. However it shouldn’t pass system test since we require an absolute error of 10^{-6} and the answer is around 10^{15}. This means our solution should have a relative error of 10^{-21}, which is not realistic even for 64-bit floating point numbers.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

2 Likes

I found it quite silly that unnecessary data was given (D and S) and that the answer was to be provided as a “real” number when the answer is guaranteed to be an integer. Not personally a fan of questions with red herrings, but ignoring that it’s a nice simple question.

I’m actually very surprised that this is only the fourth most solved question, since I thought the realization that \max(A) was the limiting factor was quite obvious. Would never have guessed someone would try doing DP on this problem.

2 Likes

https://www.codechef.com/viewsolution/17437158
Can anyone tell me the case/ cases where my code fails? I just find out the difference of the time taken to cross the nth tunnel by the first and second car and multiply by (c-1) .

import java.util.Scanner;
public class CARPTUN {

    public static void main(String[] args) {
//   System.out.println((double)5/6);

Scanner s = new Scanner(System.in);
int T = s.nextInt();
for (int i = 0; i < T; i++) {
int N = s.nextInt();
int A[] = new int[N];
for (int j = 0; j < N; j++) {
A[j] = s.nextInt();
}
int cars = s.nextInt();
int distance = s.nextInt();
int speed = s.nextInt();

long delay = (cars - 1) * A;
for (int j = 1; j < N; j++) {
if (A[j] > A[j - 1]) {
delay = delay + (cars - 1) * (A[j] - (A[j - 1]));
}
}

}
}
}


*is it true we can not typecast long into float datatype but can long in double… ? why plz *

Why even cast to a floating point type? The answer is an integer and you can print it as an integer.

Thats because floating time is less precise/accurate than double. Store {10}^{9} in double and in float and print upto 2 decimals, you will see I was not able think about the solution. All I was thinking was taking multiple queues for each tollbooth, but then I knew that this is silly, this is an easy problem. But I was not able to come to the solution. Only reason for my failure was that I didn’t read the problem correctly, anyways, I will take care next time. Nice lesson learned.

 This is, in principle, correct. However it shouldn't pass system test since we require an absolute error of 10−6 and the answer is around 1015. This means our solution should have a relative error of 10−21, which is not realistic even for 64-bit floating point numbers. 

I did not understand this statement completely. Since 64-bit floating point numbers can store up to 20 decimals places, the error in the first iteration would have an error of at most 10-20. And there would be N (105) iterations in the worst case so the error can get magnified to 10-15, right?. This is the error in the exit time f(i,j).

Then that would be multiplied by C (106) so it would get magnified to 10-9.

Can someone correct me? Really curious How can the answer be max(A[i])*(c - 1)?

Because what I suppose is we will need to add the time taken to travel from one toll booth to another as well. So it should be more than that.

Kindly explain this.