For every possible pairing of competitors, a battle was fought, with one competitor triumphing over another.

A tournament king is a competitor for which it is true that when comparing to any other competitor,

the king either triumphed over that competitor directly, or the king directly triumphed over another competitor who directly triumphed over that competitor.

Given such a tournament, give an efficient algorithm to quickly find any single tournament king.

You may choose one of three data storage methods:

Method I

You have at your disposal a look-up table which given any pair of competitors, will tell you who won.

Such a look-up is considered one operation.

You may also remove entries from this table, and each removal is considered an operation.

You may simultaneously look-up and remove the entry that is looked up, and that is considered a single operation.

You can make a copy of the initial table, which is N*(N-1)/2 operations (roughly N^2).

Method II

You have a list of N smaller lists, where each of the smaller lists corresponds to a competitor, and the contents of the smaller lists are those the competitor defeated. Looking up/modifying/creating an element from any list is 1 operation.

Method III

You have a list of N smaller lists, where each of the smaller lists corresponds to a competitor, and the contents of the smaller lists are those the competitor was defeated by. Looking up/modifying/creating an element from any list is 1 operation.

What is the time complexity of operations in your algorithm (an estimate of the number of operations as a function of N, where any proportional constant on the whole expression, or constant terms can be ignored)?

What about finding all tournament kings?

Who can give the algorithms with the lowest time complexity?

## Question

## mmiguel

There are a set of N competitors in a tournament.

For every possible pairing of competitors, a battle was fought, with one competitor triumphing over another.

A tournament king is a competitor for which it is true that when comparing to any other competitor,

the king either triumphed over that competitor directly, or the king directly triumphed over another competitor who directly triumphed over that competitor.

Given such a tournament, give an efficient algorithm to quickly find any single tournament king.

You may choose one of three data storage methods:

Method I

You have at your disposal a look-up table which given any pair of competitors, will tell you who won.

Such a look-up is considered one operation.

You may also remove entries from this table, and each removal is considered an operation.

You may simultaneously look-up and remove the entry that is looked up, and that is considered a single operation.

You can make a copy of the initial table, which is N*(N-1)/2 operations (roughly N^2).

Method II

You have a list of N smaller lists, where each of the smaller lists corresponds to a competitor, and the contents of the smaller lists are those the competitor defeated. Looking up/modifying/creating an element from any list is 1 operation.

Method III

You have a list of N smaller lists, where each of the smaller lists corresponds to a competitor, and the contents of the smaller lists are those the competitor was defeated by. Looking up/modifying/creating an element from any list is 1 operation.

What is the time complexity of operations in your algorithm (an estimate of the number of operations as a function of N, where any proportional constant on the whole expression, or constant terms can be ignored)?

What about finding all tournament kings?

Who can give the algorithms with the lowest time complexity?

Edited by mmiguel## Link to comment

## Share on other sites

## 12 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.