How to Solve “newRoadSystem” in CodeFights

The Problem:

Once upon a time, in a kingdom far, far away, there lived a king Byteasar I. As a kind and wise ruler, he did everything in his (unlimited) power to make life of his subjects comfortable and pleasant. One cold evening a messenger arrived to the king’s castle with the latest news: all kings in the Kingdoms Union started to enforce traffic laws! In order not to lose his membership in the Union, king Byteasar had to do the same in his kingdom. But what would the citizens think of it?

The king decided to start introducing the changes with something more or less simple: change all the roads in the kingdom from two-directional to one-directional. He personally prepared the roadRegister of the new roads, and now he needs to make sure that the road system is convenient and there will be no traffic jams, i.e. each city has the same number of incoming and outgoing roads. As the Hand of the King, you’re the one who should check it.

Example

  • For
    roadRegister = [[false, true,  false, false],
                    [false, false, true,  false],
                    [true,  false, false, true ],
                    [false, false, true,  false]]
    

    the output should be
    newRoadSystem(roadRegister) = true.

    The cities will be connected as follows:

    Cities 0, 1 and 3 (0-based) have one incoming and one outgoing roads, and city 2 has two incoming and two outgoing roads. Thus, the output should be true.

  • For
    roadRegister = [[false, true,  false, false, false, false, false],
                    [true,  false, false, false, false, false, false],
                    [false, false, false, true,  false, false, false],
                    [false, false, true,  false, false, false, false],
                    [false, false, false, false, false, false, true ],
                    [false, false, false, false, true,  false, false],
                    [false, false, false, false, false, true,  false]]
    

    the output should be
    newRoadSystem(roadRegister) = true.

    The cities will be connected as follows:

    Each city has one incoming and one outgoing road.

  • For
    roadRegister = [[false, true,  false],
                    [false, false, false],
                    [true,  false, false]]
    

    the output should be
    newRoadSystem(roadRegister) = false.

    The cities will be connected as follows:

    City 1 has one incoming and none outgoing roads, and city 2 has one outgoing and no incoming roads.

Input/Output

  • [time limit] 4000ms (py)
  • [input] array.array.boolean roadRegister

    Since the cartography is not yet invented in the kingdom, the registers are used instead. A register is stored as a square matrix, with its size equal to the number of cities in the kingdom. If roadRegister[i][j] = true, then there is a road from the ith to the jth city; the road doesn’t exist otherwise.

    It is guaranteed that there are no loop roads, i.e. roads that lead back to the same city it originated from.

    Constraints:

    1 ≤ roadRegister.length ≤ 100,

    roadRegister[0].length = roadRegister.length,

    roadRegister[i][i] = false.

  • [output] boolean

    true if the new road system is good enough, false otherwise.

The Solution:

code

The Explanation:

Basic graph knowledge. (Adjacency Matrix)

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

This means that the total number of trues in a row shows the total outgoing edge count. And, the total number of trues in columns show the incoming edges.

The question asks if every node has the same number of outgoing and incoming edges.

so we need to compare count(trues in column i) == count(trues in row i)

Because python can sum booleans (true = 1 and false = 0), we can use predefined sum function.

If any one node does not have the same incoming and outgoing edge count, return 0 (false).

Otherwise return 1 (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