HIGHWAYC - Editorial

general
, , , , ,
1

PROBLEM LINK:

Div1
Div2
Practice

Setter- Ashesh Vidyut
Tester- Misha Chorniy
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Math, Implementation, Dealing with floating points & similar etc.

Several interpretations about domain and category of this problem are possible. One may see it as one of Physics numerical of type Kinematics, others may see it as Vectors in Maths, while some may compare it to Geometry by using 2-D graph and due to the fact that this concept of distance being >{10}^{-6} is used in many similar geometry problems.

PROBLEM:

We have to find the minimum time taken by Chef to cross N lanes without getting hit by a car (i.e. distance Dist between Car’s front or side and Chef must be such that Dist> {10}^{-6}). All relevant information like Car’s initial position, velocity, direction and length are provided to us.

QUICK EXPLANATION:

The logic and math of this problem is very easy to get, and hence the problem boils down to careful and accurate implementation. We divide the solution into cases, like when Chef will have to wait for the car, when Chef can cross lane without waiting for car etc. We must make sure to use correct data-types, and mind the gap of {10}^{-6}.

EXPLANATION:

There isn’t much to explore in this question with respect to time complexity, as a straight-forward O(N) solution is possible. We will discuss the various approaches used by Editorialist and Tester. Setter’s approach is a hybrid between the two, and hence will be left as an exercise to work on (his code is commented for easier understanding :slight_smile: ).

1. Editorialist’s Solution-

My basic idea is inspired from divide and conquer. (Divide the problem into cases which are easy to conquer xD).

The car passes Chef when the back of car is at y=0. So I calculated a few things, such as back of car when t=0 (i.e. B_0) and back of car when current moment (i.e B_t). I then identified the following cases-

**a.**If the car is moving in positive direction, and its back is ahead of y=0 at t=0 (i.e. car has crossed y=0 already), and vice-versa if car is moving in negative direction, OR if the car has already crossed the lane by the time Chef reaches lane i, then make Chef cross the lane immediately.
b. As an extension to first case, if the car cannot reach Chef by the time he crosses the lane, defined by front and rear of car being at a distance of at least {10}^{-6} by the time Chef crosses the lane, then make Chef cross the lane immediately.
c. For ALL other cases, car will hit Chef if he doesn’t wait. Hence, add to ans the time taken by car to cross y=0 and by Chef to cross the lane.

Print upto 3 decimal places and we are done :slight_smile:

Tester’s approach-

Misha’s solution follows a similar method, but different conditions. The cases he identified were-

a. First check the direction.
b. For the respective direction, calculate the where the car’s rear will be when-
i) When Chef arrives at that lane.
**ii)**When Chef finishes crossing the lane, had he started immediately.
c. If, we observe that the car was at different side of y=0 at i) than it is at ii) (by checking location of car’s rear at i) and car’s front at ii)), it means it will hit Chef if Chef starts to cross immediately. Add time for car to cross to the answer.
d. Add time for Chef to cross the lane.

Refer to tester’s code for greater clarity.

Time Complexity- O(T*N) for both the approaches.

SOLUTION:

Setter
Tester
Editorialist

CHEF VIJJU’S CORNER:

1. This was a testing implementation problem. While the frustration a coder feels when he gets WA is understandable, it reaches to a whole new level when he knows that the logic is easy but its difficult to implement. But we cannot discard the fact that it is a necessary skill. Teaching importance of implementation, especially in a field which overlaps with concept of geometry, was one of our contest admin Misha’s big aim. And I see many of you fared well :). To all those who didnt, I will say, better fail and get frustrated here, than fail at somewhere else where it might be more important for you to get that AC. Learn from this experience, as solving this question taught me a few things as well :slight_smile:

**2.**I can recall a famous saying that-

''There is never too much Geometry!!''
- Somebody

So true a saying, lets complement it with a few Geometry, or related, problems :smiley:

2 Likes
2

Typo error in editorial. It should be 10e-6 instead of 10e6.

3

In short :
alt text

Detailed approach ::

Click to view

for __ in range(readInt()): n,s,w = readInts() v = readInts() d = readInts() p = readInts() c = readInts() t =[] carl,sumi = 0,0 for i in range(n): if d[i]==0 and p[i]>0: carl = p[i]*1.0+c[i]*1.0 if i>=1: carl -= v[i]*1.0*sum(t)*1.0 if carl<0: carl = 0 if (((carl*1.0-c[i])/v[i]*1.0)>(w*1.0/s*1.0)) and ((((carl*1.0-c[i])/v[i]*1.0)-(w*1.0/s*1.0))*1.0*v[i]>0.000001): t.append(w*1.0/s*1.0) else: t.append(carl*1.0/v[i]*1.0) t.append(w*1.0/s*1.0) elif d[i]==0 and p[i]<=0: carl = p[i]*1.0+c[i]*1.0 if carl<0: carl = 0 if i>=1: carl -= v[i]*1.0*sum(t)*1.0 if carl<0: carl = 0 if (((carl*1.0-c[i])/v[i]*1.0)>(w*1.0/s*1.0)) and ((((carl*1.0-c[i])/v[i]*1.0)-(w*1.0/s*1.0))*1.0*v[i]>0.000001): t.append(w*1.0/s*1.0) else: t.append(carl*1.0/v[i]*1.0) t.append(w*1.0/s*1.0) elif d[i]==1 and p[i]<0: carl = abs(p[i]*1.0)+c[i]*1.0 if i>=1: carl -= v[i]*1.0*sum(t)*1.0 if carl<0: carl = 0 if (((carl*1.0-c[i])/v[i]*1.0)>(w*1.0/s*1.0)) and ((((carl*1.0-c[i])/v[i]*1.0)-(w*1.0/s*1.0))*1.0*v[i]>0.000001): t.append(w*1.0/s*1.0) else: t.append(carl*1.0/v[i]*1.0) t.append(w*1.0/s*1.0) elif d[i]==1 and p[i]>=0: carl = p[i]*-1.0+c[i]*1.0 if carl<0: carl = 0 if i>=1: carl -= v[i]*1.0*sum(t)*1.0 if carl<0: carl = 0 if (((carl*1.0-c[i])/v[i]*1.0)>(w*1.0/s*1.0)) and ((((carl*1.0-c[i])/v[i]*1.0)-(w*1.0/s*1.0))*1.0*v[i]>0.000001): t.append(w*1.0/s*1.0) else: t.append(carl*1.0/v[i]*1.0) t.append(w*1.0/s*1.0) printdec(sum(t))

