A - Ekiden Race Editorial by evima
[1] Consider the necessary conditions
Let’s consider the conditions for person \(i\) to have the fastest return time.
If there is a person \(j\) who started later than person \(i\) and finished earlier than person \(i\) (i.e., \(i < j\) and \(P_i > P_j\)), person \(j\) ran the return leg faster than person \(i\), so person \(i\) cannot have the fastest return time.
Therefore, the nonexistence of a \(j\) such that \(i < j\) and \(P_i > P_j\) is necessary for person \(i\) to have the fastest return time. If this condition is met, is it possible for person \(i\) to have the fastest return time?
[2] Construct a race result favorable to person \(i\)
For example, the following race is consistent with the given information:
- person \(x\) started the return leg at time \(x\) and finished at time \(N + P_x\).
From here, let’s make the race result as favorable as possible for person \(i\) without changing the order of start and finish.
First, by adding \(10^{100}\) to the finish time of those who finished later than person \(i\), we have:
- Person \(x\) started the return leg at time \(x\) and finished at time \(N + P_x + [P_i < P_x] \times 10^{100}\).
This makes the return time of those who finished later than person \(i\) greater than person \(i\) without changing the rankings.
Similarly, by subtracting \(10^{100}\) from the start time of those who started earlier than person \(i\), we have:
- Person \(x\) started the return leg at time \(x - [x < i] \times 10^{100}\) and finished at time \(N + P_x + [P_i < P_x] \times 10^{100}\).
This makes the return time of those who started earlier than person \(i\) greater than person \(i\) without changing the rankings.
[3] Summary
From [2], we can see that if person \(i\) meets the necessary condition in [1], we can construct a race result where person \(i\) has the fastest return time. Therefore, for each \(i\), we just need to determine whether there is a \(j\) such that \(i < j\) and \(P_i > P_j\), and we can solve it in \(O(N^2)\) time.
Also, by taking the cumulative min from the back of \(P\), we can solve it in \(O(N)\) time.
(Above is a modification of a translation by GPT-4.)
posted:
last update: