I am given an $n\times n$ matrix, $M$, that denotes the outcome of a series of races between $n$ contestants. Each contestant $i$ races against every other contestant $j$ and we say $M_{i,j}=1$ if $i$ beat $j$ (note $M_{i,j}=1\Leftrightarrow M_{j,i}=0$.) We then say that racer $i$ placed in the tournament if they lost at most $10$ races. I am supposed to define an algorithm that is linear in the number of queries made to matrix that returns all of the racers who placed (i.e. lost at most $10$ races.)

In order to reach this algorithm I have noted that the number of placers is bounded by $n=22$. We can thus define an algorithm that will reduce the problem to some case with under $22$ possible candidates and it is possible to brute force from there. I am, however, having trouble reducing the problem to only $22$ contestants. I have tried applying a dynamic programming approach by keeping track of how many races each contestant has won or lost and traversing the matrix diagonally (exploiting the fact that it is symmetric along the diagonal if you invert the values) and thus eventually eliminating $n-22$ of the contestants. I am having trouble showing whether this is indeed linear or, if it is not, how else I may further reduce the problem. Any help would be greatly appreciated, thanks!

  • 2
    $\begingroup$ Do you know how to do this with 10 replaced by 0? $\endgroup$ – Yuval Filmus May 17 '17 at 12:45
  • $\begingroup$ In that case first you could traverse all the entries in the upper diagonal of matrix, and thus eliminate half of the racers since someone loses at each race, and then do something similar but only on entries $M[i,j]$ where $i,j$ have yet to be eliminated. I'm a bit confused on how you could generalize this to the case where you have to observe many more losses in order to eliminate someone. $\endgroup$ – Twis7ed May 17 '17 at 12:51
  • 2
    $\begingroup$ Ok, so you know how to do it with at most 0 losses. Now try to do it with at most 1 loss. $\endgroup$ – Yuval Filmus May 17 '17 at 13:09
  • 2
    $\begingroup$ The way to solve a problem like this is to first solve it for 0 losses, then for 1 loss, and then hopefully in the general case. You already know what to do for 0 losses, so now you have to figure out what to do with 1 loss. Try generalizing your solution for no losses to the case in which one loss is allowed. Give it a few hours. $\endgroup$ – Yuval Filmus May 17 '17 at 15:34
  • 1
    $\begingroup$ The same issue still applies: ​ A n$^2$ algorithm that makes at least $(n^2)/3$ queries to the matrix would be linear in the number of queries made to the matrix, although not in n. ​ ​ ​ ​ $\endgroup$ – user12859 May 17 '17 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.