2 Likes
4

Does this get AC? Please mention that as well :stuck_out_tongue:

5

Thank you so much @aryanc403. I really dont know how did that happen :confused:

Now that I think of it…seeing {10}^{6} instead of {10}^{-6} must have been hilarious for you given how much this question revolves around this number xD

1 Like
6

@vijju123 yeah it did. Actually readInt() and readInts() function has not been written here :stuck_out_tongue:

It’s good to see for the first time that an organiser of a contest is too active on all threads :slight_smile:

1 Like
7

Its okay. Though its always useful to put the approach under the “hidden tab” and give a brief description outside it.

As in-

My description for approach

Click to view

Interested ones can see code.

People will love you a lot then~ :3

8

thanks will edit it :slight_smile:

9

logic is easy but its difficult to implement.
Really felt this when I was this solving problem.

Took around 22 submissions. And ~3.5 days to solve this. And feeling which you get after seeing AC cannot be explained using words.

Please add more problems of this type in contest.

This is only difference between CF and CC.
And this question very well removed the difference.

Good Job.
@vidyut_1 @mgch @vijju123 and Team.

Happy Coding :slight_smile:

1 Like
10

Yes. I feel you xD. Even editorialist’s solution took me 8hrs to make, because of some really minute error. we are glad you liked it :slight_smile:

PS: Look at editorialist’s solution, I tried my best to give a neat implementation :smiley:

1 Like
11

Could someone please tell the issue in my submission. Thanks in advance.

12

Try checking your expressions. Your code is a bit messy to read, but I feel its the conditions. Do you handle the cases as said in the editorial?

13

Yes. I do handle (the car has already crossed x = 0 and the car is crossing x = 0 and the car reaches x = 0 when chef crosses). Even a counter test case would be helpful. Thanks

14

Generating TC for this problem is a painn xD. Especially if your solution fails only on a single test case.

15

I dont know why people are writing such a big code for this problem, while it can be done in few lines


    for _ in range(int(input())):
    n,s,y = [int(x) for x in input().split()]
    v = [int(x) for x in input().split()]
    d = [int(x) for x in input().split()]
    p = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    cost = 0
    for i in range(n):
        if((d[i] == 0 and (p[i] + c[i] <= 0)) or (d[i] == 1 and(p[i] - c[i] >= 0))):cost += y/s
        elif(d[i] == 1 and (p[i] + (cost*v[i])) - c[i] > 0): cost += y/s
        elif (d[i] == 1 and (p[i]*-1 - (cost*v[i]))/v[i] - y/s > 0.000001): cost += y/s
        elif (d[i] == 1 and (p[i]*-1 - (cost*v[i]))/v[i] - y/s <= 0.000001): cost += (abs((p[i] + (cost*v[i]))-c[i])) / v[i] + y/s
        elif (d[i] == 0 and (p[i] - (cost*v[i])) + c[i] < 0): cost += y/s
        elif(d[i] == 0 and (p[i] - (cost*v[i])) / v[i] - y/s > 0.000001): cost += y/s
        elif (d[i] == 0 and (p[i] - (cost*v[i])) / v[i] - y/s <= 0.000001): cost += (((p[i] - (cost*v[i])) + c[i]) / v[i]) + y/s
        #else: cose += y/s
    print("%.6f" % cost)
16 
I dont know why people are writing such a big code for this problem, while it can be done in few lines

Its natural to feel like this. Take my stand here-

I dont know why people are writing so many if-else conditions when only 3 suffice and prove to be exhaustive. (Check editorialist solution for implementation).

Whatever strikes the guy/~girl to solve the problem.

1 Like
17

Thanks @aryanc403

1 Like
18

Can someone tell me what is the problem with this


[1]. I am getting wrong answer in one test case.:)


  [1]: https://www.codechef.com/viewsolution/18177938
19

@pavitra_ag you didn’t consider 10^-6 while writing your code.

“Chef does not get hit by a car if the minimum distance between him and any car remains greater than 10−6 at all times.”

you can see my solution.

20

Hi, I was unable to solve this problem in the contest. I liked the tester’s approach which is similar to my approach. I think the editorialist explanation for tester’s code is confusing. It should be "he checks the location of car’s rear when chef has reached the lane and he checks for the location of front of the car after chef moves instantly. The editorialist said that he checks for the location of rear both the time. If I understood it wrong please let me know.