Official Analysis

Explanation

Note that since it might not always be optimal to keep the strongest/heaviest cow at the bottom of the stack, we have to go through every single possible subset, which is feasible with $N \leq 20$.

Here's an example of a counter case:

4 6
1 1000 4
1 1 5
3 2 3
3 3 3

(In this case, it's more optimal to take the last two cows instead!)

Almost every time the bounds are ~$20$, it suggests looping over subsets.

Let's go through the information we need to implement it!

States

Let's use a bitmask ($\texttt{mask}$) to keep track of the cows we're using.

To check if we've surpassed Mark's height already and if so, return the result, we should also keep track of the current height and the best safety factor we can get.

$\texttt{dp}[\texttt{mask}] =\{$current height, maximum safety factor achievable$\}$

Base Case

With no cows, the safety factor will be infinite and the height will be zero.

Transitions

$\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))$

Such that $j$ is the index of the $j$th cow and $\texttt{weight}_j,\hspace{0.1cm}\texttt{strength}_j$ represents the weight and strength of cow $j$ respectively.

This gets the maximum safety factor if we put cow $j$ at the top of our stack for every $j$. We have to take into account $\texttt{strength}_j$ and $\texttt{dp}[\texttt{mask} \char`\\ j] - \texttt{weight}_j$ in the case that either one of the cows below can't sustain as much weight as cow $j$ can, or vice-versa.

Implementation

Time Complexity: $\mathcal{O}(2^N \cdot N)$

Copy
#include <bits/stdc++.h>
using namespace std;

struct Cow {
	int height;
	int weight;
	int strength;
};

int main() {

Copy
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];