Help needed on this atcoder problem.
Difference between en3 and en4, changed 0 character(s)
[B — Pass on Path  arc_152](https://atcoder.jp/contests/arc152/tasks/arc152_b)↵

UPD : Solved<br>↵
- Observe that it will be most optimal when both the travellers start at same position and move in opposite direction.<br>↵
Proof:<br>↵
In general case, the travellers will pass each other twice.<br>↵
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.)<br>↵
<br>↵
- 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 ..<br>↵
- `2 * ( min ( (L-A[i]-A[j]) , A[k]-(L-A[i])) )`.<br>↵
- To get final answer, Add the min waiting time to 2*L.  ↵

History

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