10767 - Barcelona's trams

[Dmytro Korzhyk]

Can anyone give the idea to solve this problem?
Is it true that function T(v) has only one local extremum?

[misof]

Can anyone give the idea to solve this problem?
Is it true that function T(v) has only one local extremum?

I used dynamic programming to find the best velocity for the x-th segment if I arrive with y crashes. When computing this, the corresponding function T(v) (input: speed on the x-th segment, output: expected time to finish the whole track, valid inputs: (0,M-y> ) has only one local minimum and this is also the global minimum you seek.

[Dmytro Korzhyk]

I used dynamic programming to find the best velocity for the x-th segment if I arrive with y crashes. When computing this, the corresponding function T(v) (input: speed on the x-th segment, output: expected time to finish the whole track, valid inputs: (0,M-y> ) has only one local minimum and this is also the global minimum you seek.

Thanks for your reply.
I used similar algorithm, but got TLE. What precision should have the value of v to get T with 4 decimal digits?

[Adrian Kuegel]

I had this idea in the contest to use dynamic programming. But then I discarded it, because I was not sure about:

(0,M-y> ) has only one local minimum and this is also the global minimum you seek.

Can this be shown by some induction? Or how did you see that this is also the global minimum?
To Dmytro:
I think he uses only one value (the value of the local minimum up to this segment, but probably starting with last segment; at least that was what I was thinking about when I tried to solve the problem).

[Dreamer#1]

Nice Problem.

I'm not good enough to understand the details of the discussions going on here so I can't contribute, sorry.

But I solved in my way, which is little inefficient though but ofcourse AC.

[abishek]

the function T(v, x, y) which will give the average time velocity for the xth segment with y crashes will depend on the average time for x+1 the segement and y or y+1 crashes. as none of these can be affected by this velocity, they can be assumed to be constant w.r.t this v when you differentiate. so i guess that would be the proof that this method works.
Also, if you work out the function it has only one local minima.

[Dmytro Korzhyk]

Thanks you all, I got AC, but only after setting precision of V to 1e-10 (1e-8 didn't work).