11457 - Classified

All about problems in Volume 114. 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
baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

11457 - Classified

Post by baodog » Tue Jun 24, 2008 10:29 pm

I tried constructing RMQ from DFS tree of each node with no parents.
However this TLEs, since there can be O(n) such RMQs.
Is there some way to do it with one RMQ, so each query is O(logn)?
How did you guys solve this one :-) ? Thanks!

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11457 - Classified

Post by baodog » Wed Jun 25, 2008 1:01 am

maybe construct one RMQ, keep list of indices for each node, and find the closest two nodes by binary search.

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

Re: 11457 - Classified

Post by rio » Wed Jun 25, 2008 4:18 am

This problem is about finding LCA in DAG.

I used an algorithm with O(nm) for precalculation and O(1) for query.
-----
Rio

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11457 - Classified

Post by baodog » Wed Jun 25, 2008 6:03 am

THanks. Do you have a reference? Can you describe your algorithm? Thanks!

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

Re: 11457 - Classified

Post by rio » Wed Jun 25, 2008 6:29 am

Search google with "lca dag".
I found paper about it in the first page.
-----
Rio

Post Reply

Return to “Volume 114 (11400-11499)”