ZIO05002 - Editorial

PROBLEM LINK : Problem 2

Editorialist : Subhesh

DIFFICULTY : EASY

PREREQUISITES : Graph Theory

Problem :
Given Route of Buses, You have to find a bus stop from where the maximum number of stops supervisor has to travel to reach any other bus stop is minimized.

Quick Explanation :
Create Graph of the given routes (undirected Graph as buses run in both directions). Now you just have to find out a node from which every other node is at minimum possible distance.

Explanation :
We shall create graph in which node corresponds to a bus stop and edges will specify the path which supervisor can travel.

consider Given Example:

49%20PM

The corresponding graph would be:

56%20PM
Now we have to minimize the maximum number of stops to travel to reach any other bus stop i.e. Best of the worst.

Let’s just assume each node as office of supervisor one by one and find out the best one:

Node 1 : max distance node is 6 which at 4 distance

Node 2 : max distance node is 6 which is at 3 distance

Node 3 : max distance node is 6 which is at 4 distance

Node 4 : max distance node is 1 or 3 or 6, all at 2 distance

Node 5 : max distance node is 1 or 3 which is at 3 distance

Node 6 : max distance node is 1 or 3 or 7 which is at 3 distance

Node 7 : max distance node is 1 or 3 or 6, all at 3 distance

So Node 4 (Bus stop 4) is the best stop no. to locate office of the supervisor as max distance possible to any other bus stop is 2 which is minimum among all other bus stop.

a)
42%20PM

The corresponding graph would be :

08%20PM

Now you can compare and figure out that the Node 6 (Bus stop 6) is the best possible stop no as maximum distance to any node is 4.

b)

31%20PM

Corresponding graph:

Again you can compare and figure out that the Node 15 (Bus stop 15) is the best possible stop as maximum distance to any node is 5

c)

42%20PM

Corresponding Graph:

28%20PM

Again you can compare and figure out that the Node 6 (Bus stop 6) is the best possible stop as maximum distance to any node is 5.