Minimax Problem

Explicación

A simple vista, es difícil calcular la respuesta de forma directa sin comparar cada par de arreglos. En lugar de calcularla directamente, podemos intentar hacer búsqueda binaria sobre ella.

Si el valor que estamos comprobando es $x$ , entonces necesitamos un par de arreglos $a$ y $b$ tal que $\text{max}(a[i], b[i]) \geq x$ para todo $i$ válido. Podemos reformular esto como que o bien $a[i] \geq x$ o bien $b[i] \geq x$ . Dado que $m$ es pequeño, esto significa que podemos representar cada arreglo como una máscara de bits, donde el $i$ -ésimo bit de una máscara dada está activado si $a[i] \geq x$ en el arreglo actual.

Como hay como máximo $8$ bits en nuestra máscara, hay hasta $256$ máscaras posibles. Observemos que podemos considerar dos arreglos con la misma máscara como funcionalmente equivalentes. Así, podemos probar por fuerza bruta cada par de máscaras para ver si algún par de arreglos satisface la condición para el valor que estamos comprobando.

Implementación

Complejidad temporal: $\mathcal{O}((NM+4^{M})\log{A})$ , donde $A$ es el valor más grande del arreglo.

C++JavaPython


#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]; }
	}
 
	std::pair<int, int> chosen;
 
	/** @return si una respuesta res funciona, y asigna chosen a un par válido */
	const auto check = [&](int res) -> bool {
		std::vector<int> used(1 << m, -1);
		for (int i = 0; i < n; i++) {
			// representamos cada arreglo i con una máscara de bits
			// la máscara indica si a[i][j] >= res
			int mask = 0;
			for (int j = 0; j < m; j++) { mask |= (vals[i][j] >= res) << j; }
 
			// mapeamos cada máscara a su índice
			used[mask] = i;
		}
 
		// ahora probamos por fuerza bruta cada par de máscaras para ver si hay
		// un par válido que satisfaga la condición
		const int full = (1 << m) - 1;
		for (int i = 0; i < (1 << m); i++) {
			for (int j = 0; j < (1 << m); j++) {
				if ((i | j) == full && used[i] != -1 && used[j] != -1) {
					chosen = {used[i], used[j]};
					return true;
				}
			}
		}
 
		return false;
	};
 
	int lo = 0, hi = 1e9;
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
		check(mid) ? lo = mid : hi = mid - 1;
	}
 
	check(lo);  // asegurarse de que el par elegido es correcto
 
	std::cout << chosen.first + 1 << ' ' << chosen.second + 1 << std::endl;
}


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));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		vals = new int[n][m];
 
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				vals[i][j] = Integer.parseInt(st.nextToken());
			}
		}
 
		int lo = 0, hi = (int)1e9;
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			if (check(mid)) {
				lo = mid;
			} else {
				hi = mid - 1;
			}
		}
 
		check(lo);  // asegurarse de que el par elegido es correcto
		System.out.println((chosenA + 1) + " " + (chosenB + 1));
	}
 
	/** @return si una respuesta res funciona, y asigna los valores elegidos */
	static boolean check(int res) {
		int[] used = new int[1 << m];
		Arrays.fill(used, -1);
 
		for (int i = 0; i < n; i++) {
			// representamos cada arreglo i con una máscara de bits
			// la máscara indica si a[i][j] >= res
			int mask = 0;
			for (int j = 0; j < m; j++) {
				if (vals[i][j] >= res) { mask |= (1 << j); }
			}
 
			// mapeamos cada máscara a su índice
			used[mask] = i;
		}
 
		// ahora probamos por fuerza bruta cada par de máscaras para ver si hay
		// un par válido que satisfaga la condición
		final int full = (1 << m) - 1;
		for (int i = 0; i < (1 << m); i++) {
			for (int j = 0; j < (1 << m); j++) {
				if ((i | j) == full && used[i] != -1 && used[j] != -1) {
					chosenA = used[i];
					chosenB = used[j];
					return true;
				}
			}
		}
 
		return false;
	}
}


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:
	"""
	Comprueba si una respuesta res es alcanzable. Si lo es, asigna
	los valores de la lista chosen a un par válido para nuestra respuesta.
	"""
	used = [-1] * (1 << m)
	for i in range(n):
		# representamos cada arreglo i con una máscara de bits
		# la máscara indica si a[i][j] >= res
		mask = 0
		for j in range(m):
			if vals[i][j] >= res:
				mask |= 1 << j
 
		# mapeamos cada máscara a su índice
		used[mask] = i
 
	# ahora probamos por fuerza bruta cada par de máscaras para ver si hay
	# un par válido que satisfaga la condición
	full = (1 << m) - 1
	for i in range(1 << m):
		for j in range(1 << m):
			if (i | j) == full and used[i] != -1 and used[j] != -1:
				chosen[0], chosen[1] = used[i], used[j]
				return True
 
	return False
 
 
lo = 0
hi = 10**9
while lo < hi:
	mid = (lo + hi + 1) // 2
	if check(mid):
		lo = mid
	else:
		hi = mid - 1
 
check(lo)  # asegurarse de que el par elegido es correcto
print(chosen[0] + 1, chosen[1] + 1)