Help needed on this atcoder problem.

Revision en4, by Misa-Misa, 2023-10-10 01:14:34

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 Misa-Misa 2023-10-10 01:14:34 0 (published)
en3 Misa-Misa 2023-10-10 01:14:11 5 Tiny change: 'ition and in opposi' -> 'ition and move in opposi'
en2 Misa-Misa 2023-10-10 01:13:32 1024 (saved to drafts)
en1 Misa-Misa 2023-10-09 13:56:37 120 Initial revision (published)