G. Opportunity Cost

Key Observations

• For a fixed phone $(x,y,z)$ and a fixed competitor $(x_i,y_i,z_i)$, \[ \max(x_i-x,0)+\max(y_i-y,0)+\max(z_i-z,0) \] is the sum of the positive coordinate differences.

• That is exactly \[ \max_{S \subseteq \{x,y,z\}} \left( \sum_{d \in S} d_i - \sum_{d \in S} d \right), \] because for each coordinate we either include its difference (if positive) or exclude it (if negative).

• Therefore the opportunity cost of phone $(x,y,z)$ is \[ \max_{\emptyset \ne S \subseteq \{x,y,z\}} \left( M_S - \sum_{d \in S} d \right), \] where \[ M_S = \max_i \sum_{d \in S} d_i. \]

• There are only $2^3-1=7$ nonempty subsets, so we can precompute all values $M_S$ in one pass and then evaluate every phone in constant time.

Algorithm

1. Number the three dimensions by bits $0,1,2$. For every nonempty mask mask from $1$ to $7$, let \[ M_{\texttt{mask}} = \max_i \sum_{\texttt{bit} \in \texttt{mask}} \text{value}_{i,\texttt{bit}}. \]

2. Read all phones and update these $7$ maxima.

3. For each phone $p$, compute \[ \max_{\texttt{mask}=1}^{7} \left( M_{\texttt{mask}} - \sum_{\texttt{bit} \in \texttt{mask}} p_{\texttt{bit}} \right). \] This is exactly its opportunity cost.

4. Keep the minimum pair \[ (\text{cost}, \text{index}) \] lexicographically, so ties are broken by the smallest index automatically.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

For any real numbers $a,b,c$, \[ \max(a,0)+\max(b,0)+\max(c,0) = \max_{S \subseteq \{1,2,3\}} \sum_{j \in S} v_j, \] where $(v_1,v_2,v_3)=(a,b,c)$.

Proof.

For each coordinate $v_j$, adding it helps exactly when $v_j > 0$ and hurts when $v_j < 0$. So the maximum subset sum is obtained by taking precisely the positive coordinates, and its value is $\max(a,0)+\max(b,0)+\max(c,0)$. □

Lemma 2.

For a fixed phone $p=(x,y,z)$, its opportunity cost equals \[ \max_{\emptyset \ne S \subseteq \{x,y,z\}} \left( M_S - \sum_{d \in S} d \right). \]

Proof.

For any competitor phone $i$, apply Lemma 1 to \[ a = x_i-x,\qquad b = y_i-y,\qquad c = z_i-z. \] Then \[ \max(x_i-x,0)+\max(y_i-y,0)+\max(z_i-z,0) = \max_S \left( \sum_{d \in S} d_i - \sum_{d \in S} d \right). \] Now maximize over all competitors $i$: \[ \max_i \max_S (\cdots) = \max_S \max_i (\cdots) = \max_S \left( M_S - \sum_{d \in S} d \right). \] The empty subset contributes $0$, so restricting to nonempty subsets does not change the maximum. □

Lemma 3.

For every phone $p$, the algorithm computes its exact opportunity cost.

Proof.

The preprocessing step computes every value $M_S$ exactly by definition. Then for phone $p$ the algorithm evaluates the expression from Lemma 2 over all seven nonempty subsets. Hence the maximum it obtains is exactly the opportunity cost of $p$. □

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

By Lemma 3, the algorithm computes the exact opportunity cost of every phone. It then chooses the minimum pair $(\text{cost}, \text{index})$, so it returns the smallest possible opportunity cost and, among all phones achieving it, the smallest index. Therefore the output is correct. □

Complexity Analysis

There are only $7$ nonempty subsets. So both the preprocessing pass and the evaluation pass take $O(7n)=O(n)$ time.

The stored phone list uses $O(n)$ memory.

Implementation Notes

• Using bitmasks $1 \dots 7$ is a convenient way to enumerate the seven nonempty subsets.

• All sums fit safely in 64-bit integers.

• The lexicographic minimum of (cost, index) handles the required tie-break automatically.