HOMDEL - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Simple

PREREQUISITES:

Graph theory, Shortest Paths

PROBLEM:

You’re given an N * N grid where (i,j)th entry is the distance between ith and jth point. You’re given M queries consisting of three points A, B, C. You’re task is to find out shortest distances : d(A, C) and d(A,B) + d(B, C).

QUICK EXPLANATION:

Pre-compute all pair-shortest paths using Floyd-Warshall algorithm. Solve every query in O(1) time.

DETAILED EXPLANATION:

Number of queries is so large that we can’t hope to find the shortest distance separately for each query. So we must do some precomputation so that we can answer individual queries fast enough. But as vertices change with each individual query, we can’t precompute distances from some points only, we need all pair shortest paths. Once we figure out this much, we could choose one of the algorithms for all pair shortest paths. The most common and simplest algorithm is Floyd Warshall which has a runnning time of O(N3)

Those of you who don’t know this algorithm, let me describe it a little here and you can follow up in detail in any algorithms book. Floyd Warshall is essentially a DP algorithm. DP state is d(i, j, k) which denotes the shortest distance between vertices j and k such that only vertices 1…i are allowed to be intermediate vertices. Base case is when i = 0 and it means shortest paths between vertices when no intermediate vertices are allowed. This is same as edge lengths between pair of vertices. After that when we include a new ith vertex, shortest path between j and k might not change in which case it’d be d(i-1, j, k) or it might change. It’d change iff ith vertex appears on the shortest path in which case its value would be d(i-1, j, i) + d(i-1, i, k).

We can save space by storing the dp for different values of i in the same 2D array. Sample code follows:

for i from 1 to N
    for j from 1 to N
        dist[j][k] = adj[j][k] // adj[j][k] is the adjacency matrix, as given in the problem  

for i from 1 to N
   for j from 1 to N
       for k from 1 to N
           dist[j][k] = min(dist[j][k], dist[j[i] + dist[i][k])

SETTER’S SOLUTION:

Can be found here.

TESTER’S SOLUTION:

Can be found here.

5 Likes

Did Anyone try dijkstra’s algo for this problem???I am getting WA and I am unable to find any test case for which I get the incorrect output…

same here.

I implemented floyd warshall in python for this problem but it gives TLE T_T
how come? aren’t the time-limit suppose to be fair for all languages?

Also isn’t it weird how there are no accepted python solutions for HOMEDEL?

Same problem. Implemented Floyd Warshall algorithm in python. Got TLE

Tried the same in java and it got accepted. To anyone who’s reading this “DON’T IMPLEMENT THIS ONE IN PYTHON”. You’ll get TLE. If you do implement this one in PYTHON then please speak about it in this discussion.

You output wrong answer - http://ideone.com/Q0OcP

Incorrect answer too - http://ideone.com/CTSyW

Yes, i solved it using Dijkstra’s algorithm. Here is the link:
http://www.codechef.com/viewsolution/1216567