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).