PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
We are given a graph having n nodes and m edges and asked a lot of queries. Given a vertex u, find the sum of the shortest path distances from u to every other vertex ( actually in the problem not to all other vertices, to all floors of every other building ). There can be at most 100 buildings and each building can have a million floors, so we have a huge number of vertices in the graph. But the edges are only a few, and so the number of vertices having degree more than 2 are very less, at most 300. Consider a vertex u of degree 1. It can reach to other vertices only by going through its neighbor. What about vertices of degree 2 ? They can reach other vertices going through one of its 2 neighbors. So we don’t have to worry about vertices of degree ≤ 2 while finding the shortest path distances, at least initially. We can run a simple floyd-warshall’s algorithm only on the canonical vertices ( those with degree > 2 ) and every other vertex has to reach out to any other vertex by passing through these canonical vertices and the good thing is, we just need to consider at most 2 of them, one above and one below ( viewing in buildings and floors setting ).
Given vq = (bq,fq), we can’t go through each vertex u and sum its distance to vq, as there are huge number of vertices. Lets go building by building and with in each building, we look at the segments between the canonical nodes. Consider one such segment A–u1–u2–u3–…--uk–B, where A and B are the canonical nodes and the vertices ui form a chain joining them. We know the distance from A to vq ( = dA ) and B to vq ( = dB ) and each of ui can either each vq through A or B only. Also, if a vertex ui prefers A over B, then all the vertices between A and ui also prefers A over B. This observation leads to a binary search based approach. We actually want to find the maximum index i such that the vertex ui prefers A over B and then we can just sum up the distances ( dA+1, dA+2, …, dA+i ) using a simple formula. Index i is (dB-dA+k)/2 if dA <= dB else k - (dA-dB+k)/2. Some variation of ideas in this problem and a simpler version of it is used in ACM-ICPC Regionals of Amritapuri this year.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.