Most of the solution to problem 14.16 make sense. However, at the step to eliminate B3, I don’t see a reason why B3 can not be one of the top 3. The fact that B1 is before C1, does not imply B2 and B3 can not be before C1 as well.
After some thoughts, I can clarify it myself. Assume A1 and B1 are #1 and #2, then B2 may be #3, but in this case, B3 can be eliminated.
Hi Louis,
Could you please share something more about the explanation?
Compare to other problems, 14.16 - Schedule Time Trials is different, we need to do more math work and induction instead of coding.
For me, I think transitivity is the key, what do you think?
Let me explain the logic behind the book’s solution.
First split 25 objects into 5 groups. What we get is 5 groups of 5 objects. Sort each group (this requires total of 5 sorts). Since we are interested in the top 3, clearly only the top 3 objects in each of the 5 groups have a chance to be in the top 3. So we can eliminate #4 and #5 in each of the 5 groups.
Now we are left with the top 3 in each group. Say we pick the #1 from each group and sort them (1 sort), this results the final #1 among all 25 objects.
In the book’s example, assume the sort for #1 resulted in this order (A1, B1, C1, D1, E1). So A1 can be excluded for the next sort to find #2 and #3. It’s important to note that the example ordering does not limit the following logic (as you can apply the same logic to any outcomes of this sort step). What we can deduct from this example is D1 and E1 can be eliminated from the top 3 since A1, B1, and C1 can take the top 3. So all objects in the D and E groups can be eliminated, because they have lower rank than D1 and E1.
Now we look at groups A, B, and C. Since at least A1 and B1 can take the top 2 spots, there is only 1 spot left for #3. So only C1 from group C should be considered for the #3 spot. Therefore C2 and C3 can be eliminated. For the B group, we can follow similar logic we used for C group. That is there are only 2 spots left (#2 & #3) open for the top 3, after we determined A1 is #1. It only make sense for B group to have 2 candidates to compete for these two spots, namely B1 and B2. So B3 can be eliminated from the ranking. Now we are left with A2, A3, B1, B2, C1 for the final sort (1 sort) step to determine #2 and #3.
This results in total 7 sorts. I have an alternative solution (with simpler logic) that requires 8 sorts.
Hey Louis,
First of all, thanks for your question, and it is a very meaningful discussion as it is non-trivial problem.
Like @carlshen said, transitivity is the key of solving this problem, and you actually caught the key of explaining this is A1 and B1 are #1 and #2, and assume A2 and A3 are slow behind B3. The best case for B3 is #4 since B2 is #3. This theory also holds for the situation that why C2 cannot be #3.
Please let me know if there is any problem.