CARPTUN - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

SIMPLE

PREREQUISITES:

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:

The answer is

(\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[1] seconds later than Reziba.
  • If A[1] < A[2], 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[2].
  • If A[1] > A[2], when Chef arrives the second tunnel, Reziba has already left. In this case, the time difference is A[1].
  • In conclusion, Chef exits the second tunnel \max(A[1],A[2]) seconds later than Reziba.

Let f[i][j] be the time that the i-th car exits from the j-th tunnel. Then f[2][k]-f[1][k]=\max(f[2][k-1]-f[1][k-1],A[k]). Thus f[2][n]-f[1][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).

ALTERNATIVE SOLUTION:

a dp solution

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

f[1][j]=f[1][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[1][\cdot] and f[2][\cdot], and the answer is

(C-1)(f[2][n]-f[1][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.

BTW, feel free to discuss about your approaches in comments!

AUTHORā€™S AND TESTERā€™S SOLUTIONS:

Authorā€™s solution can be found here.
Testerā€™s solution can be found here.

1 Like

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.

3 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[0];
            for (int j = 1; j < N; j++) {
                if (A[j] > A[j - 1]) {
                    delay = delay + (cars - 1) * (A[j] - (A[j - 1]));
                }
            }
            System.out.println((double) delay);//Giving AC answer
            System.out.println((float) delay);//why Giving wrong answer  



        }
    }
}

System.out.println((double) delay);//Giving AC answer
System.out.println((float) delay);//why Giving wrong answer

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

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 :slight_smile:

1 Like

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.

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 :slight_smile: