Ninja And Cities

Hard
0/120
Average time to solve is 50m
profile
Contributed by
4 upvotes
Asked in companies
AdobeLTI - Larsen & Toubro InfotechAdrosonic

Problem statement

Ninja decided to find the distance between the neighbouring cities and then store them for future use. He took data from the map and developed an input format. He is given an integer ‘N’ denoting the number of cities and then he has an array of size ‘N - 1’ that stores a pair of numbers at each index. Let the pair be ‘I1’ and ‘I2’, which will denote a bidirectional edge between the two cities ‘I1’ and ‘I2’.

A subtree is a subset of cities, where each city can be reached from every other city of the subset. The path between each pair passes only though the cities present in the subset. Two subtrees are taken differently if there are one or more cities in one subtree not present in the other.

Now, you need to create an array of ‘N' - 1 elements where the ‘ith’ element is the number of subtrees in which the maximum distance between any two cities is equal to ‘i’.

Note: 
1. Note that there exists a unique path between each pair of cites. Also, the final array that you need to create should be 1-indexed, meaning cities with a maximum distance = 1 should be stored on the normal 0th index.

2. Also, note that the distance between two is the number of cities you cross in between.
Example: 
Given 'N' = 7, and Array = {[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7]}

So the tree of cities formed in this case would look like:


In the above problem, the subtrees with subsets {[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7]}, have a maximum distance of 1, so put 6 on index 1.

Similarly the subtrees with subsets {[1, 2, 4], [1, 2, 5], [2, 1, 3], [4, 2, 5], [1, 3, 6], [1, 3, 7], [6, 3, 7], [1, 2, 4, 5], [1, 3, 6, 7]} have a maximum distance of 2, so put 9 on index 2.

Now, the subtrees with subsets {[4, 2, 1, 3], [2, 1, 3, 7], [5, 2, 1, 3], [2, 1, 3, 6], [4, 5, 2, 1, 3], [2, 1, 3, 6, 7]} have a maximum distance of 3, so put 6 on index 3.

Now, the subtrees with subsets {[4, 2, 1, 3, 7], [4, 2, 1, 3, 6], [5, 2, 1, 3, 7], [5, 2, 1, 3, 6], [5, 2, 1, 3, 6, 7], [4, 2, 1, 3, 6, 7], [4, 2, 5, 1, 3, 6], [4, 2, 5, 1, 3, 7], [4, 2, 5, 1, 3, 6, 7]} have a maximum distance of 4, so put 12 on index 4.

No subtree has two nodes where the maximum distance between them is 5 and 6 so print 0 on both these indexes.

 Final resultant array = [6, 9, 6, 9, 0, 0]
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ which denotes the number of test cases. 

The first line of each test case contains a single integer ‘N’ denoting the number of cities.

The next ‘N - 1’ lines of each test contain an array of ‘N' - 1 pairs where each pair denotes path from ‘I1’ to ‘I2’
Output Format: 
For each test case, you need to return ‘N - 1’ space-separated integers where the ‘ith’ element denotes the number of paths in which the maximum distance between the two cities is equal to ‘i’.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
2 <= N <= 15
size of array == N - 1
1 <= I1, I2 <= N

Time limit: 1 sec
Sample Input 1:
1
3
1 2
1 3
Sample Output 1:
2 1
Explanation of Sample Output 1:
In test case 1, The tree of cities formed in this case would look like:


In the above problem, the subtrees with subsets {[1, 2], [1, 3]} have a maximum distance of 1, so print 2.

Similarly, the subtrees with subsets {[2, 1, 3]} have a maximum distance of 2, so print 1.
Sample Input 2:
2
2
1 2
4
1 2
1 3
2 4
Sample Output 2:
1
3 2 1
Explanation of Sample Output 2:
In test case 1, The tree of cities formed in this case would look like:


In the above problem, the subtrees with subsets {[1, 2]} have a maximum distance of 1, so print 1.

In test case 2, The tree of cities formed in this case would look like:


In the above problem, the subtrees with subsets {[1, 2], [1, 3], [2, 4]} have a maximum distance of 1, so print 3.

Similarly the subtrees with subsets {[1, 2, 4], [2, 1, 3]} have a maximum distance of 2, so print 2.

Now, the subtrees with subsets {[4, 2, 1, 3]} have a maximum distance of 3, so print 1.
Hint

Can you think of using the Floyd Warshall Method using DFS to check for city distances?

Approaches (1)
Floyd Warshall + DFS

The simple idea that we use in this approach will be to check all the subsets of cities. For every subset, we will check if it is valid or not. If the subtree is valid, we then find the maximum distance between the two nodes. Now store it according to 1-based indexing.

 

If for any root, the number of visited nodes equals the number of elements in the subset, it is a valid subtree.

 

The steps are as follows:

 

  • Create an adjacency matrix let’s say ‘ADJ’ from the given cities or edges.
  • Now, calculate the shortest distance from each node to every other node using the Floyd Warshall technique and store it in another 2D array, let’s say ‘DIST’.
  • Then generate all the subsets using bit manipulation and for every subset:
    • If the size of the subset is greater than one and it is a valid subtree:
      • Calculate the maximum distance in that subtree by checking the distance of every node from every other node.
  • In order to check if the subtree is valid:
    • Create a linear array let’s say ‘VISITED’.
      • If the node is not present in the subset:
        • ‘VISITED[i]' = 0
      • If the node is present in the subset:
        • ‘VISITED[i]' = 1
      • If the node is visited while doing DFS on the subtree:
        • ‘VISITED[i]' = 2
    • We start traversing using the DFS approach from any given node in the subset, traversing further to neighbour cities or nodes only if that node is present in the given subset.
    • We stop traversing when there are no more options left.
    • Using this method, a subset will be valid if all the ‘i’th nodes that initially were ‘VISITED[i]' = 1, are now updated to ‘VISITED[i]' = 2.
    • The summation of all the elements in ‘VISITED[]’ will become 2 * size of the given subset.
    • If the subtree is valid we return true else false.
Time Complexity

O(2 ^ N), Where ‘N’ is the number of cities.

 

Since the tree formed with depth = N - 1, will have a total number of  2 ^ N nodes, traversing them in depth-first manner. Hence the overall time complexity of this approach is O(2 ^ N).

Space Complexity

O(N * N), Where ‘N’ is the number of cities.

 

Since the space required for the recursive stack is O(N), also the space required to store the shortest distance is O(N * N), so the overall space complexity will be O(N * N).

Code Solution
(100% EXP penalty)
Ninja And Cities
Full screen
Console