Last Updated: 24 Mar, 2021

K Centers

Moderate

Asked in companies

Solve now

Problem statement

In Ninja Land there are ‘N’ cities numbered from 0 to ‘N’-1. The distance between each pair of cities is given by N * N matrix ‘DIST’ where ‘DIST[i][j]’ denotes the distance between city ‘i’ and ‘j’.

Ninja wants to select ‘K’ (‘K’ <= ‘N’) cities and install Coding Ninjas Server in these cities. He wants to select ‘K’ cities in such a way that the maximum distance of a city from the Coding Ninjas Server is minimized.

Can you help Ninja in finding this maximum distance if he selects ‘K’ cities optimally? You should return this distance.

Note :

1. DIST[i][j] = DIST[j][i].
2. DIST[i][i] = 0.

Example :

Consider that there are 4 cities i.e. ‘N’ = 4, and the distance between each pair of cities is given by the following matrix ‘DIST’:  
             [0, 10, 7, 6]
             [10, 0, 8, 5]
             [7, 8, 0, 12]
             [6, 5, 12, 0]

Graphically, cities can be represented as -:

alt text

Assume Ninjas wants to install a server in 2 cities i.e ‘K’ = 2.  Then one optimal choice is to select cities 2 and 3.
After that, the minimum distance of city 0 from the server is  6  (i.e from city 2).
The minimum distance of city 1 from the server is 5  (i.e from city 3).
The minimum distance of cities 2 and 3 from the server is 0, as the server is installed in these cities.
Thus the maximum distance of the city from the server is max (6, 5, 0, 0) = 6.
So, we should return 6.
No selection of two cities can give a maximum distance which is less than 6.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.

The first line of each test case consists of two single space-separated integers ‘N’ and ‘K’ respectively representing the number of cities in Ninja Land and the number of cities where the server needs to be installed.

The next ‘N’ line follows in each test case. Each of these ‘N’ lines consists of ’N’ single space-separated integers. These ‘N’ lines together represent the matrix ‘DIST’.

Output Format :

For each test case, print a single integer that represents the maximum distance of a city from the server when ‘K’ cities are selected optimally.

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 15
1 <= K <= N
1 <= DIST[i][j] <= 10^9,  for i != j
DIST[i][j] = 0, for i = j

Time limit: 1 sec

Solve now

Approaches

01 Approach

This problem is an NP-Hard problem i.e there exists no polynomial-time solution for it. So we cannot do anything more than brute force for the exact solution.

Algorithm

This is a recursive algorithm.
Create an empty integer list/vector ‘SELECTED’ of size ‘N’.
Initialize an integer variable ‘RESULT’:= INF.
We make a recursive function, let it be kCenterHelper(K, N, SELECTED, DIST). It will one by one generate all possible ways of selecting ‘K’ cites from ‘N’.
- If K = 0, then do the following -:
  - Initialize an integer variable ‘MAXDIST’: = 0.
  - Run a loop where ‘i’ ranges from 0 to ‘N’-1. For each ‘i’ iterate over ‘SELECTED’ and find the minimum distance of the ith city from any of the selected cities and update ‘MAXDIST’ with the maximum of its current value and this minimum distance.
  - Do ‘RESULT’:= max(‘RESULT’, ‘MAXDIST’).
- Otherwise, let ‘PREV’ be -1 if ‘SELECTED’ is empty, else it should be the last integer of ‘SELECTED’, Run a loop where ‘i’ ranges from ‘PREV’+1 to ‘N’ -1 and for each ‘i’ do the following -:
  - Append ‘i’ in ‘SELECTED’.
  - Call kCenterHelper(K-1, N, SELECTED, DIST).
  - Pop last element from ‘SELECTED’.
Call kCenterHelper with given values, and return ‘RESULT’.

Solve now