EXUNB - Editorial

editorial
, ,
1

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

2 Likes
2

the problem says "Your task is to determine if such a scenario can take place and if yes find one such scenario ."Except for n=2, all the cases have at least one condition in which each of them win same number of matches, that is 1 wins 2, 2 wins 3 , and so on up to n, and n wins 1. i.e., every team wins only one match of all they played .However my solution giving the same result is marked wrong. Here is my java code finally submitted:
CodeChef: Practical coding for everyone

Please clarify my doubt cause neither I got why my logic is wrong nor the one in editorial.

1 Like
3

Hey, for a team to win only 1 match, they will have to lose the other n-1 matches since each team plays exactly 1 match with every other team.

Now the question is there must be someone who won those matches right?
So for each match where some team loses, there must be some other team that gains a victory, hence your logic is wrong.

For n>3, there cannot be any scenario that each team wins only 1 match. Some team will definitely have to win more than 1 match for other teams to lose.

4

Ohk, now i got this. Thank you very much.