?

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:35 pm (UTC)
Yeah, that's along the right lines. Your approach counts the number of peaks, but you also have to take into consideration the valleys. Having a single lift to every peak doesn't guarantee that you can "get out of" all of the valleys. Also, the algorithm has to be linear to run in time, so you have to be a bit careful about how you do the DFS (your "go to 1" step makes it sound potentially quadratic).

Union-find with path compression is an algorithm for computing the union of disjoint sets. It runs really really quickly (basically linear), and is easy to code. Here's the algorithm:

// these operations assume a, b are not 0

const int NODES = 100000;

int root[NODES];

int getroot( int a ) {
    return !root[a] ? a : root[a] = getroot(root[a]);
}

void join( int a, int b ) {
    if( (a=getroot(a)) != (b=getroot(b)) ) root[a] = b;
}

(Reply) (Parent) (Thread)
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)