This is a live problem from interviewstreet.com: In the game challenges that we host, one practial problem that we face is to rank the contestants. Contestants need to submit code for a game problem and we pair up them against each other to see their relative performance.
The aim of this tournament is to rank the players on the quality of code they submit. The task for you is to come up with an approach to rank the players using as few matches as possible. Submission Notes: You have to complete the function "game" given for this task. You can also create your own data structures and functions as needed. The function "game" is passed as parameter the number of players "nPlayers" and players have ids from 0 to nPlayers-1( 0 and nPlayers-1 included ). This function should return a vector of player ids. In this vector better players have lower indices. You can make calls to a hidden function "gameResult" which takes as argument the id of two players and conduct a match, this function returns the id of winner among the two players. Scoring: The list of player that you produce is compared against the hidden expected list, and for each player the difference in their position from both lists is added. If this sum is less than 3*nPlayers you get a score based on the number of calls you made to function "gameResult". Less number of calls fetches higher score. Further Notes: This is approx-type problem so "compile and test" option might not work, so directly submit your code ans see the score in submissions tab. Since there is no deterministic minimal number of comparison, you may see you submission as wrong bu the score you get will give you an idea of your code's performance. The language shown for submission is C++, but it should not be a problem to the programmers of other language since the i/o and other details has been taken care of and you just need to write the appropriate functions. You can refer to http://www.cplusplus.com/doc/tutorial/ for more details if necessary. Standard header files/STL have already been included so you need not include/import additional header files. Note: nPlayers is not greater than 100. Different calls to gameResult between same pair of players may not necessarily return same winner always. We have tried to tweak a real game data by incorporate the elo rating system to determine the winner of matches. So in a call to gameResult, the winner is determined by that probability. Note: Don't give the the exact solution...jut m looking for an approach. Some of the approach I have followed are as: First Approach Have n/2 matches among n players then n/4 matches among previous looser and n/4 among previous winner Continue recursively. Second Approach Each player play against each other. The players having the maximum winning appear above in the returning queue Both the above approach doesn't seem working...can u please suggest what's going wrong here...and how to proceed further... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
