EVO vs STI#493

EVO vs STI (Editorial)

Author: Timur Degteari

Prepared by: Timur Degteari

The key insight is to reformulate the winning conditions in terms of difference arrays and then observe that optimal track selections correspond to prefixes of sorted arrays.

Define two auxiliary arrays:

  • c_i = e_i - s_i (positive when STI Guy is faster on track )

  • d_i = s_i - e_i (positive when EVO Guy is faster on track )

Let c' be the array sorted in non-decreasing order, and d' be the array sorted in non-decreasing order.

The optimal selection of tracks for EVO Guy to win consists of a prefix of c'. Similarly, the optimal selection for STI Guy to win consists of a prefix of d'.

For EVO Guy to win, we need: [_track i is chosen c_i < 0]

Suppose is the largest subset of tracks such that \sum_{c_i \in S} c_i < 0, and does not correspond to a prefix of c'. Since c' is sorted in non-decreasing order, replacing with the prefix of c' of the same size will yield a sum that is at most the original sum. Hence, the prefix is at least as good as (and often better than) any other subset of the same size.

By a symmetric argument, the same holds for STI Guy's victory using the array d'.

  1. Compute arrays and from the input.

  2. Sort both arrays in non-decreasing order.

  3. For each array, find the length of the longest prefix whose sum is strictly less than .

  4. These lengths give R_E (for EVO Guy using array c') and R_S (for STI Guy using array d').

Note: If no prefix has a negative sum, the answer is , meaning that racer cannot win regardless of track selection.

Time complexity: O(n \log n) due to sorting. The prefix sum computation is .