?

Log in

Greek letters - lars0 [entries|archive|friends|userinfo]
lars0

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Greek letters [Dec. 17th, 2004|02:25 pm]
lars0
I may be the only person in the history of the world to encounter a scenario where a factor of O(\alpha(n)) was of practical significance. \alpha(n), of course, being the inverse Ackermann function.

My solution to 'skiareas' from last weekend's USACO contest timed out on a single test case because I used union-find with path compression (as I am wont to do) to merge ajacent points of the same height into a single component, rather than coding up a BFS/DFS.

(Yeah, I know there are factors besides the asymptotic complexity, such as an function call for each lookup, but that should never be the difference between passing and failing a test case. I've always found USACO's super-strict time limits irritating.)
linkReply

Comments:
From: lars0
2004-12-18 10:43 pm (UTC)
Just to clarify, getroot(a) returns the root (or label) of the set that a is a member of. Initially all of the elements belong to their own singleton set, so the root of each set is just that node. When sets are joined together, each set becomes represented as a tree, where root[a] essentially points to the parent of a. join(a,b) merges the set containing a with the set containing b, by making the root of a a child of the root of b.

The algorithm is super efficient because every time you query for which set a node belongs to, it traverses the path from that node all the way up to the root of the tree. Each node that is visited along this path gets its parent pointer replaced with a pointer directly to the root, thereby "collapsing" the tree so it's very flat.

For example, say you had a tree like this:

1
|
2
|
3
|
4
|
5

Now suppose you call getroot(4). Then the new tree becomes:
1--2
|
+--3
|
+--4--5
So now all future operations become faster, because all of the nodes are pushed really close to the root.
(Reply) (Parent) (Thread)