11165 - Galactic Travel

Moderator: Board moderators

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

11165 - Galactic Travel

any hint ?? I don't understand , How to solve it ?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You can use some data structure (linked list, or segments tree) to improve it, so that its overall running time will depend on the number of forbidden pairs or intervals, instead of the total number of edges.

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
mf wrote:Basic algorithm is breadth-first search.
You can use some data structure (linked list, or segments tree) to improve it, so that its overall running time will depend on the number of forbidden pairs or intervals, instead of the total number of edges.
yes, I think in that, but a don't know how to save, because in the breadth-first search i need to mark some position. :S the worse case is when i have a line and i can visit 41,000 / 2 nodes

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I haven't got accepted. But I can give you some ideas. Suppose you have designed the edges in the linked fashion.

[0] -> (1 - 100) -> (500 - 1000) -> NULL
[1] -> (600 - 900) -> (950-1000) -> NULL

When searching from 0 you have visited 1 - 100 and 500 - 1000. Now when searching from 1 you don't need to visit again.

So, try to figure out a structure such that you can find large visited intervals in almost constant time.

EDIT : Got Accepted.
Last edited by Jan on Sat Feb 24, 2007 7:14 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
lord_burgos wrote:yes, I think in that, but a don't know how to save, because in the breadth-first search i need to mark some position.
Keep a linked list of unvisited nodes.
When you expand a node during breadth-first search, scan this list and erase all nodes from it, except those in forbidden intervals.

Total runtime of the algorithm would be proportional to number of forbidden pairs.
The worse case is when i have a line and i can visit 41,000 / 2 nodes
So what?

Anyway, worst-case input in the form of a line consists of just about sqrt(5000000) < 2300 vertices.

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:
Hello,

there exists a solution in almost O(n+k).

Cu, Erik

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Erik wrote:Hello,

there exists a solution in almost O(n+k).

Cu, Erik
Found Thanks.