How to Solve “efficientRoadNetwork” in CodeFights

The Problem:

Once upon a time, in a kingdom far, far away, there lived a king Byteasar III. As a smart and educated ruler, he did everything in his (unlimited) power to make every single system of his kingdom efficient. The king went down in history as a great road builder: during his reign a great number of roads were built, and the road system he created was the most efficient for those dark times.

When you started to learn about Byteasar’s III deeds in your history classes, the creeping doubt crawled into the back of your mind: what if the famous king wasn’t so great after all? According to the most recent studies, there were n cities in the Byteasar’s kingdom, which were connected by the two-ways roads. You managed to get information about this roads from the university library, so now you can write a function that will determine whether the road system in Byteasar’s kingdom was efficient or not.

A road system is considered efficient if it is possible to travel from any city to any other city by traversing at most 2 roads.

Example

  • For n = 6 and
    roads = [[3, 0], [0, 4], [5, 0], [2, 1],
              [1, 4], [2, 3], [5, 2]]
    

    the output should be

    efficientRoadNetwork(n, roads) = true.

    Here’s how the road system can be represented:

  • For n = 6 and
    roads = [[0, 4], [5, 0], [2, 1],
              [1, 4], [2, 3], [5, 2]]
    

    the output should be

    efficientRoadNetwork(n, roads) = false.

    Here’s how the road system can be represented:

    As you can see, it’s only possible to travel from city 3 to city 4 by traversing at least 3 roads.

Input/Output

  • [time limit] 7000ms (py)
  • [input] integer nThe number of cities in the kingdom.

    Constraints:

    1 ≤ n ≤ 250.

  • [input] array.array.integer roadsArray of roads in the kingdom. Each road is given as a pair [cityi, cityj], where 0 ≤ cityi, cityj < n and cityicityj. It is guaranteed that no road is given twice.

    Constraints:

    0 ≤ roads.length ≤ 35000,

    roads[i].length = 2,

    0 ≤ roads[i][j] < n.

  • [output] booleantrue if the road system is efficient, false otherwise.

The Solution:

up.PNG

The Explanation:

Basic graph knowledge. (Adjacency Matrix)

The rows are the sources of the edges. Columns are the targets.

If we have a road from x to y; we have a road from y to x. (Since roads are to both directions.)

If there is no road between two cities, the adj cell for those two will be zero infinity, but since we will check if it is shorter than 2 or not, we can just put any number bigger than 2. I put 4.

update the roads as we iterate over the roads array.

update path from each node to itself. We can say the length from each node to itself is zero.

I used floyd-warshall all-pairs-shortest-path algorithm since the limits on number of nodes is small and it’s easy to implement. (Complexity of this algorithm is high, so, with higher number of nodes, we would have to use a more efficient algorithm.)

Check if all the roads are shorter than 3, if not return False.

else, return True.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s