A total of n players have competed in a chess tournament. In particular every pair of players i and j played one single game. All results of the tournament are encoded in a n × n-matrix A, where for every pair of different players A[i, j] encodes the result of the game that i and j played in the following way:
A[i, j] = Option 1: i if i wins Option 2: 0 draw Option 3: j if j wins
We say that a player d is a superchampion if she has won all her games. We would like an algorithm that receives A as input and returns a superchampion d if exists. If there is no superchampion then the algorithm must return 0. Give a divide-and-conquer algorithm for the task. It is enough to obtain a O(n log n) . In your algorithm is perfectly fine to consider the matrix A to be global variable so that it does not need to be included in the input of each recursive call.
I assume each player plays once against other players. Also, the diagonal will contain 0's as each player cannot play against herself, and the matrix will be symmetric. In addition, I think the base case would be that we only have 1 player, so that player will be the superchampion. However, I do not know how to check for a superplayer, i.e., how to check the rows and columns of the matrix without a double for loop, which would result in O(n^2).
Firstly note that there is at most one superchampion. Secondly note that each comparison eliminates at least one candidate to be superchampion.
That's why we can firstly eliminate $n - 1$ candidates and secondly check whether the remaining one is actual superchampion. Let $c$ be the only candidate among the first $p$ players. Initially $c \gets 1$ and $p \gets 1$. Then while $p < n$ we compare our candidate $c$ with $p + 1$-st player. If $p + 1$ wins, then $c \gets p + 1$. In any case we increase the number of players: $p \gets p + 1$. This part takes $\mathrm O(n)$ of time and gives us the only possible candidate $c$. The second part is to check if $c$ is actual superchampion. It is trivial and takes $\mathrm O(n)$ of time too.