= Solution
The first value is the tournament winner $M$. Find the second value $s$ by taking the <maximum> of the direct-loser set $\operatorname{second}(S)$, retaining its associated tournament record.
The third-largest value must have lost directly to either $M$ or $s$: any other value is smaller and could not defeat it. Therefore it belongs to
$$
C=\bigl(\operatorname{second}(S)\setminus\{s\}\bigr)
\ \cup\ \{r.\mathrm{key}:r\in s.\mathrm{losers}\}.
$$
Conversely, every value in $C$ is distinct from $M,s$. Thus \b[the third-largest value is $\max C$]. This is <tournament selection of the three largest elements>; it uses the retained defeat records while computing the requested three-part partition.
Three largest elements exist only for $n\geq3$. With the paper's power-of-two assumption this means $n\geq4$. The partition in part (b) remains meaningful for $n=2$, but a third output cannot be supplied in that case.
Back to article page
