Zomato OA-4 2022

Problem Description

There are N individuals. For each pair of people (i, j), their friendship value is given by A[i][j]. The goal is to divide these N people into two distinct groups such that every individual belongs to exactly one group, and both groups contain at least one person.

The partition value of a split is defined as the smallest friendship value among all pairs of people within the same group. Specifically, if min1 is the minimum friendship value among all pairs of people in Group 1, and min2 is the minimum friendship value in Group 2, then the partition value is:

partition value = min(min1, min2)

Your task is to determine the maximum partition value possible by finding the optimal way to split the individuals into two groups.

Input Format:

• The first line contains an integer N representing the number of people.
• The next N lines contain N integers each, where A[i][j] represents the friendship value between person i and person j.

Output Format:

Print a single integer representing the maximum partition value that can be achieved.

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 partition could be:

• Group 1: Person 1 and Person 2
• Group 2: Person 3 and Person 4

In Group 1, the smallest friendship value is 2 (between Person 1 and Person 2).
In Group 2, the smallest friendship value is 5 (between Person 3 and Person 4).

Thus, the partition value is min(2, 5) = 2.

The objective is to maximize this partition value among all valid ways of grouping the individuals.