[EM] Easy River definition (also my site is back up)

[Kristofer Munsterhjelm]

On 2024-03-10 02:07, Kevin Venzke wrote:
> Hi Closed Curves, Mike,
> 
> I thought about the definition a little. Let's try this, using the "bins" concept
> rather than the "subordination" one:
> 
> 1. Initially each candidate is in their own "bin" named for themselves.
> 2. Consider each pairwise defeat from strongest to weakest.
> 3. For a given defeat X>Y, move everyone in bin Y to the bin that X is in.
> 4. End loop. Go to the next defeat.
> 5. Elect one of the candidates who remains in their original bin.
> 
> Things to note about this:
> Once Y has moved anywhere, no one will ever be in bin Y again. So we don't actually
> have to throw out other defeats over Y.
> If X is in Y's bin when X>Y is considered, rule 3 says that everyone in bin Y
> (including X) moves to where X is, which is already Y. So nothing will happen in
> this case either.
> 
> Should be right.

This concept of "bins" seems to have a pretty close connection to 
disjoint-set data structures, which should give River n^2 time 
complexity for all practical purposes.

(Unless I'm mistaken, the complexity would be O(n^2 * a(n^2)), where a 
is the inverse Ackermann function.)

-km