Problem
There are 25 horses and only five tracks in a race (i.e., you can race 5 horses at a time). There is no stop clock !! Assume that there are no ties.
1: What is the minimum number of races needed to determine the 3 fastest horses in order from fastest to slowest ?
Follow Up minimum number of races needed to find
1:....... to rank all of them from fastest to slowest ?
2:....... to find the top k fastest horses ?
Solution :
Divided into 5 groups, each 5 horses and have 5 races.
first 5 preliminary races
We run five races with five horses. The five winners race in a sixth race while the 4th and fith place finishers are eliminated from further consideration, as we have to anyways take first 3.
Now we are left with 15 horses.
6th race
Take all the fastest horses from each group and race them. The sixth race show horse is faster than all the horses that participated in the preliminary races where the 4th and 5th place horses participated and they are eliminated from further consideration. So, now we have 12 horses left, because we know who is the fastest horse, and 4th and 5th horses are removed, so 15 - 1 -2 = 12.
The other horses in the preliminary race where the 6th race show horse participated are also eliminated.
The slow horses in the preliminary race in competition of 4th and 5th horse in the 6th race are also eliminated since there are at least three remaining horses that are faster.
So, horses who lost to 4th and 5th horse of race 6 are removed, so 12 - 4 = 8
Throw the last one horse of the second fast group. 7 horse left
We run five races with five horses. The five winners race in a sixth race while the 4th and fith place finishers are eliminated from further consideration, as we have to anyways take first 3.
Now we are left with 15 horses.
6th race
Take all the fastest horses from each group and race them. The sixth race show horse is faster than all the horses that participated in the preliminary races where the 4th and 5th place horses participated and they are eliminated from further consideration. So, now we have 12 horses left, because we know who is the fastest horse, and 4th and 5th horses are removed, so 15 - 1 -2 = 12.
The other horses in the preliminary race where the 6th race show horse participated are also eliminated.
The slow horses in the preliminary race in competition of 4th and 5th horse in the 6th race are also eliminated since there are at least three remaining horses that are faster.
So, horses who lost to 4th and 5th horse of race 6 are removed, so 12 - 4 = 8
Throw the last one horse of the second fast group. 7 horse left
Throw the last two horse of the third fast group. 5 horse left
Now, lets have the last race
7th race
Take first 2, from this race, and we have our 3 fastest.
Follow Up questions
minimum number of races needed to find
1:....... to rank all of them from fastest to slowest ?
2:....... to find the top k fastest horses ?
* min number of races to rank all of them
1. I can re-phrase this question to ask the min number of races to get 25 fastest horses.
2. You need 6 races to get the fastest ranked (steps 1 thru 3).
3. After that every race will give you the next fastest.
4. We can continue this till we have got the 20 fastest horses. After that we just need 1 race to rank the remaining 5.
total = 6 (to get rank 1) + 19 (to get rank 2-20) + 1 (to get rank 21-25) = 26
* min number of races to get k fastest horse
sol:-
5 + k (for k <= 20 )
26 (otherwise)
Now, lets have the last race
7th race
Take first 2, from this race, and we have our 3 fastest.
Follow Up questions
minimum number of races needed to find
1:....... to rank all of them from fastest to slowest ?
2:....... to find the top k fastest horses ?
* min number of races to rank all of them
1. I can re-phrase this question to ask the min number of races to get 25 fastest horses.
2. You need 6 races to get the fastest ranked (steps 1 thru 3).
3. After that every race will give you the next fastest.
4. We can continue this till we have got the 20 fastest horses. After that we just need 1 race to rank the remaining 5.
total = 6 (to get rank 1) + 19 (to get rank 2-20) + 1 (to get rank 21-25) = 26
* min number of races to get k fastest horse
sol:-
5 + k (for k <= 20 )
26 (otherwise)
0 comments:
Post a Comment