New Year's Problem (Codeforces 1619D)
Tags: Greedy, binary search

Vlad has $$$n$$$ friends, for each of whom he wants to buy one gift for the New Year.There are $$$m$$$ shops in the city, in each of which he can buy a gift for any of his friends. If the $$$j$$$-th friend ($$$1 \le j \le n$$$) receives a gift bought in the shop with the number $$$i$$$ ($$$1 \le i \le m$$$), then the friend receives $$$p_{ij}$$$ units of joy. The rectangular table $$$p_{ij}$$$ is given in the input.Vlad has time to visit at most $$$n-1$$$ shops (where $$$n$$$ is the number of friends). He chooses which shops he will visit and for which friends he will buy gifts in each of them.Let the $$$j$$$-th friend receive $$$a_j$$$ units of joy from Vlad's gift. Let's find the value $$$\alpha=\min\{a_1, a_2, \dots, a_n\}$$$. Vlad's goal is to buy gifts so that the value of $$$\alpha$$$ is as large as possible. In other words, Vlad wants to maximize the minimum of the joys of his friends.For example, let $$$m = 2$$$, $$$n = 2$$$. Let the joy from the gifts that we can buy in the first shop: $$$p_{11} = 1$$$, $$$p_{12}=2$$$, in the second shop: $$$p_{21} = 3$$$, $$$p_{22}=4$$$.Then it is enough for Vlad to go only to the second shop and buy a gift for the first friend, bringing joy $$$3$$$, and for the second — bringing joy $$$4$$$. In this case, the value $$$\alpha$$$ will be equal to $$$\min\{3, 4\} = 3$$$Help Vlad choose gifts for his friends so that the value of $$$\alpha$$$ is as high as possible. Please note that each friend must receive one gift. Vlad can visit at most $$$n-1$$$ shops (where $$$n$$$ is the number of friends). In the shop, he can buy any number of gifts.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input.An empty line is written before each test case. Then there is a line containing integers $$$m$$$ and $$$n$$$ ($$$2 \le n$$$, $$$2 \le n \cdot m \le 10^5$$$) separated by a space — the number of shops and the number of friends, where $$$n \cdot m$$$ is the product of $$$n$$$ and $$$m$$$.Then $$$m$$$ lines follow, each containing $$$n$$$ numbers. The number in the $$$i$$$-th row of the $$$j$$$-th column $$$p_{ij}$$$ ($$$1 \le p_{ij} \le 10^9$$$) is the joy of the product intended for friend number $$$j$$$ in shop number $$$i$$$.It is guaranteed that the sum of the values $$$n \cdot m$$$ over all test cases in the test does not exceed $$$10^5$$$.

Output: Print $$$t$$$ lines, each line must contain the answer to the corresponding test case — the maximum possible value of $$$\alpha$$$, where $$$\alpha$$$ is the minimum of the joys from a gift for all of Vlad's friends.


Sample Inputs:
5

2 2
1 2
3 4

4 3
1 3 1
3 1 1
1 2 2
1 1 3

2 3
5 3 4
2 5 1

4 2
7 9
8 1
9 6
10 8

2 4
6 5 2 1
7 9 7 2

Sample Outputs:
3
2
4
8
2

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def new_years_problem(m, n, joy_by_shop):
    best_present_by_friend = [0] * n
    for i in range(m):
        for j in range(n):
            best_present_by_friend[j] = max(best_present_by_friend[j], joy_by_shop[i][j])
    best_present_with_min_joy = min(best_present_by_friend)
    optimal_joy = 0
    if n > m:
        return best_present_with_min_joy
    for i in range(m):
        joys = sorted(joy_by_shop[i], reverse=True)
        optimal_joy = max(optimal_joy, min(best_present_with_min_joy, joys[1]))
    return optimal_joy
for _ in range(int(input())):
    input()
    (m, n) = map(int, input().split())
    joy_by_shop = [None] * m
    for i in range(m):
        joy_by_shop[i] = list(map(int, input().split()))
    sys.stdout.write(f'{new_years_problem(m, n, joy_by_shop)}\n')

Solution (Python):
from sys import stdin
import math
from collections import deque
from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
input = stdin.readline

def log(n, m):
    (res, val) = (0, 1)
    while True:
        if n == val:
            return res
        elif n > val:
            return res - 1
        res += 1
        val *= m

def ceil(m, n):
    val = m // n
    if m % n != 0:
        return val + 1
    return val

def square(a, p, low, high):
    while low < high:
        mid = (low + high) // 2
        val = mid ** p
        if a > val:
            low = mid + 1
        elif a == val:
            return mid
        else:
            high = mid
    if low ** p > a:
        return low - 1
    else:
        return low
for _ in range(int(input())):
    input()
    (m, n) = map(int, input().split())
    (arr, seconds, fvals) = ([], 0, [0] * n)
    for _ in range(m):
        row = list(map(int, input().split()))
        for i in range(n):
            fvals[i] = max(row[i], fvals[i])
        row.sort()
        seconds = max(seconds, row[-2])
    print(min(seconds, min(fvals)))

Solution (Python):
import sys

def read_line():
    return sys.stdin.readline().strip()

def get_max_2_value(arr):
    max_0 = -1
    max_1 = -1
    for i in range(len(arr)):
        if max_0 == -1 or arr[i] >= arr[max_0]:
            max_1 = max_0
            max_0 = i
        elif max_1 == -1 or arr[i] >= arr[max_1]:
            max_1 = i
    return arr[max_1]
t = int(read_line())
for _ in range(t):
    read_line()
    nm = read_line().split()
    m = int(nm[0])
    n = int(nm[1])
    p = [list(map(lambda x: int(x), read_line().split())) for _ in range(m)]
    max_possible = [max([p[i][x] for i in range(m)]) for x in range(n)]
    best_result = min(max_possible)
    if m < n:
        print(best_result)
    else:
        best_reduction = max([get_max_2_value(p[i]) for i in range(m)])
        print(min([best_reduction, best_result]))