Rafat's blog

Dijkstra Variation (Help Needed)
By Rafat, history, 5 years ago, In English

Problem: Given a weighted graph G, source node, destination node and a value X. find the shortest route from source to destination.

If there is a path from U to V with cost C, and you choose the path the value of X will change to X=gcd(X,C). So if the new X is less than the cost of next edge you can't pick the next edge. This way you have to find out the shortest path possible.

Node and Edges size can be up to 10^5 and the time limit is 5s. What's the idea to solve this problem??

For better understanding you can find the problem statement Here (Problem F)

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Since your title is Dijkstra variant, I assume you know about creating a state graph and running Dijkstra on it.

Whenever you are at a node two parameters are enough to define the state: the current node number and the current X.

So we consider a new graph where each node represents state (node, current_x ). For each edge u-v with say w weight in the original graph we would have an edge from (u,x) to ( v, gcd(x,w) ) if x>=w ; in this state graph.

Now we can run Dijkstra on this graph from (start,X). The answer would be the minimum of all the distances to (destination,c) nodes. That is all the state nodes that contain the destination in its parameter.

Running Time: All the intermediate X will be a factor of initial X. So the number of nodes and edges in the new graph is n*no_factors(X).

No factors = O( sqrt(X) ).

So running time would be n*sqrt(X) * log( n*sqrt(X) ).

Also X<=10^5 no_factors cant be more than 130. So we can replace sqrt(n) above with 130.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about problem A ?

any idea ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Precalculate N%r for all r where r is prime or a perfect power. Then do CRT to find the rest of the modulo.

    For example. 12 can be expressed as (3^1)*(2^2). This way every composite number can be expressed as the product of prime and perfect powers. And since we precalculated the modulo value for prime and perfect powers. Now we can use CRT to find the value of N%r with help of prime factors of r.

    To understand how CRT solves this problem, you can get help from Here

    → Reply