372. K Centers Problem

Given n vertices of a complete graph with a symmetric distance matrix, choose k of them as 'centers' to minimize the maximum distance from any vertex to its nearest center, using the standard greedy: start with vertex 0 as the first center, then repeatedly add whichever remaining vertex is currently farthest (in nearest-center distance) from all centers chosen so far, until k centers have been chosen. Print the resulting maximum distance from any vertex to its nearest center.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer k, the number of centers to choose. Each of the next n lines contains n space-separated integers, the symmetric distance matrix. Output: Print a single integer - the maximum distance from any vertex to its nearest chosen center.

1 <= k <= n <= 500

Updating every vertex's nearest-center distance after adding EACH new center (not just checking distances to the newest center alone) is essential - a vertex's true nearest center could be ANY of the centers chosen so far, not necessarily the most recently added one.

Choose k 'center' points from a set so that the maximum distance from any point to its nearest center is minimized. Brute force: Try every possible combination of k centers out of n vertices directly, computing the maximum nearest-center distance for each combination - this is combinatorially expensive (choosing k out of n), impractical for larger n. Optimised: The greedy 'always add the currently farthest-from-any-center vertex as the next center' strategy is a well-known 2-approximation algorithm for this NP-hard problem - while it doesn't guarantee the mathematically optimal solution in general, it's provably never worse than twice the optimal, and this specific problem defines exactly this greedy procedure as the expected approach.

Following the specified greedy rule, start with vertex 0 as the sole center. Then, k-1 times, for every vertex not yet a center, scan through all currently chosen centers to find its distance to the nearest one, and pick whichever vertex has the largest such nearest-center distance as the next center to add. Because each of the k rounds re-scans every non-center vertex against every already-chosen center from scratch, work is redone that could otherwise be reused from the previous round. Time: O(k^2 * n) Space: O(k)

Enumerate every possible subset of k vertices out of the n given vertices as the set of centers. For each candidate subset, compute for every vertex its distance to whichever chosen center is nearest to it, and take the maximum such nearest-center distance across all vertices as that subset's score. Report the minimum score achieved over all subsets considered; this finds the true globally optimal set of centers, but the number of subsets to check grows combinatorially. Time: O(2^n * n) Space: O(k)

Keep one array nearestDist[] where nearestDist[v] holds the distance from vertex v to the closest center chosen so far, initialized once vertex 0 is picked as the first center. After adding each new center, do a single pass over all vertices updating nearestDist[v] to the smaller of its current value and the distance to the new center, instead of re-scanning all previous centers, then simply pick the vertex with the largest nearestDist[] value as the next center. Since each of the k rounds now only costs O(n), the whole greedy selection runs faster overall, and the final answer is the maximum nearestDist[] value once all k centers are chosen. Time: O(k*n) Space: O(n)

1. Start with vertex 0 as the first center, and initialize every vertex's 'distance to nearest center' using just this one center. 2. Repeatedly add whichever remaining vertex currently has the LARGEST nearest-center distance as the next new center (it's the 'most underserved' point). 3. After adding it, update every vertex's nearest-center distance using this new center (it may now be closer to this new center than to any previous one); repeat until k centers are chosen.

Time: O(k * n) - for each of the k centers chosen, updating every vertex's nearest-center distance takes O(n). Space: O(n), for tracking every vertex's current nearest-center distance.

k = n (every vertex becomes its own center), k = 1 (a single center), and n at its maximum of 500 to confirm the greedy farthest-point selection runs efficiently.

Be ready to mention that K-Centers is NP-hard in general, and that this greedy approach is a well-known APPROXIMATION algorithm (not guaranteed globally optimal) - the problem here specifically asks for the result of running this exact greedy procedure, not the true theoretical optimum.