Timeline for There are $n$ horses. At a time only $k$ horses can run in a single race. What is the minimum number of races required to find the $m$ fastest horses?
Current License: CC BY-SA 3.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Apr 30, 2018 at 20:18 | history | suggested | Rodrigo de Azevedo | CC BY-SA 3.0 |
Minor improvements
|
| Apr 30, 2018 at 12:56 | review | Suggested edits | |||
| S Apr 30, 2018 at 20:18 | |||||
| Sep 3, 2017 at 14:51 | history | protected | Lucia | ||
| Jul 3, 2017 at 15:16 | review | Close votes | |||
| Jul 3, 2017 at 18:40 | |||||
| S Jul 3, 2017 at 11:59 | history | suggested | CommunityBot | CC BY-SA 3.0 |
I used some $
|
| Jul 3, 2017 at 11:57 | review | Suggested edits | |||
| S Jul 3, 2017 at 11:59 | |||||
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| S Apr 18, 2014 at 6:42 | history | bounty ended | CommunityBot | ||
| S Apr 18, 2014 at 6:42 | history | notice removed | CommunityBot | ||
| Apr 11, 2014 at 22:18 | answer | added | Will Sawin | timeline score: 15 | |
| Apr 10, 2014 at 9:57 | comment | added | domotorp | This has been asked before, now I cannot find the other question but see researchgate.net/publication/… | |
| Apr 10, 2014 at 5:37 | comment | added | Włodzimierz Holsztyński | Phrase "Please explain your answer" sounds... I don't know. Is it necessary? | |
| S Apr 10, 2014 at 5:13 | history | bounty started | Quixotic | ||
| S Apr 10, 2014 at 5:13 | history | notice added | Quixotic | Authoritative reference needed | |
| Dec 25, 2013 at 1:36 | comment | added | Brendan McKay | It isn't clearly stated whether we have to plan all the races in advance or we can plan each race after knowing the results of the previous races. The answer could change. | |
| Dec 25, 2013 at 1:29 | comment | added | Eric Naslund | I believe the Google interview question was $m=3$ rather than $m=5$. | |
| Dec 25, 2013 at 0:25 | review | Close votes | |||
| Dec 25, 2013 at 10:33 | |||||
| Dec 24, 2013 at 23:02 | comment | added | Dylan Pizzo | I just wanted to say that this is the same as Generalization of a horse-racing puzzle. | |
| Dec 3, 2012 at 17:12 | history | edited | Debanjan Chanda | CC BY-SA 3.0 |
added 8 characters in body
|
| Dec 3, 2012 at 0:42 | comment | added | Gerhard Paseman | It is clear that O(nlogn) is an upper bound on what is necessary, simply by using a race as a comparison (and forgetting about 3 of the horses) and doing something like mergesort to get a complete ranking. For a complete ranking with races, information theory should yield the same order as a lower bound. For ranking a small fraction m of the n horses, it may be possible to do it in O(nlogm), but I would expect the constants for small m to outweigh logm, so practical methods would look like O(nm) in those cases. Gerhard "Ask Me About System Design" Paseman, 2012.12.02 | |
| Dec 3, 2012 at 0:19 | comment | added | Ralph Furman | Indeed, for k=2 you are looking at $m$ order statistics, which is linear in $n$. | |
| Dec 2, 2012 at 23:37 | comment | added | Zack Wolske | @David: This is even weaker than partial sorting, since we don't need to know the exact rank of elements $1$ to $m$, just the set of elements in those positions. | |
| Dec 2, 2012 at 21:56 | history | edited | Debanjan Chanda | CC BY-SA 3.0 |
added 14 characters in body
|
| Dec 1, 2012 at 2:38 | history | reopened |
David E Speyer algori Todd Trimble Gjergji Zaimi Brendan McKay |
||
| Dec 1, 2012 at 0:32 | comment | added | David E Speyer | If $k=2$, this is a well studied but not solved problem en.wikipedia.org/wiki/Partial_sorting . I have to assume that someone knows something about larger $k$. | |
| Nov 30, 2012 at 20:43 | comment | added | David E Speyer | This seems like a nontrivial algorithms question to me. It may be a standard result for the right people, but I don't think it is obvious and I would be interested in learning the answer. Voting to reopen. | |
| Nov 30, 2012 at 16:44 | comment | added | Debanjan Chanda | @Misha: I have already posted the MSE link. | |
| Nov 30, 2012 at 16:33 | comment | added | Misha | Try math.stackexchange instead f MO. | |
| Nov 30, 2012 at 16:33 | history | closed |
Benjamin Steinberg Misha Andrew Stacey Felipe Voloch Andy Putman |
off topic | |
| Nov 30, 2012 at 16:17 | history | asked | Debanjan Chanda | CC BY-SA 3.0 |