Consider the following problem:
Give an algorithm to find the $1^{st}, 2^{nd}, 3^{th}$ fastest horses from 25 horses. In each round, at most 5 horses can race and you can get the exact position of these horses. Analyze the lower bound of this problem using adversary argument. One race is considered as one critical operation.
I can figure out a solution using 7 races:
- Divide 25 horses into 5 groups with 5 horses for each: $A: a_1, a_2, a_3, a_4, a_5$; $B: b_1, b_2, b_3, b_4, b_5$; $C: c_1, c_2, c_3, c_4, c_5$; $D: d_1, d_2, d_3, d_4, d_5$; and $E: e_1, e_2, e_3, e_4, e_5$.
- One race within each group. Suppose that the position of each horse in each group is consistent with its index: e.g., $A: a_1 > a_2 > a_3 > a_4 > a_5$.
- One race for $a_1, b_1, c_1, d_1, e_1$ and get $a_1 > b_1 > c_1 > d_1 > e_1$. Thus, $a_1$ is the fastest horse.
- The second and third ones are among $a_2, a_3, b_1, b_2, c_1$. So one more race is enough.
However I have difficulty in analyzing its lower bound using adversary argument. So my problem is:
How to analyze its lower bound using adversary argument? What is the adversary strategy?
finding max and min
,finding the second-largest key
andfinding the median
. To this horse-racing problem, I failed to state the adversary strategy formally. I will try again based on your answer. $\endgroup$