In a tournament, there are n participating teams are labelled from 1 to n. Each pair of teams will play against each other exactly once. Thus, a total of [n(n-1)/2] matches will be held, and each team will compete in n − 1 of these matches. There are only two possible outcomes of a match: 1. The match ends in a draw, in which case both teams will get 1 point. 2. One team wins the match, in which case the winning team gets 3 points and the losing team gets 0 points. Design an algorithm which runs in O(n2 ) time and provides a list of results in all [n(n-1)/2] matches which: (a) ensures that all n teams finish with the same points total, and (b) includes the fewest drawn matches among all lists satisfying (a). Do not write the code, give steps and methods. Explain the steps of algorithm, and the logic behind these steps in plain English. PLease give the total time complexity.
In a tournament, there are n participating teams are labelled from 1 to n. Each pair of teams will play against each other exactly once. Thus, a total of [n(n-1)/2] matches will be held, and each team will compete in n − 1 of these matches. There are only two possible outcomes of a match:
1. The match ends in a draw, in which case both teams will get 1 point.
2. One team wins the match, in which case the winning team gets 3 points and the losing team gets 0 points.
Design an
(a) ensures that all n teams finish with the same points total, and
(b) includes the fewest drawn matches among all lists satisfying (a).
Do not write the code, give steps and methods. Explain the steps of algorithm, and the logic behind these steps in plain English. PLease give the total time complexity.
Step by step
Solved in 3 steps
