CARPTUN - Editorial

r_64 · February 3, 2018, 6:22pm

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.

algmyr · February 13, 2018, 4:01am

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.

battlejonin · February 13, 2018, 11:35pm

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) .

hemant_dhanuka · February 15, 2018, 11:03pm

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 *

algmyr · February 16, 2018, 7:48pm

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

vijju123 · February 16, 2018, 8:58pm

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

jaksparo · February 17, 2018, 12:28pm

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.

rushilpaul · March 5, 2018, 8:22pm

``` This is, in principle, correct. However it shouldn't pass system test since we require an absolute error of 10⁻⁶ and the answer is around 10¹⁵. This means our solution should have a relative error of 10⁻²¹, 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 (10⁵) 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 (10⁶) so it would get magnified to 10^-9.

Can someone correct me? Really curious

shraeyas · April 21, 2018, 10:58am

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.