The idea is that you have 25 horses, a 5 lane track, no timer, and want to find the fastest 5 horses. How many races can you do it in?
NOTE THAT THE ORIGINAL PROBLEM WANTED ALL 5 IN ORDER, AND THIS WAY JUST GIVES THE FASTEST 5 POSSIBLY OUT OF ORDER AND NEEDS A 9TH RACE TO ORDER THEM PROPERLY.
I stayed up all night once to come up with an 8, and thought i did, but in the morning realized that I had made a mistake. BruteForce found a description of a solution for 8. It was on the same track as me, but he didn't make the mistake I did. I take no credit.
Anyhow, here's the write-up so it's a little more visual and easier to parse than the text answer he found.
You start by running 6 races. 5 races let every horse run, and the 6th is the winner's race. You're left with:
Note that "1" is clearly the fastest horse, since he was never beaten, and we have some information about every horse relative to at least one other horse. We can also remove some as hopeless, since they're too far back along the known relative speed graph to possibly be in the top 5.
Let's remove those.
Now what? Well, if we want the top 3 in order we'd race 1.2, 1.3, 2, 2.2, and 3. That's 5 horses and the answer to the "top 3 in 7" problem. That's not what we want, though.
We're going to instead race 1.3, 2.2, 3, 3.2, and 4. Why? We know that at least one of 1.2 and 2 are in the top 5, and can figure that out based on the result of our race 7. Here's our race 7.
Let's take the easiest result case first. 3 and 4 are the top 2. 3 had to have beaten 4, since we knew it was already faster. 2 is therefore in the top 4 in second position, and the final horse is one of 1.2, 2.2, 3.2, 4.2, 5. That's 5 horses and we can just race them. Brown indicates horses to be in race 8.
Now let's look at a complicated result. 1.3 and 2.2 are the top 2, in that order. What do we know?
The key piece of information is that since 2.2 beat 3, 3 cannot be in the top 5. Why? For 3 to be in, 2 would have to be in, as well as 2.2. Both beat 3. But that also means, since 1.3 beat 2.2 that 1.2 is in there too. We ran out of places. The same logic rules out 2.3. Depending on the result of race 7, you might have to flip the graph but can then apply the same reasoning as it ends up being symmetrical.
So in this case, which is an example of the most complicated situations from race 7, ends up looking like this:
1.3 and 2.2 run again, and 1.2 doesn't need to run because it has to be in the finals anyhow. The top 3 from this race are in the top 5 with 1 and 1.2.
This was a much better problem than the "top 3" version.
8 comments:
can u pls explain how 2.3 can be discarded when race 7 results in 1.3 and 2.2 being in top 2? thnku!! :)
thanku:)
I haven't seen this in a while, and just noticed your question PCBarn.
So I think you mean that 2.2 beats 1.3 in Race 7 in the top 2 spots. What does this rule out? Since 1.3 beat 3 we are left with the candidates left being 1,1.2,1.3,2, 2.2, 2.3,2.4.
Race 8 is then 1.2, 2.2, 1.3, 2.3, 2.4. 1 and 2 are clearly in the top 5 (though we don't know 2's rank).
The top 3 from this race 8 would then race against #2 in a race 9 with only 4 horses to get a final ordering (1 is the fastest horse - period).
I believe your solution is flawed. Let's explore your "complicated" case.
"1.3 and 2.2 are the top 2, in that order."
So we know that 1.3 is faster than 2.2. let's take an example of that
('>' signifies faster):
1.3 > 2.2 > 3 > 3.2 > 4
What does this say about 1.4 in relation to 2.2 ? Nothing. So it _could_ be the case that:
1.3 > 1.4 > 2.2 > 3 > 3.2 > 4
In which case 1.4 is a valid candidate to be in top 5. Your solution neglects
that. In fact, in the "complicated case" of your solution 1.4 can never be in
top 5, which is wrong.
Also, you make it look like there are just 2 cases for race 7:
1) 3 and 4 are top 2
2) 1.3 and 2.2 are in top 2
Well, I can think of more cases:
3) 1.3 > 3 > 4 > 2.2
4) 1.3 > 3 > 2.2 > 4
5) 2.2 > 3 > 4 > 1.3
6) 2.2 > 3 > 1.3 > 4
7..N) cases that incorporate 3.2 being faster than either 1.3 or 2.2 or both and more cases where 3.2 is faster than 4
I'm not sure how my solution neglects 1.4 being in the top 5. The 5th race is the brown ones (1.3, 1.4, 1.5, 2, 2.2).
I don't "make it look like that", I only chose to explain those ones since they're complicated.
Let's look at your 3,4,5,6
3) 1.3 > 3 > 4 > 2.2 -
Well, 1 is fastest. I won't talk about that one again, since it's obvious. We also know that the following horses are faster than 3: 1.2, 1.3, 2. 3 is at best 5th place, and 2.2 and 4 are completely out of it (as well as horses that they beat).
So who has to race in that one? well, 2 is a lock to be faster than 3, and since we don't care about order we can just include that and 1.2 and 1.3 in the top 5. There's one spot left. So who could it be? Can't be 2.2 since that's slower than 3, can't be 4.x or 5, since that's slower than 3. Could be 3. Could be 1.4. Let those 2 race for the final spot.
Hell, with that case you can race 1.2, 1.3, 1.4, 2, 3 and actually get the full ordering.
4) This is exactly the same case. the positioning of 2.2 and 4 are irrelevant because 1.3 beating 3 means that anything that 3 beat is out of it, because 2 already beat 3, and that means that all of 1, 1.2, 1.3, and 2 are faster than it. We don't know their relative speeds when we combine the columns, but we know they're top 5.
5) 5 and 6 are more complicated, so I have to assume that the unmentioned horse is in last place in your ranking (I admit that if we don't know where all 5 horses finish in a given race it doesn't work).
So 5... 1, 2, 2.2 are top 3. Who could be in the last 2 spots? 1.2, 2.3, 2.4, 3, 4. Can 3.2 be there? Nope, since he came in behind 4 other horses already that didn't include the fastest horse. So we race those 5 and the top 2 round out the top 5.
For 6: 1, 2, 2.2 are still in the top 4 for sure, so we have 3 of the top 5. Needing 2 more spots, it could be 1.2 and 1.3, 2.3 and 2.4, and 3. 3.2 is eliminated because it was last place in race 7 and can't therefore be in the top 5 (4 beat it and all lost to 1 so that's that).
7..N - The fact that you mention 3.2 being faster than 4 as a troublesome result indicates that you're not understanding the problem or solution at all. 3.2 > 4 > the rest in race 7 says that 1, 2, 3, 3.1, and 3.2 are the top 5 horses, and actually in that order, with no race 8 needed. 3.2 >1.3 > rest means that 1, 2, 3, 3.2 are in the top 5, and there's one spot left for either 1.2, 3.3, or 4. That's only a 3 horse race.
Feel free to plot out the rest of the solutions to convince yourself.
Note: Using quotes around a word like complicated makes you sound smug.
I meant "8th race" in the first part.
In option 5 as above, you mentioned that 1,2,2.2 are top 3 and to get rest two, you race 1.2,2.3,2.4,3,4. However, 1.2 has not been tested against 2 and 2.2 and hence to get order you need the 9th race.. So you essentially need 8 races to determine the fastest 5 without order and 9 races to fix the order also once you consider the options 3 & 5 as above..
Cheers
Solution: answer is 9 races
Step 1: First, we group the horses into groups of 5 and race each group in the race course. This gives us 5 races.
W11 W12 W13 W14 W15
W21 W22 W23 W24 W25
W31 W32 W33 W34 W35
W41 W42 W43 W44 W45
W51 W52 W53 W54 W55
Step 2:we race the 5 level 1 winners(w11,w21,w31,w41,w51) and assume winning order of this race is w11,w21,w31,w41,w51 (THIS IS 6TH RACE)
Step 3: BECAUSE WE NEED TOP 5 AND W51 HAS COME 5TH Position that is the reason we don't need to consider W52 W53 W54 W55
now we have
W11 W12 W13 W14 W15
W21 W22 W23 W24 W25
W31 W32 W33 W34 W35
W41 W42 W43 W44 W45
W51
Step 4: because we need top 5 then dont need W25 W34 W35 W43 W44 W45
now we have
W11 W12 W13 W14 W15
W21 W22 W23 W24
W31 W32 W33
W41 W42
W51
Step 5: top 1 is already achieved which is W11(winner of 6th race)
remaining are
X W12 W13 W14 W15
W21 W22 W23 W24
W31 W32 W33
W41 W42
W51
Step 6: candidates for 5th position: W51 W42 W33 W24 W15. 1 RACE TO GET 5TH POSITION (this is 7th race)
remaining are
X W12 W13 W14
W21 W22 W23
W31 W32
W41
Step 7: candidates for 4th position: W41 W32 W23 W14. 1 race to get 4th position ((this is 8th race)
X W12 W13
W21 W22
W31
Step 8: Candidates for 2nd and 3rd position: W12 W13 W21 W22 W31. 1 race to get 2nd and 3rd position ((this is 9th race)
Hence answer is 9 races.
25 horses 5 tracks 3 fastest horses puzzle | Google Interview Question
http://codinginterviewquestionsans.blogspot.in/2017/07/25-horses-5-tracks-3-fastest-horses.html
Post a Comment