Home
hackerrank
hackerrank certification

Hotel Construction - Problem Solving (Intermediate) | Hacker Rank

 



Hotel Construction


There are a certain number of cities in a country, some of which are connected with bidirectional roads. The number of roads is one less the number of cities, and it is possible to travel between any pair of cities using the roads. The distance between cities is the minimum number of roads one has to cross when traveling between them. How many ways are there to build exactly 3 hotels, each in a different city, such that the distance between every pair of hotels is equal?

For example, let's say there are n = 5 cities, and roads = [[1, 2], [1, 3], [1, 4], [1, 5]]. This means that city 1 is connected with roads to all other cities, as seen below:



There are 4 ways to build exactly 3 hotels, each in a different city, so that the distance between every pair of hotels is equal:

    1. Build hotels in cities 2, 3, and 4.
    2. Build hotels in cities 2, 3, and 5.
    3. Build hotels in cities 2, 4, and 5.
    4. Build hotels in cities 3, 4, and 5.


In all these cases, the distance between every pair of hotels is 2. Because there are 4 ways to accomplish this, the answer is 4.



Function Description

Complete the function numberOfWays in the editor below. The function must return an integer denoting the number of ways to build 3 hotels in such a way that the distance between every pair of hotels is equal.


numberOfWays has the following parameter:     int roads[n-1][2]: a 2-dimensional array of integers, O-indexed, such that roads[i][0] and roads[i][1] denote cities that are connected by the ith road
    Returns: int: the number of ways to build 3 hotels in such a way that the distance between every pair of hotels is equal



Constraints

    • 4<=n<=50
    • 1 <=roads[i][0]<=n
    • 1<=roads[i][1]<= n
    • roads[i][0]!= roads[0][1]

Input Format For Custom Testing

In the first line, there is a single integer, n - 1, denoting the number of roads.
In the second line, there is a single integer, 2.
Then, n - 1 lines follow. The ith of them contains two space-separated integers, roads[i][0] and roads[i][1], denoting the cities that are connected by roads.

Solution in Python:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#!/bin/python3

import math
import os
import random
import re
import sys

from itertools import product

#
# Complete the 'numberOfWays' function below.
#
# The function is expected to return an INTEGER.
# The function accepts 2D_INTEGER_ARRAY roads as parameter.
#

def numberOfWays(roads):
    n = len(roads) + 1
    adj = [[] for _ in range(n)]
    for i, j in roads:
        adj[i - 1].append(j - 1)
        adj[j - 1].append(i - 1)
    ans = 0
    
    def dfs(x, d):
        dist[x] = d
        for y in adj[x]:
            if dist[y] == -1:
                dfs(y, d + 1)
    
    # Brute force.
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                dist = [-1 for _ in range(n)]
                dfs(i, 0)
                if dist[j] != dist[k]:
                    continue
                dist = [-1 for _ in range(n)]
                dfs(j, 0)
                if dist[i] == dist[k]:
                    ans += 1
    return ans

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    roads_rows = int(input().strip())
    roads_columns = int(input().strip())

    roads = []

    for _ in range(roads_rows):
        roads.append(list(map(int, input().rstrip().split())))

    result = numberOfWays(roads)

    fptr.write(str(result) + '\n')

    fptr.close()
Labels : #hackerrank ,#hackerrank certification ,#problem solving ,#problem solving (intermediate) ,#python ,

Post a Comment