Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Misa-Misa's blog

By Misa-Misa, history, 7 months ago,

B — Pass on Path arc_152

UPD : Solved
- Observe that it will be most optimal when both the travellers start at same position and move in opposite direction.
Proof:
In general case, the travellers will pass each other twice.
At the time of first meet it will be like this -> One of the travellers is waiting at rest area for other to pass, as other passes it they will meet again for second meet afterwards. So it is better if they started at the same meet point in different directions, answer would always be less. Hence proved. (Because the first meet point has become the start so does not add anything to the wait time, so it is better.)

- Now we just have to solve if they had to start at rest point A[i]. To solve this note that their meeting point will be L-A[i]. - It will lie between two rest positions (may coincide also) such that A[j] <= L-A[i] <= A[k], min waiting time will be ..
- 2 * ( min ( (L-A[i]-A[j]) , A[k]-(L-A[i])) ).
- To get final answer, Add the min waiting time to 2*L.

• +3

 » 7 months ago, # |   0 Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).