question on codeforces problem

Question

I was unable to solve this problem from a past programming contest I did. Since this is more of a math question than programming, I thought it best to ask it here instead of over at stackoverflow.

In the explanation on the samples (see Note at the bottom of that link), I do not know how they are getting 510.5 for the time that the second trolleybus catches up with the first.

I do not have any physics background, but the physics formulas I know so far are:

dist = initialVelocity * tm + .5 * acceleration * (tm*tm)
time = sqrt(dist / (.5 * acceleration))
vel = initialVelocity + tm * acceleration

So for the first example, trolley 1's maximum speed is 10. Max acceleration for all trolleys is 10. But I don't know how to figure out when trolley 1 and trolley 2 meet.

The problem analyses for this problem is here. (see 167A at that link). But I do not understand how they are coming up with those formulas.

Thanks for any help.

Answer 1

You don't need to find where two bus meet, try to find each bus arrival time $a_i$ if each bus can ride in his own track, then the arrival time in the complete problem is $\max_{j<=i} a_j$.

For finding the arrival bus in the simpler problem, you need to consider two subcase: the bus keep accellerating for the whole time or not?

Answer 2

carlop has shown that you don't need to calculate when two buses meet, but you can if you want. Your equation for dist is not correct: initialVelocity is specified as 0, so you can delete that term, and once the bus hits maximum speed it stops accelerating. tm has to be counted from the departure time. $$dist=\begin {cases} \frac 12 a\cdot tm^2 & tm \lt maxV/a \\ \frac 12 a (maxV/a)^2 + maxV(tm-maxV/a) & else \end {cases}$$

Then you can solve for when the dist of one bus equal that of the previous one. If it is not in the range of the length of the run, they don't meet.

I used a for acceleration and maxV for maxVelocity to make the equation narrower