Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Tournament Kings


  • Please log in to reply
12 replies to this topic

#1 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 04 September 2012 - 01:02 AM

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, 04 September 2012 - 01:11 AM.

  • 0

#2 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 532 posts

Posted 04 September 2012 - 03:35 AM

so it sounds like a round robin tourney.
Spoiler for i think method 3 allows for the most straight forward algorithm

Edited by phil1882, 04 September 2012 - 03:35 AM.

  • 0

#3 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 05 September 2012 - 05:04 PM

Couple of questions about definitions:
(1) "to quickly find any single tournament king": Does this mean you'll come to me and say, "find me a tournament king"? Or does it mean "Here is a single competitor: see if he/she is a tournament king"? I'm assuming the former.
(2) Method II has a list of lists. Each list operation counts as 1 operation. I assume that means stepping through the main list as well. How is it sorted? Do we get to declare as part of the solution how we wish it were sorted? Do we have to include any such sorting of that list as part of the algorithm's time? (Yes, Method III also has such a list--same questions applies)
  • 0

#4 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 05 September 2012 - 05:11 PM

Phil, imagine competitor P, who beat everybody but Q, and Q lost to everybody but P.
Q is a tournament king, even though he lost to almost everybody.
  • 0

#5 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 05 September 2012 - 07:47 PM

Spoiler for Simple (and slow) algorithm using Beats lookup table

edit: gack, formatting.

Edited by CaptainEd, 05 September 2012 - 07:53 PM.

  • 0

#6 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 06 September 2012 - 02:30 AM

Couple of questions about definitions:
(1) "to quickly find any single tournament king": Does this mean you'll come to me and say, "find me a tournament king"? Or does it mean "Here is a single competitor: see if he/she is a tournament king"? I'm assuming the former.
(2) Method II has a list of lists. Each list operation counts as 1 operation. I assume that means stepping through the main list as well. How is it sorted? Do we get to declare as part of the solution how we wish it were sorted? Do we have to include any such sorting of that list as part of the algorithm's time? (Yes, Method III also has such a list--same questions applies)


(1) The Former

(2) Pulling out any element from any list is one operation (including the main list). For sorting, I didn't really specify a way of identifying competitors in order to sort. Say for example that, you uniquely assign a number from 0 to N-1 for each competitor. In the main list, you can access any element in constant time (O(1)). You can say the xth slot corresponds to competitor x. For the sublists, you can assume whatever sorting you want as long as you consistently assume it is the same way the whole algorithm (unless of course you spend operations to change it in some way).
  • 0

#7 curr3nt

curr3nt

    The

  • Members
  • PipPipPipPip
  • 2839 posts
  • Gender:Male
  • Location:in a field of spatulas...

Posted 06 September 2012 - 04:26 PM

Spoiler for hmmm...

Edited by curr3nt, 06 September 2012 - 04:27 PM.

  • 0

#8 curr3nt

curr3nt

    The

  • Members
  • PipPipPipPip
  • 2839 posts
  • Gender:Male
  • Location:in a field of spatulas...

Posted 06 September 2012 - 06:22 PM

Spoiler for I had issues with my logic...but I think I have them fixed now.

Edited by curr3nt, 06 September 2012 - 06:32 PM.

  • 0

#9 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 07 September 2012 - 02:46 AM

so it sounds like a round robin tourney.

Spoiler for i think method 3 allows for the most straight forward algorithm


Spoiler for

  • 0

#10 mmiguel

mmiguel

    Advanced Member

  • Members
  • PipPipPip
  • 134 posts
  • Gender:Not Telling

Posted 07 September 2012 - 02:50 AM

Phil, imagine competitor P, who beat everybody but Q, and Q lost to everybody but P.
Q is a tournament king, even though he lost to almost everybody.


Spoiler for

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users