11165 - Galactic Travel

All about problems in Volume 111. 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
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

11165 - Galactic Travel

Post by lord_burgos »

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

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.

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

Post by lord_burgos »

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 :cry:

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

Post by Jan »

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:

Post by mf »

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:

Post by Erik »

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

Post by rio »

Erik wrote:Hello,

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

Cu, Erik :)
Found :D Thanks.

Post Reply

Return to “Volume 111 (11100-11199)”