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:
- Build hotels in cities 2, 3, and 4.
- Build hotels in cities 2, 3, and 5.
- Build hotels in cities 2, 4, and 5.
- 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, 0-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[i][1]
SOLUTION (IN PYTHON):
#!/bin/python3
import math
import os
import random
import re
import sys
from itertools import product
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()