# question on codeforces problem

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.

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?

• I don't understand how they got the number 510.5 though, which was part of my question. I also don't understand how they derived the formulas in the analysis, which was also part of the question. Those are the details I need to know. Your explanation is basically the same as the one in the analysis, which I don't follow.
– dcp
Apr 19, 2012 at 14:30
• Sorry, I should have read the problem explanation first. The fact is that you don't need to know the time when they meet for solve the problem, I think this it's the basic idea behind this type of problem "find a simpler problem that you know how to solve". Apr 19, 2012 at 14:46
• Ok, I'll try it your way. But if first trolley leaves at 0 and goes a distance of 10,000, then why isn't the time 10,000 / 10 = 1000? In the Notes, the time is 1000.5. I don't understand how they got that.
– dcp
Apr 19, 2012 at 18:19
• The first thing to note is that you must always go at maximum velocity OR maximum accelleration. You go at max accelleration until max_a * t = max_v (look at your third formula), and after that time you go at costant speed. So the first bus for the first second(10*x=10 -> x=1) he increase speed, and in this time he travel 0.5*10*1*1=5 meters (using your first formula). The second part he travel at costant speed 10, but he have already done 5 meters, so (10000-5)/10=999.5 seconds. Plus 1s for the accelleration part = 1000.5. Apr 19, 2012 at 22:13

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

• Why is the equation for dist not correct? initialVelocity is always 0, true, but that just causes the initialVelocity * tm to always be 0, so it doesn't affect equation. So while it's not needed, I don't necessarily agree it's not correct. Or did I misunderstand something?
– dcp
Apr 19, 2012 at 14:59
• Also, I don't understand how you got the second formula you used (e.g. the "else" clause). Can you explain it more?
– dcp
Apr 19, 2012 at 15:28
• @dcp: the else clause covers the time after the bus gets to maximum velocity. The first term is how far it goes while accelerating, the second is the distance at constant velocity (at maxV) Apr 19, 2012 at 15:32
• Ok, so distance at constant velocity is vel * x, where x is time, right? I still don't understand the tm - maxV / a part.
– dcp
Apr 19, 2012 at 15:39
• @dcp: maxV/a is the time to accelerate to maxV. That is the (maxV/a)^2 part of the first term, so the time at maxV is after that. Apr 19, 2012 at 15:49