Game With Triangles

El área de un triángulo es $\frac{1}{2}bh$, donde $b$ es la longitud de la base y $h$ es la altura del triángulo. Nótese que si ponemos la base como el lado con dos puntos, $h$ es siempre $2$. ¿Qué significa esto?

Si elegimos dos puntos $x$ e $y$ en un lado, entonces el área del triángulo resultante es simplemente $|x - y|$. ¡La ubicación del tercer punto en el otro lado no importa!

Intentemos diseñar una solución $\mathcal{O}(n^2)$ al problema con la información de la primera pista.

Explicación

Como se mencionó en la pista 1, el área de un triángulo solo depende de la longitud de su base, que es el lado donde están dos de nuestros puntos. Así, podemos reducir el problema a elegir $x$ pares de puntos en el arreglo $a$, e $y$ pares de puntos en el arreglo $b$.

Digamos que queremos hallar la mejor forma de elegir $x$ pares de puntos en el arreglo $a$. ¿Cómo podemos maximizar nuestra área? La forma más directa sería emparejar los $x$ valores más pequeños con los $x$ más grandes en cualquier disposición de emparejamiento. Podemos calcular el área total usando sumas de prefijos de esta forma.

Esto nos da nuestro algoritmo $\mathcal{O}(n^2)$: para cada valor de $k$, iteramos sobre nuestro valor de $x$, con $y = k - x$. Con la estrategia voraz de arriba, podemos calcular el mejor resultado para cada par $(x, y)$ en tiempo $\mathcal{O}(1)$.

Sea $x$ el número de pares que hacemos del arreglo $a$, $f(x)$ el área total máxima de triángulos del arreglo $a$, y $g(x)$ el área total máxima de triángulos del arreglo $b$. Entonces, nuestra respuesta es el valor máximo de $f(x) + g(x)$ entre todos los valores válidos de $x$.

Podemos hacer las siguientes afirmaciones:

1. $f(x)$ es estrictamente creciente, mientras que $g(x)$ es estrictamente decreciente.
2. $f(x)$ y $g(x)$ tienen diferencias consecutivas no crecientes, lo que las hace convexas.
3. La función $h(x) = f(x) + g(x)$ es convexa.

¡Intentemos entender por qué cada una de estas afirmaciones es cierta!

Ahora, como las funciones convexas son unimodales, nuestro problema se reduce a maximizar una función unimodal. Esto se puede manejar con búsqueda ternaria o binaria. Hay que restringir bien el espacio de búsqueda, ya que solo algunos valores de $x$ son válidos.

Implementación

Complejidad temporal: $\mathcal{O}(N\log{N} + M\log{M})$

#include <bits/stdc++.h>
 
using ll = long long;
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, m;
		std::cin >> n >> m;
		std::vector<int> a(n), b(m);
		for (int &i : a) { std::cin >> i; }
		for (int &i : b) { std::cin >> i; }
 
		// calculate prefix sums for array a
		std::sort(std::begin(a), std::end(a));
		std::vector<ll> pf_a(n);
		pf_a[0] = a[0];
		for (int i = 1; i < n; i++) { pf_a[i] = a[i] + pf_a[i - 1]; }
 
		// calculate prefix sums for array b
		std::sort(std::begin(b), std::end(b));
		std::vector<ll> pf_b(m);
		pf_b[0] = b[0];
		for (int i = 1; i < m; i++) { pf_b[i] = b[i] + pf_b[i - 1]; }
 
		/** @return best way to choose num pairs in array pf */
		const auto get_best = [&](const std::vector<ll> &pf, int num) -> ll {
			const int sz = pf.size();
			return (pf[sz - 1] - pf[sz - 1 - num]) - (num == 0 ? 0 : pf[num - 1]);
		};
 
		// k_max is bounded by the number of points,
		// and the number of points on each side
		const int k_max = std::min({n, m, (n + m) / 3});
		std::cout << k_max << '\n';
 
		for (int i = 1; i <= k_max; i++) {
			/** @return best result if we pick j pairs from array a */
			const auto get = [&](int j) -> ll {
				return get_best(pf_a, j) + get_best(pf_b, i - j);
			};
 
			/**
			 * We use binary search to find the maximum of our function. (See module)
			 * In this case, because our function strictly increases, reaches its
			 * maximum, and becomes strictly decreasing, we find the first point where
			 * the function beceomes strictly decreasing.
			 */
			int lo = std::max(0, 2 * i - m);
			int hi = std::min(i, n - i);
			while (lo < hi) {
				int mid = (lo + hi) / 2;
				if (get(mid) > get(mid + 1)) {
					hi = mid;
				} else {
					lo = mid + 1;
				}
			}
 
			std::cout << get(lo) << " \n"[i == k_max];
		}
	}
}