Tournament Kings

[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 September 4, 2012 by mmiguel

[phil1882]

so it sounds like a round robin tourney.

start with a randomly selected player, and see who defeated him.

if he was defeated by more than 1/2 of the players, we can eliminate him as a contender.

then for each person that beat him, again look at the number of losses.

keep on doing so untill you have eliminated all but a single player.

time complexity approximately n* log(2) n.

Edited September 4, 2012 by phil1882

[CaptainEd]

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)

[CaptainEd]

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.

[CaptainEd]

Call the Beats table B. If Q beats P, we'll say "Q B P"

Copy Beats table, call it B2. If Q beats someone who beats P, we'll say "Q B2 P"

For Q in 1...N

....For P in 1...N (skip Q)

........if Q B P

............for each R in 1...N (skip Q and P)

................if P B R

....................set Q B2 R

....count = 0

....For P in 1...N (skip Q)

........if Q B P | Q B2 P, increment count

....if count = N-1, Stop, declaring Q to be a TK. (or print is a TK)

If you want all TKs, then don't stop, just print and keep going through all Q in 1...N

The time is order of n^3 in either case.

Analogous algorithm on Lost-to lists is also n^3 for one TK.

I'm not proud...

edit: gack, formatting.

Edited September 5, 2012 by CaptainEd

[mmiguel]

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).

[curr3nt]

I ran every combination for N = [4,5,6]. There were no cases where the king didn't score against another player either directly or indirectly. I'm pretty sure that will hold for N > 6...

Can I cheat and use all three methods?

Use method 2 and method 3 for a given player with method 1 until a win is found against method 3 player or no win found.

w = M2[p].count


If w = 0 then k = false --- exit

If w = N - 1 then k = true --- exit


l = N - w - 1


k = true

For i = 1 to w

  f = false

  For j = 1 to l

    r = M3[p][j]

	If M1[ M2[p][i] , r ] = r Then

	  f = true

	  j = l

    End If

  Next

  If f = false Then

	k = false

    j = w

  End if

Next


If k = true then "Congrats on being a TOURNEY KING"

I think this would work... what would the lookup count be?

Edited September 6, 2012 by curr3nt

[curr3nt]

Option Explicit

Const N = 10

Public Function TourneyKing(player As Long) As Boolean

Dim rng As Range

Dim w As Long, l As Long

Dim M2(N - 1) As Long, M3(N - 1) As Long

Dim i As Long, j As Long, f As Boolean

Dim king As Boolean


Set rng = game.Range("$E$5:$N$14")

w = 0

l = 0

For i = 1 To N

	 If Not i = player Then

		 If rng.Cells(player, i) = player Then

			 M2(w) = i

			 w = w + 1

		 Else

			 M3(l) = i

			 l = l + 1

		 End If

	 End If

Next


king = True

[s]If w = 0 Then

	 king = False

Else[/s]

	 For j = 0 To l - 1

		 f = False

		 For i = 0 To w - 1

			 If rng.Cells(M2(i), M3(j)) = M2(i) Then

				 f = True

				 i = w

			 End If

		 Next

		 If Not f Then

			 king = False

			 j = l

		 End If

	 Next

[s]End If[/s]

Set rng = Nothing


TourneyKing = king

End Function

Still not sure what the operation count would be for this.

N-1 to build the M2/M3 arrays for a player

Max of win * loss of lookups to determine indirect wins

Would it be a max:

( N - 1 ) + ( w * l ) or 9 + 5 * 4 = 29 if N = 10?

If you want to count adds/lookups to the M2 and M3 I created too then it would be:

2 * ( N - 1 ) + 3 * ( w * l ) or 2 * 9 + 3 * 5 * 4 = 78 if N = 10?

Multiple by N to get all players. So 290 or 780 depending on how you want to score it?

-edit-

grr...I crossed out a part of the script that isn't required.

Edited September 6, 2012 by curr3nt

[mmiguel]

so it sounds like a round robin tourney.

start with a randomly selected player, and see who defeated him.

if he was defeated by more than 1/2 of the players, we can eliminate him as a contender.

then for each person that beat him, again look at the number of losses.

keep on doing so untill you have eliminated all but a single player.

time complexity approximately n* log(2) n.

this is basically the same algorithm i came up with, for finding a single king.

I would use method II, which allows you to see who any given competitor defeated

while king not found

{

pick a competitor at random.

delete everyone that this competitor defeated (this should be proportional to n operations)

if competitor is last one

{

he is king

}else{

delete him too

}

}

on average, deleting everyone a competitor is defeated reduces the number of competitors left by some proportion.

Thus the number of times this must be done is proportional to the log of n.

Each time this is done, there are something proportional to n operations due to deletions.

The time complexity is there for O(n*log(n)), as phil stated.

I don't think there is an algorithm with better time complexity for finding a single tournament king.

This algorithm does not find all tournament kings though.

Nice work phil!

[mmiguel]

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.

this is true, and one can think of a contrived example where in each step of elimination, you can only eliminate one or two participants.

this would give time complexity O(n^2), which isn't all that great.

however, the famous sorting algorithm quicksort has a similar weakness for certain initial orderings.

in practice, it is well known to have O(n*log(n)) time complexity on average, although for certain initial conditions can have O(n^2).

given the similarities to quicksort, I would say that phil's algorithm justly deserves the O(n*log(n)) label.

[mmiguel]

Call the Beats table B. If Q beats P, we'll say "Q B P"

Copy Beats table, call it B2. If Q beats someone who beats P, we'll say "Q B2 P"

For Q in 1...N

....For P in 1...N (skip Q)

........if Q B P

............for each R in 1...N (skip Q and P)

................if P B R

....................set Q B2 R

....count = 0

....For P in 1...N (skip Q)

........if Q B P | Q B2 P, increment count

....if count = N-1, Stop, declaring Q to be a TK. (or print is a TK)

If you want all TKs, then don't stop, just print and keep going through all Q in 1...N

The time is order of n^3 in either case.

Analogous algorithm on Lost-to lists is also n^3 for one TK.

I'm not proud...

edit: gack, formatting.

this looks like it works and has O(n^3) time complexity

[mmiguel]

I ran every combination for N = [4,5,6]. There were no cases where the king didn't score against another player either directly or indirectly. I'm pretty sure that will hold for N > 6...

Can I cheat and use all three methods?

Use method 2 and method 3 for a given player with method 1 until a win is found against method 3 player or no win found.

w = M2[p].count


If w = 0 then k = false --- exit

If w = N - 1 then k = true --- exit


l = N - w - 1


k = true

For i = 1 to w

f = false

For j = 1 to l

r = M3[p][j]

	If M1[ M2[p][i] , r ] = r Then

	 f = true

	 j = l

End If

Next

If f = false Then

	k = false

j = w

End if

Next


If k = true then "Congrats on being a TOURNEY KING"

I think this would work... what would the lookup count be?

Looks like you are trying to prove that at least one tournament king exists regardless of who wins who.

I would use mathematical induction.

Prove that this is true for something simple, like n=2.

Then prove that the truth of the statement for n, implies the truth of the statement for n+1.

i.e., pretend you already know it is true for arbitrary n, then prove that it must also be true for n+1.

Based on double loop, I think this is O(n^2) algorithm.

Your second post has a double loop too, so I think they are both O(n^2).

[mmiguel]

this is basically the same algorithm i came up with, for finding a single king.

I would use method II, which allows you to see who any given competitor defeated

while king not found

{

pick a competitor at random.

delete everyone that this competitor defeated (this should be proportional to n operations)

if competitor is last one

{

he is king

}else{

delete him too

}

}

on average, deleting everyone a competitor is defeated reduces the number of competitors left by some proportion.

Thus the number of times this must be done is proportional to the log of n.

Each time this is done, there are something proportional to n operations due to deletions.

The time complexity is there for O(n*log(n)), as phil stated.

I don't think there is an algorithm with better time complexity for finding a single tournament king.

This algorithm does not find all tournament kings though.

Nice work phil!

Let's say we pick random competitor A.

Let W(A) be the set of competitors who won against A and L(A) be the set of competitors that lost to A.

Selection of A allows us to partition the competitors into three groups:

W(A),

A,

and L(A).

Notice that it is true for any member of W(A), that they defeated A directly, and defeated everyone in L(A) indirectly i.e. they defeated A who defeated whoever we are talking about in L(A).

Thus for any member of W(A), to determine that they are a king, we merely need to prove that they defeated everyone else in W(A) directly or indirectly.

That is, pretending that W(A) is the only thing in the whole world (ignoring A and L(A)), find a tournament king there.

This is the same thing as the initial problem, except we reduced the problem size!

Keep doing this until you have eliminated all but 1 competitor.

By the logic above, he has defeated everyone else either directly or indirectly, and is a tournament king.

QED

Edited September 7, 2012 by mmiguel