In a tennis tournament of N players every player plays with every other player. The following condition always hold- If player P1 has won the match with P2 and player P2 has won from P3, then Player P1 has also defeated P3. Find winner of tournament in O(N) time and O(1) space. Find rank of players in O(NlogN) time. My Solution : The input is a boolean matrix where element matrix[i][j] indicates whether player i wins player j.
bool win[][]= {
{0, 0, 1, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 1, 1},
{0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{1, 0, 1, 1, 1, 0, 1},
{0, 0, 1, 1, 1, 0, 0}
};
So the winner could be found like,
int winner = 0;
for (int i = 1; i < PLAYER_COUNT; ++i) {
if (win[i][winner])
winner = i;
}
return winner;
For getting the rank of the players, I guess Topological sorting will be the good one. If Player 1 wins Player 2, then an edge is added lke this P1-> P2. If the Player 1 is winner here, then it would have edges to all the other players. Then topological sorting with winner as the source vertex, will give the rank of the player. Is my solution correct ? Is there any other efficient solution ? Any help would be great, thanks in advance.
The condition
If player P1 has won the match with P2 and player P2 has won from P3
Is defining a total ordering, i.e. if we define P1 < P2 for "P2 defeated P1", we have a transitive ordering relation <, which can be used exactly as the regular less-than relation in either sorting or finding the maximum. So for the implementation we can define the predicate bool lessThan(int p1, int p2) which will simply look up p1 and p2 relation in the matrix in O(1). And then use the predicate for "maximum" search, which is linear (O(N)), or for sorting (ranking), which is O(N log N).
Your approach for finding a winner seems correct. Indeed, assume the real winner number is W. When in your loop you have i==W, you will always have win[i][winner]==1, because player W has won everybody else. Therefore you will set winner=W, and will never more change it, because nobody has won over W.
Your code is also O(N), so I think it solves the first problem.
For the second problem, yes, topological sort would do, but a simple implementation will be O(N^2). However, note that your win table actually provides strict total order. Therefore you can just apply any standard sorting algorithm, and compare two players simply checking whether one has won over another. That is, just use
bool less(int playerA, int playerB) {
return win[playerA][playerB];
}
in std::sort.
This concept of strict total order also provides an alternative proof for you algorithm for finding a winned.
Here is the full code for your example: http://ideone.com/99DIQk