Official Analysis (C++)

Explanation

At a glance, it's difficult to directly compute the answer without comparing each pair of arrays. Instead of directly computing the answer, we can try binary searching on it.

If the value we are checking is $x$, then we need a pair of arrays $a$ and $b$ where $\text{max}(a[i], b[i]) \geq x$ for all valid $i$. We can rephrase this to where either $a[i] \geq x$ or $b[i] \geq x$. Given that $m$ is small, this means that we can represent each array as being a bitmask, where the $i$-th bit in a given bitmask is turned on if $a[i] \geq x$ in our current array.

Because there are only a maximum of $8$ bits in our bitmask, there are up to $256$ possible bitmasks. Note that we can consider two arrays with the same bitmask as being functionally equivalent. Thus, we can brute force every pair of bitmasks to see if any pair of arrays satisfies the condition for the value we are checking for.

Implementation

Time Complexity: $\mathcal{O}((NM+4^{M})\log{A})$, where $A$ is the largest value in the array.

Copy
#include <bits/stdc++.h>

using ll = long long;

int main() {
	int n, m;
	std::cin >> n >> m;
	std::vector vals(n, std::vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { std::cin >> vals[i][j]; }

Copy
import java.io.*;
import java.util.*;

public class Minimax {
	static int n, m;
	static int[][] vals;
	static int chosenA = 0, chosenB = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

Copy
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
vals = [list(map(int, input().split())) for _ in range(n)]
chosen = [0, 0]


def check(res: int) -> bool: