12 replies to this topic

[mmiguel]

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

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.

Spoiler for

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

[mmiguel]

Spoiler for hmmm...

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?

Spoiler for

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]

Spoiler for

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!

Spoiler for proof of correctness

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 by mmiguel, 07 September 2012 - 03:03 AM.