TWOTRAINS - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Abhinav Sharma
Testers: Nishank Suresh, Nishant Shah
Editorialist: Nishank Suresh






There are two trains A and B, and N stations. A train takes time P_i to go from station i to station (i+1).

Train B can depart from station i only after train A has reached station (i+1). What is the minimum amount of time needed for train B to reach station N?


Let S = P_1 + P_2 + \ldots + P_{N-1}, i.e, the sum of all the elements of P.
Let M = \max(P_1, P_2, \ldots, P_{N-1}), i.e, the maximum element of P.
Then the answer is just S + M.


The journey of train B can be broken into two separate parts: time taken by it when travelling from one station to another, and time taken while waiting for train A to reach the next station.

The time taken while travelling is clearly just P_1 + P_2 + \ldots + P_{N-1}, by definition.

Now, let M = \max(P_1, P_2, \ldots, P_{N-1}).

The minimum waiting time is definitely at least M, since while train A crosses the section that needs M time, train B cannot move along that section at all, and hence must wait for a total of \geq M units of time already.

Conversely, suppose train B just waits for M seconds at the very beginning before even starting, and starts moving at the end of the M-th second. It is easy to see that, since M = \max(P_1, P_2, \ldots, P_{N-1}), whenever train B is at station i, train A has already reached station (i+1) (and may have gone even further). So, no more waiting time is needed.

Thus, the minimum waiting time is exactly M, and hence the answer is S + M as claimed.


\mathcal{O}(N) per test case


Editorialist's Code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(sum(a) + max(a))