There are N cities and two newly built cities X and Y among them (1 <=X<=Y<= N) There exists a road between cities:
i and i+1 for each 1 to N
X and Y.
The task is to tell for each k from 1 to N, the number of pairs of cities (such that the shortest path between city i and city is k
Consider the following example.
N number of cities-3
X, first special city-1
Y second special city-3
The pair of cities having the shortest distance-1 are (1,2) (1,3) and (2,3)
There is no pair of cities with the shortest distance-2.
There is no pair of cites with the shortest distance-2
Hence the answer returned is (3,0,0)
Can someone explain how to approach this problem?
What? I can't understand the statement at all. Can you rephrase it?
Probably this:
You're given a graph with $$$n$$$ vertices indexed $$$1 \ldots n$$$. The graph has $$$n$$$ edges: an edge between $$$i$$$ and $$$i + 1$$$ for every $$$1 \le i < n$$$ and an extra edge between $$$x$$$ and $$$y$$$ for given $$$x$$$ and $$$y$$$.
For each $$$k$$$ in $$$1 \ldots n$$$, calculate the number of pairs $$$(u, v)$$$ such that the length of the shortest path between $$$u$$$ and $$$v$$$ is $$$k$$$.
Ah thanks
Draw the graph like this: a bamboo $$$1-2-3-\ldots-x-y-(y+1)-\ldots-n,$$$ with the additional cycle $$$x-(x+1)-\ldots-(y-1)-y.$$$
We can split the vertices into the three sets $$$A = \{1,2,\ldots,x-1\}, B = \{y+1,\ldots,n\}$$$ and the cycle $$$C = \{x,\ldots,y\}.$$$
It is easy to calculate the contributions from a bamboo graph $$$1-2-\ldots-j.$$$ There are $$$j-d$$$ pairs with distance $$$d.$$$ And note that the shortest path between a vertex in $$$A$$$ and $$$B$$$ never uses other edges in $$$G[C].$$$ So we can easily compute for $$$\{u,v\}$$$ with $$$u \in A, v \in B.$$$
Second case is $$$u, v \in C.$$$ This is also easy to do in $$$O(n).$$$ If cycle length is $$$j$$$ then there are exactly $$$j$$$ pairs with distance $$$d$$$ for each $$$d = 1,2,\ldots,\lfloor j/2 \rfloor.$$$
Final case is $$$u \in A, v \in C$$$ or $$$u \in B, v \in C.$$$ Suppose $$$u \in A, v \in C.$$$ Clearly shortest path never uses any vertices in $$$B.$$$ Then for $$$d=1$$$ there is only one pair, $$$\{x-1,x\}.$$$ For $$$d=2$$$ there are $$$1+2 = 3$$$ pairs, $$$\{x-2,x\}, \{x-1,x+1\}, \{x-1,y\}.$$$ Similarly for $$$d=3$$$ there are $$$1+2+2 = 5$$$ pairs, ie. $$$\{x-3,x\}, \{x-2,x+1\}, \{x-2,y\}, \{x-1,x+2\}, \{x-1,y-1\}$$$ and so forth.
Overall solution runs in $$$O(n).$$$
Could you provide more detailed for this ?
some pseudocode or something