Guard Mark

Explicación

Notemos que como no siempre es óptimo dejar a la vaca más fuerte/pesada en el fondo de la pila, tenemos que recorrer cada subconjunto posible, lo cual es factible con $N \leq 20$ .

Aquí hay un ejemplo de un contraejemplo:

(En este caso, es más óptimo tomar las últimas dos vacas.)

Casi siempre que las cotas son ~ $20$ , sugiere recorrer subconjuntos.

Veamos la información que necesitamos para implementarlo.

Estados

Usamos una máscara de bits ( $\texttt{mask}$ ) para llevar la cuenta de las vacas que estamos usando.

Para comprobar si ya superamos la altura de Mark y, de ser así, devolver el resultado, también debemos llevar la cuenta de la altura actual y el mejor factor de seguridad que podemos obtener.

$\texttt{dp}[\texttt{mask}] =\{$ altura actual, máximo factor de seguridad alcanzable $\}$

Caso base

Sin vacas, el factor de seguridad será infinito y la altura será cero.

Transiciones

\texttt{dp}[\texttt{mask}] = \max_{j \in mask}(\texttt{dp}[\texttt{mask}],\hspace{0.1cm}\min(\texttt{dp}[\texttt{mask} \char`\\ j] - \texttt{weight}_j,\hspace{0.1cm}\texttt{strength}_j))

Donde $j$ es el índice de la $j$ -ésima vaca y $\texttt{weight}_j,\hspace{0.1cm}\texttt{strength}_j$ representan el peso y la fuerza de la vaca $j$ respectivamente.

Esto obtiene el máximo factor de seguridad si ponemos a la vaca $j$ en la cima de nuestra pila para cada $j$ . Tenemos que tener en cuenta $\texttt{strength}_j$ y $\texttt{dp}[\texttt{mask} \char`\\ j] - \texttt{weight}_j$ en el caso de que alguna de las vacas de abajo no pueda sostener tanto peso como la vaca $j$ , o viceversa.

Implementación

Complejidad temporal: $\mathcal{O}(2^N \cdot N)$

C++Java


#include <bits/stdc++.h>
using namespace std;
 
struct Cow {
	int height;
	int weight;
	int strength;
};
 
int main() {
	freopen("guard.in", "r", stdin);
	freopen("guard.out", "w", stdout);
 
	int n;
	int h;
	cin >> n >> h;
 
	vector<Cow> cows(n);
	for (int i = 0; i < n; i++) {
		cin >> cows[i].height >> cows[i].weight >> cows[i].strength;
	}
 
	// dp[i] = {altura acumulada, factor de seguridad}
	vector<pair<int, int>> dp(1 << n);
 
	// inicialmente no tenemos altura, y podemos agregar peso infinito
	dp[0] = {0, INT32_MAX};
 
	for (int i = 1; i < (1 << n); i++) {
		dp[i] = {0, -1};
 
		for (int j = 0; j < n; j++) {
			// si el j-ésimo bit está encendido
			if (i & (1 << j)) {
				// actualizar nuestra altura
				dp[i].first += cows[j].height;
 
				int prev = i ^ (1 << j);
				/*
				 * máximo factor de seguridad si ponemos a la vaca j
				 * en la cima de nuestra pila (también tener en cuenta la fuerza de j)
				 */
				dp[i].second = max(dp[i].second, min(dp[prev].second - cows[j].weight,
				                                     cows[j].strength));
			}
		}
	}
 
	int max_safety = -1;
	for (int i = 1; i < (1 << n); i++) {
		if (dp[i].first >= h) { max_safety = max(dp[i].second, max_safety); }
	}
 
	// no existe un arreglo lo suficientemente alto/estable
	if (max_safety < 0) {
		cout << "Mark is too tall" << endl;
	} else {
		cout << max_safety << endl;
	}
}


import java.io.*;
import java.util.*;
 
public class GuardMark {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("guard");
 
		int N = io.nextInt();
		int H = io.nextInt();
		Cow[] cows = new Cow[N];
		for (int i = 0; i < N; i++) {
			int h = io.nextInt();
			int w = io.nextInt();
			int s = io.nextInt();
			cows[i] = new Cow(h, w, s);
		}
 
		/*
		 * dp[subset][0] = Altura del subconjunto de vacas
		 * dp[subset][1] = Factor de seguridad del subconjunto de vacas
		 */
		int[][] dp = new int[1 << N][2];
 
		// Inicialmente, la altura es 0 y se puede apilar altura infinita.
		dp[0][0] = 0;
		dp[0][1] = Integer.MAX_VALUE;
 
		// Recorrer cada subconjunto de vacas.
		for (int i = 1; i < (1 << N); i++) {
			// Condiciones iniciales.
			dp[i][0] = 0;
			dp[i][1] = -1;
			for (int j = 0; j < N; j++) {
				if ((i & (1 << j)) == 0) { continue; }
				// Agregar la altura de la vaca a la altura total del subconjunto.
				dp[i][0] += cows[j].height;
				// Subconjunto anterior antes de que se activara este bit.
				int prev = i ^ (1 << j);
				/*
				 * Máxima seguridad del subconjunto dado que j es la vaca más alta.
				 * Revisar el factor de seguridad anterior - el peso de j,
				 * y revisar la propia fuerza de j.
				 */
				dp[i][1] = Math.max(
				    dp[i][1], Math.min(dp[prev][1] - cows[j].weight, cows[j].strength));
			}
		}
 
		int maxSafety = -1;
		for (int i = 1; i < (1 << N); i++) {
			if (dp[i][0] >= H) {
				// Cumple las condiciones de altura.
				maxSafety = Math.max(dp[i][1], maxSafety);
			}
		}
 
		// No se puede encontrar un orden válido.
		if (maxSafety == -1) {
			io.println("Mark is too tall");
		} else {
			io.println(maxSafety);
		}
		io.close();
	}
 
	static class Cow {
		public int height;
		public int weight;
		public int strength;
 
		public Cow(int height, int weight, int strength) {
			this.height = height;
			this.weight = weight;
			this.strength = strength;
		}
	}
 
	// CodeSnip{Kattio}
}