11354 - Bond

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11354 - Bond

Post by sclo » Sun Nov 25, 2007 11:02 am

Looking at the problem, I think the solution can be found by kruskal's algorithm. The problem is how to answer the queries fast enough? In the worst case, the tree can be linear, each query takes O(n) time.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

I've not coded it yet.

Post by jah » Sun Nov 25, 2007 11:57 am

Hi, I've have not coded it yet but what I thought was the following.

First compute the min spanning tree.
Apply an algorithm similar to LCA to the tree as in problem QTREE of http://www.spoj.pl. (http://www.spoj.pl/problems/QTREE/)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Nov 25, 2007 12:24 pm

I think that works, but I haven't solved that problem yet.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Nov 25, 2007 12:32 pm

If you use union by rank, you can answer queries in O(log n) on the union find tree.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Nov 25, 2007 1:17 pm

can you please describe it a bit more?
Self judging is the best judging!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Nov 26, 2007 12:26 am

I would like to know how the query can be answered directly on the union find datastructure. I solved it by using the dividing the tree into sqrt(height) layers, and precompute the maximum edge weight to previous layer.

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Mon Nov 26, 2007 8:54 am

Code: Select all

I would like to know how the query can be answered directly on the union find datastructure.
It is interesting to me too.

I solved it just using LCA and calculated maximum edge cost from each vertex by 2^j vertices up.
Then each querry also can be answered in O(log n). Answer is the maximum value from LCA to vertex1 or from LCA to vertex 2.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Nov 26, 2007 9:32 am

When constructing the union-find tree, add weight info to the edge in the union-find tree.
For query(a,b):

Code: Select all

query(a,b) := max(the last edge weight of path a -> LCA(a,b),
                  the last edge weight of path b -> LCA(a,b));
LCA(a,b) is LCA of a,b in union-find tree.
The hight of tree is O(logn), so you could answer the query with O(logn).
-----
Rio

davidsun
New poster
Posts: 5
Joined: Fri Apr 11, 2008 3:08 pm

Re: 11354 - Bond

Post by davidsun » Fri Apr 11, 2008 3:13 pm

I really want to know what your algorithm is. I know I can use a segment tree or something like this, but I really don't know HOW to use it.
I'm interested in your O(log N) solution, so can you explain it more carefully, or do you have any lecture about it?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Re: 11354 - Bond

Post by rio » Sat Apr 19, 2008 4:14 pm

davidsun wrote:I really want to know what your algorithm is. I know I can use a segment tree or something like this, but I really don't know HOW to use it.
I'm interested in your O(log N) solution, so can you explain it more carefully, or do you have any lecture about it?
Union-find tree is different from segment tree.
Heres a pdf about union-find tree I found on web:
http://valis.cs.uiuc.edu/~sariel/teach/ ... /22_uf.pdf

Once you understand about this data structure, I think you could understand the algorithm I said.
-----
Rio

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

Re: 11354 - Bond

Post by empo » Sun Dec 07, 2008 7:25 am

Can anyone tell me the algo for LCA...i am not getting it...
"Accepted" is my passion but RTE is my weakness.....

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11354 - Bond

Post by Jan » Fri Feb 27, 2009 12:39 pm

Ami ekhono shopno dekhi...
HomePage

aman181993
New poster
Posts: 1
Joined: Fri Mar 29, 2013 10:59 pm

Re: 11354 - Bond

Post by aman181993 » Fri Mar 29, 2013 11:03 pm

(http://www.spoj.pl/problems/QTREE/)

can some1 please explain the updation part in this problem using LCA

csprajeeth
New poster
Posts: 5
Joined: Sat May 26, 2012 7:25 pm

Re:

Post by csprajeeth » Mon Dec 23, 2013 10:27 pm

rio wrote:When constructing the union-find tree, add weight info to the edge in the union-find tree.
For query(a,b):

Code: Select all

query(a,b) := max(the last edge weight of path a -> LCA(a,b),
                  the last edge weight of path b -> LCA(a,b));
LCA(a,b) is LCA of a,b in union-find tree.
The hight of tree is O(logn), so you could answer the query with O(logn).
-----
Rio
Brilliant. I never thought of that. I constructed a new tree and answered LCA(u,v) using heavy-light decomposition technique... Got me the last rank... and then used ur idea... rank 19. :D thanks

Post Reply

Return to “Volume 113 (11300-11399)”