Lizard Era Beginning

Pista 1

Elegir dos compañeros por tarea equivale a excluir un compañero por tarea.

Pista 2

Digamos que tenemos un par $(a, b)$ y $(c, d)$ . Si queremos que $a + c$ sea igual a $b + d$ , entonces $a - b$ debe ser igual a $d - c$ . ¿Cómo nos ayuda esto a hacer meet-in-the-middle sobre el arreglo?

Explicación

Con la información de las pistas, podemos hacer meet-in-the-middle y considerar todas las formas posibles de elegir compañeros a excluir en nuestros subarreglos izquierdo y derecho.

Dada la información de la pista 2, podemos unir de forma eficiente los resultados de los lados izquierdo y derecho. En una respuesta válida, las diferencias adyacentes de actitudes del lado izquierdo deben ser las opuestas de las diferencias adyacentes del lado derecho. Con esta observación, podemos hallar el mejor emparejamiento para cada resultado posible del lado izquierdo en $\mathcal{O}(\log{N})$ .

Implementación

Complejidad temporal: $\mathcal{O}(3^{\left \lfloor{\frac{N}{2}}\right \rfloor}\log\left({3^{\left \lceil{\frac{N}{2}}\right \rceil}}\right))$

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	vector<array<int, 3>> tasks(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) { cin >> tasks[i][j]; }
	}
 
	/** calcula todas las actitudes finales posibles en [l, r) */
	const auto calc_subarray = [&](int l, int r) -> vector<array<int, 4>> {
		array<int, 3> attitude = {0, 0, 0};
		for (int i = l; i < r; i++) {
			for (int j = 0; j < 3; j++) { attitude[j] += tasks[i][j]; }
		}
 
		// enmascaramos en base 3
		int len = r - l;
		int max_mask = 1;
		for (int i = 0; i < len; i++) { max_mask *= 3; }
 
		// si nuestras actitudes finales para una máscara son (a, b, c), entonces
		// res[i] = {b - a, c - b, a, mask}
		vector<array<int, 4>> res(max_mask);
		for (int i = 0; i < max_mask; i++) {
			int cur_mask = i;
			array<int, 3> subtracted = {0, 0, 0};
 
			for (int j = 0; j < len; j++) {
				subtracted[cur_mask % 3] += tasks[l + j][cur_mask % 3];
				cur_mask /= 3;
			}
 
			for (int j = 0; j < 3; j++) { subtracted[j] = attitude[j] - subtracted[j]; }
 
			res[i] = {subtracted[1] - subtracted[0], subtracted[2] - subtracted[1],
			          subtracted[0], i};
		}
		return res;
	};
 
	/** @return actitud final hacia el héroe, o -INF si no son todas
	 * iguales */
	const auto calc_attitude = [](const array<int, 4> &x,
	                              const array<int, 4> &y) -> int {
		if (x[0] != -y[0] || x[1] != -y[1]) { return INT32_MIN; }
		return x[2] + y[2];
	};
 
	vector<array<int, 4>> left = calc_subarray(0, n / 2);
	vector<array<int, 4>> right = calc_subarray(n / 2, n);
	sort(begin(right), end(right));
 
	int mask1 = -1;
	int mask2 = -1;
	int res = INT32_MIN;
	for (array<int, 4> &i : left) {
		const auto [diff_1, diff_2, fi, mask] = i;
 
		// hallar el "complemento" de este resultado
		auto it = lower_bound(begin(right), end(right),
		                      array<int, 4>{-diff_1, -diff_2, INT32_MAX, 0});
		if (it == begin(right)) { continue; }
		it = prev(it);
 
		int cand = calc_attitude(i, *it);
		if (res < cand) {
			res = cand;
			mask1 = mask;
			mask2 = (*it)[3];
		}
	}
 
	if (res == INT32_MIN) {
		cout << "Impossible" << "\n";
		return 0;
	}
 
	// ignored[i] = string a imprimir si ignoramos al compañero i
	array<string, 3> ignored = {"MW", "LW", "LM"};
	for (int i = 0; i < n / 2; i++) {
		cout << ignored[mask1 % 3] << "\n";
		mask1 /= 3;
	}
	for (int i = 0; i < (n + 1) / 2; i++) {
		cout << ignored[mask2 % 3] << "\n";
		mask2 /= 3;
	}
}