Help with algorithm problem from SPOJ

tags:

algorithm

views:

120

answers:

+1 Q:

Help with algorithm problem from SPOJ

I thought it would be a fun problem: Prime Path

But...It is hard for me. My only idea is "To do something with knapsack problem".. and no other ideas. Could You track me for good way? It's not for any challenge or University homework. I just want to learn something.

Ok, but firstly, how to find this prime numbers? Do i need to find all 4digit prime numbers, add it to graph?

For now i have generating all prime numbers.

http://pastebin.com/wbhRNRHQ

Could You give me sample code to declare graph build on neighbour list?

+5 A:

Seems like a straightforward graph path finding problem.

Take all 4 digit primes as the vertices. Connect two with an edge, if we can go from one to the other.

Now given two, you need to find the shortest path between them, in the graph we just formed. A simple BFS (breadth-first-search) should do for that.

For programming contests with time limits, you could even hardcode every possible prime pair path and get close to zero running time!

Moron 2010-07-10 22:57:08

Since there are multiple test cases, it might be worth running roy-floyd and answering each test case in `O(1)`.

IVlad 2010-07-10 23:02:22

For any particular prime, you can find all possible next-primes using a hash-table lookup. Each prime gets indexed in four tables, each based on all-but-one digit. Then, for each prime, you search four tables - again, each based on all-but-one digit, to find possible next primes. That's the only worthwhile addition I can think of - replaces the O(n^2) checks with an O(n), though with only primes <10,000 to worry about, it probably isn't a big deal anyway.

Steve314 2010-07-10 23:03:16

@Steve314: it wouldn't be O(n^2) anyway, since you can just construct an array of 10000 graph nodes with a flag to indicate primality. Do your prime sieve, then for each prime check each of the 9 * ceil(log10(n)) nodes it might possibly be connected to. O(n log n), which is good enough to beat the path-finding algorithm you're going to use next.

Steve Jessop 2010-09-06 18:44:01

Look into "breadth-first search". Also worth bearing in mind here that the problem can be approached "from both ends" simultaneously (a chain from numbers X to Y can be reversed to get Y to X, and you can exploit this). Precalculating primes will avoid much computation along the way.

Will A 2010-07-10 22:58:12

+3 A:

Build a graph where the nodes are all the 4 digit prime numbers, and there are arcs everywhere two numbers have three digits in common. From there, it's a basic graph traversal to find the lowest-cost path from one node to another.

Jerry Coffin 2010-07-10 22:58:27

Why -1 for this?

Moron 2010-07-10 23:09:01

@Moron: I kind of wondered the same, but nobody seems to be coming forward with an explanation. I was a few seconds slower than you were; I suppose somebody might have thought I copied it from you?

Jerry Coffin 2010-07-10 23:12:49

@Jerry: My guess is they just misunderstood what you wrote.

Moron 2010-07-10 23:21:50

I'd run a BFS using probable prime testing, which would work relatively well with only 4 digit numbers. With only 4 digits, also, you may want to use more exacting methods to produce all primes to compare against for faster prime checking.

Stefan Kendall 2010-07-10 22:59:08

I think that once you're at the BFS stage, there's no need for any primality testing at all.

IVlad 2010-07-10 23:11:33

It depends. If you don't construct the graph beforehand, and instead mark where you've been and derive a method from going from number A to all prime numbers reachable from A, the pre-population is not required.

Stefan Kendall 2010-07-11 00:55:32

ansaurus

tags:

views:

answers:

Help with algorithm problem from SPOJ

related questions