You are viewing a single comment's thread. Return to all comments →
WOOHOO, I DID IT!!! sorry, it just took me that long.
And because I'm still high on success, I will leave some tips for despairing ones. (I also don't understand a thing in the editorial)
Calculating every node-combination in a set is O(n²), so we have to condense the set somehow...
Let's say, we have two nodes, v1 and v2; v is the lowest common ancestor(LCA):
v / \ .. .. / \ v1 v2
The thing we have to calculate is v1*v2*d(v1,v2). d() is distance.
v1*v2*d(v1,v2)
It can be split up like this: v1*d(v1,v)*v2 + v2*d(v2,v)*v1
v1*d(v1,v)*v2 + v2*d(v2,v)*v1
Now, let's add another node (u is the new LCA):
u / \ .. .. / \ \ .. v2 v3 / v1 v1*v2*d(v1,v2) + (v1*d(v1,u)+v2*d(v2,u))*v3 + v3*d(v3,u)*(v1+v2) = v1*v2*d(v1,v2) + ((v1+v2)*d(v2,u)+v1*(depth(v1)-depth(v2)))*v3 + v3*d(v3,u)*(v1+v2)
If v1 and v2 are already processed, the only variables are u and v3. We can replace the rest with constants:
C0 + (C1*d(v2,u)+C2)*v3 + v3*d(u,v3)*C1
...there, it's no longer necessay to handle v1 and v2 seperately. (as long as nothing relevant is below v1 or between v1 and v2)
I also used lookup-tables for depth and predecessor.
Please let me know if something is too confusing.
Seems like cookies are disabled on this browser, please enable them to open this website
Kitty's Calculations on a Tree
You are viewing a single comment's thread. Return to all comments →
WOOHOO, I DID IT!!! sorry, it just took me that long.
And because I'm still high on success, I will leave some tips for despairing ones. (I also don't understand a thing in the editorial)
Calculating every node-combination in a set is O(n²), so we have to condense the set somehow...
Let's say, we have two nodes, v1 and v2; v is the lowest common ancestor(LCA):
The thing we have to calculate is
v1*v2*d(v1,v2)
. d() is distance.It can be split up like this:
v1*d(v1,v)*v2 + v2*d(v2,v)*v1
Now, let's add another node (u is the new LCA):
If v1 and v2 are already processed, the only variables are u and v3. We can replace the rest with constants:
...there, it's no longer necessay to handle v1 and v2 seperately. (as long as nothing relevant is below v1 or between v1 and v2)
I also used lookup-tables for depth and predecessor.
Please let me know if something is too confusing.