tag:blogger.com,1999:blog-2906036198963334156.post1340054478355357269..comments2018-09-08T07:06:30.355-07:00Comments on With My Eyes: 25 Horses, 5 lanes, no clock, top 5 (not 3)Dukehttp://www.blogger.com/profile/06677123157024090273noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-2906036198963334156.post-81094000537393378782017-07-18T19:50:10.693-07:002017-07-18T19:50:10.693-07:00Solution: answer is 9 races
Step 1: First, we gro...Solution: answer is 9 races<br /><br />Step 1: First, we group the horses into groups of 5 and race each group in the race course. This gives us 5 races.<br /><br /><br /><br />W11 W12 W13 W14 W15<br /><br />W21 W22 W23 W24 W25<br /><br />W31 W32 W33 W34 W35<br /><br />W41 W42 W43 W44 W45<br /><br />W51 W52 W53 W54 W55<br /><br /><br />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)<br /><br />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 <br />now we have<br /><br />W11 W12 W13 W14 W15<br /><br />W21 W22 W23 W24 W25<br /><br />W31 W32 W33 W34 W35<br /><br />W41 W42 W43 W44 W45<br /><br />W51<br /><br />Step 4: because we need top 5 then dont need W25 W34 W35 W43 W44 W45<br /><br />now we have<br /><br />W11 W12 W13 W14 W15<br /><br />W21 W22 W23 W24 <br /><br />W31 W32 W33 <br /><br />W41 W42 <br /><br />W51<br /><br /><br />Step 5: top 1 is already achieved which is W11(winner of 6th race)<br />remaining are <br /> X W12 W13 W14 W15<br /><br />W21 W22 W23 W24 <br /><br />W31 W32 W33 <br /><br />W41 W42 <br /><br />W51<br /><br />Step 6: candidates for 5th position: W51 W42 W33 W24 W15. 1 RACE TO GET 5TH POSITION (this is 7th race)<br /><br />remaining are<br /><br /> X W12 W13 W14 <br /><br />W21 W22 W23 <br /><br />W31 W32 <br /><br />W41<br /><br /><br />Step 7: candidates for 4th position: W41 W32 W23 W14. 1 race to get 4th position ((this is 8th race)<br /><br />X W12 W13 <br /><br />W21 W22 <br /><br />W31<br /><br /><br />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)<br /><br /><br />Hence answer is 9 races.<br /><br />25 horses 5 tracks 3 fastest horses puzzle | Google Interview Question<br />http://codinginterviewquestionsans.blogspot.in/2017/07/25-horses-5-tracks-3-fastest-horses.htmlindianhttps://www.blogger.com/profile/13022734071024600704noreply@blogger.comtag:blogger.com,1999:blog-2906036198963334156.post-33237520208351894202013-07-25T05:29:40.653-07:002013-07-25T05:29:40.653-07:00In option 5 as above, you mentioned that 1,2,2.2 a...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.. <br /><br />Cheers <br /><br />KRGhttps://www.blogger.com/profile/07205642208009061950noreply@blogger.comtag:blogger.com,1999:blog-2906036198963334156.post-92223355976620894972013-06-05T14:23:14.541-07:002013-06-05T14:23:14.541-07:00I meant "8th race" in the first part.I meant "8th race" in the first part.Dukehttps://www.blogger.com/profile/06689353337965574738noreply@blogger.comtag:blogger.com,1999:blog-2906036198963334156.post-77620841129526119412013-06-05T11:37:22.292-07:002013-06-05T11:37:22.292-07:00I'm not sure how my solution neglects 1.4 bein...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).<br /><br />I don't "make it look like that", I only chose to explain those ones since they're complicated.<br /><br />Let's look at your 3,4,5,6<br /><br />3) 1.3 > 3 > 4 > 2.2 - <br /><br />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).<br /><br />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.<br /><br />Hell, with that case you can race 1.2, 1.3, 1.4, 2, 3 and actually get the full ordering.<br /><br />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.<br /><br />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).<br /><br />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.<br /><br />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).<br /><br />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.<br /><br />Feel free to plot out the rest of the solutions to convince yourself.<br /><br />Note: Using quotes around a word like complicated makes you sound smug.<br /><br />Dukehttps://www.blogger.com/profile/06689353337965574738noreply@blogger.comtag:blogger.com,1999:blog-2906036198963334156.post-1499875800147135982013-06-04T19:04:15.142-07:002013-06-04T19:04:15.142-07:00I believe your solution is flawed. Let's explo...I believe your solution is flawed. Let's explore your "complicated" case.<br /><br />"1.3 and 2.2 are the top 2, in that order."<br /><br />So we know that 1.3 is faster than 2.2. let's take an example of that<br />('>' signifies faster):<br /><br />1.3 > 2.2 > 3 > 3.2 > 4<br /><br />What does this say about 1.4 in relation to 2.2 ? Nothing. So it _could_ be the case that:<br /><br />1.3 > 1.4 > 2.2 > 3 > 3.2 > 4<br /><br />In which case 1.4 is a valid candidate to be in top 5. Your solution neglects<br />that. In fact, in the "complicated case" of your solution 1.4 can never be in<br />top 5, which is wrong.<br /><br />Also, you make it look like there are just 2 cases for race 7:<br />1) 3 and 4 are top 2<br />2) 1.3 and 2.2 are in top 2<br /><br />Well, I can think of more cases:<br />3) 1.3 > 3 > 4 > 2.2<br />4) 1.3 > 3 > 2.2 > 4<br />5) 2.2 > 3 > 4 > 1.3<br />6) 2.2 > 3 > 1.3 > 4<br />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<br />Art Mhttps://www.blogger.com/profile/05870318874217133439noreply@blogger.comtag:blogger.com,1999:blog-2906036198963334156.post-38379939630340402992013-03-02T07:20:23.776-08:002013-03-02T07:20:23.776-08:00I haven't seen this in a while, and just notic...I haven't seen this in a while, and just noticed your question PCBarn.<br /><br />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.<br /><br />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).<br /><br />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).Dukehttps://www.blogger.com/profile/06689353337965574738noreply@blogger.comtag:blogger.com,1999:blog-2906036198963334156.post-79801124261237498402012-09-05T09:41:16.383-07:002012-09-05T09:41:16.383-07:00thanku:)thanku:)Deepthahttps://www.blogger.com/profile/07950200745565739368noreply@blogger.comtag:blogger.com,1999:blog-2906036198963334156.post-21782771916696512302012-08-08T05:25:55.463-07:002012-08-08T05:25:55.463-07:00can u pls explain how 2.3 can be discarded when ra...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!! :)Anonymousnoreply@blogger.com