Zomato OA 2022 - Friends
There are N people. For a pair of people (i, j), they have a friend value A[i][j]. We want to split these N people into 2 groups such that each person belongs to exactly one group, and each group contains at least one person.
The partition value of a split is defined as the minimum friend value of all pairs of different people within the same group. Our goal is to find the maximum partition value possible.
Suppose the minimum friend value of all pairs of different people from Group 1 is min1 and from Group 2 is min2. Then, the partition value is defined as:
partition value = min(min1, min2)
Input Format:
- The first line contains a single integer N representing the number of people.
- The next N lines contain N integers each, where A[i][j] represents the friend value between person i and person j.
Output Format:
- Print a single integer representing the maximum partition value possible.
Constraints:
- (3 < N <= 500)
- (1 <= A[i][j] <= 10^9) for (i != j)
- (A[i][i] = 0)
- (A[i][j] = A[j][i])
Example
Input:
4
0 2 3 4
2 0 1 5
3 1 0 6
4 5 6 0
Output:
2
Explanation:
For the given input, a possible way to partition the 4 people could be:
- Group 1: Persons 1 and 2
- Group 2: Persons 3 and 4
The minimum friend value for Group 1 (1, 2) is 2 and for Group 2 (3, 4) is 5.
Thus, the partition value is min(2, 5) = 2.
The goal is to maximize this partition value across all possible valid groupings.