EXUNB - Editorial

PROBLEM LINK:

Practice
Contest

Author: Shashwat Chandra
Tester: Shashwat Chandra, Taranpreet Singh
Editorialist: Shashwat Chandra

DIFFICULTY:

EASY

PREREQUISITES:

Constructive algorithms

PROBLEM:

Output a tournament graph of size N such that all outdegrees are equal or report that it is not possible.

QUICK EXPLANATION:

For even N, it is not possible.
For odd N, from every node i direct edges to i+1,i+2,....,(i+(n-1)/2)%N outwards and rest inwards.

EXPLANATION:

Firstly, observe that if each player wins an equal amount of matches then that amount has to be \frac{N-1}{2} this is because the total number of matches is \frac{N*(N-1)}{2}.

Also, if N is even then \frac{N-1}{2} is not a natural number hence there is no scenario in which players win the same amount of matches for even N.

Now we provide a method to construct a solution for all odd N.

Label all the players from 0 to N-1 and consider them to lie on a circle in that order with player 0 and N-1 adjacent as well. Now for every player i, consider the closest \frac{N-1}{2} when we go clockwise from i, we set the winner of the matches between i and these nodes to be i.

Note that this ensures that each player wins exactly \frac{N-1}{2} matches and does not beat himself. We just have to prove that this assignment does not lead to any contradicting results. The proof for this is given below, before reading, do try to prove it yourself !

Proof

For the sake of contradiction, assume we have produced 2 contradicting assignments say for nodes A and B.

This means B is X \leq \frac{N-1}{2} places away from A and similarly A is at Y \leq \frac{N-1}{2} places away from B.
Also, summing up X and Y gives us the the total number of players, this is because we have completed a full circle counting each of the players exactly once.

Now, X+Y \leq \frac{N-1}{2}+\frac{N-1}{2} = N-1 which is clearly less than N.
Thus, we have reached a contradiction.

SOLUTIONS:

Setter’s Solution
Tester’s Solution

1 Like