Can anyone explain to me what the problem asks, and then a working algorithm or
ID: 3582949 • Letter: C
Question
Can anyone explain to me what the problem asks, and then a working algorithm or plan with walkthrough, I don't need code, just what the problem wants , what concepts i have to use(like graph) and finally, a working algorithm which can be easily converted to a java code.
Here it goes
In a different universe, on a planet called Middle Earth, the Queen of Gondor wants to find the a suitable location for her capital city.
There are many cities in the kingdom, and they are connected by the Numenorian Roads. These roads do not obey the physical laws of our universe. So, if a road exists between cities A and B, and a road exists between cities C and D, then it takes the same amount of time to get to A from B (or vice versa) as it would take to go from C to D (or vice versa).
The Queen would however like to select the capital city, let us call this city MT. Let X be the city that takes the longest time to travel to from MT. The Queen wants to minimize the time it takes to reach X. In some sense, the Queen wants a central location.
To make the requirement more precise, let us start with N cities, X[0], ..., X[N-1]. Let t(X[i,j]) be the shortest time (here, this is equivalent to using the smallest number of roads) it takes to travel to X[j] from X[i]. We can then define t(X[i]) as max{t(X[i,1]), t(X[i,2]), ..., t(X[i,n-1])} (maximum value from the set of travel times).
The goal is to select X[i] such that t(X[i]) <= t(X[j]) for all j in 0 .. N-1 (minimize the maximum travel time over all the cities). It is possible that more than one city meets this requirement so we want to identify the set of such cities. Then the Queen can use other criteria to locate the capital.
You are provided the road network information as a (potentially long) string, roadNetwork, and the number of cities, n. For 0 <= i < n and 0 <= j < n, the character at position n*i+j in the string tells us if there is a road from city X[i] to city X[j]. There is a 1 in that position if there is a road and a 0 otherwise. You may assume that there is always a road from X[i] to itself and that n*i+i is always a 1.
You want to use this information and determine the set of potential locations for the capital. You are to return a set of integers that contains the indices of the cities that are suitable. So, if City 1 is a good choice then the set you return should contain 1.
The preconditions for the method you have to implement are stated in the skeleton source code.
Examples
roadNetwork = "1" and n=1.
Returns: a set with 0.
roadNetwork = "1111" and n=2
Returns: a set with 0 and 1.
roadNetwork = "111111111" and n=3
Returns: a set with 0, 1, and 2.
roadNetwork = "111110101" and n=3
Returns: a set with 0.
One can reach all cities in one step from City 0, but we would need two steps to go from City 1 to City 2 or from City 2 to City 1. The maximum travel time from City 0 to every part of the kingdom is only 1 step, whereas the maximum travel time from the other cities is 2 steps.
roadNetwork = "1101 1111 0111 1111".replaceAll("\s","") and n=4
Returns: a set with 1 and 3.
One can reach every city in one step from Cities 1 and 3. From City 0, one can reach City 2 in two steps (either via City 1 or City 3), and the same is true for City 2 (in terms of reaching City 0).
roadNetwork = "11100 11100 11111 00111 00111".replaceAll("\s","") and n=5
Returns: a set with 2.
One can reach every other city in one step from City 2.
roadNetwork = "10101 01110 11110 01111 10011".replaceAll("\s","") and n=5
Returns: a set with 0, 1, 2, 3 and 4.
The maximum travel time from every city is 2 steps. So all cities are equally "central".
Explanation / Answer
The problem says that it would take same amount of time to travel between any adjacent cities, “So, if a road exists between cities A and B, and a road exists between cities C and D, then it takes the same amount of time to get to A from B (or vice versa) as it would take to go from C to D (or vice versa)”. Therefore we can say the above network is the graph which has all the edges of equal weight. This would mean that all the edges are of same length, say, unit length [Technically, this graph is an unweighted graph].
In order to find a shortest path between any two vertices in the above graph, we can use BFS instead of Djsktra's Algorithm because all the edges are of equal length(unweighted graph). Now how are we going to find the shortest path in terms of no. of edges (since all edges are of unit distance) from a given vertex v?
It's simple, In BFS algorithm, we first label all the nodes that are at a distance of 1 from v, then we label all the nodes that are at a distance of 2 from v, and so on. This label is nothing but the shortest distance.
Now, we have to find the node (city) that is closest to all other nodes. Iterate over each city and find the city which has the lowest sum of incoming weights. And in this procedure, use BFS to find the shortest distance between the cities.
The total Runtime of the above algorithm will be O(V.(V+E)) = O(V3), since E=O(V2)
In order to find the shortest distances, please refer BFS algorithm.