New Years Resolution

Review

Summary

If there was only one macro-nutrient this would exactly be the classic "Subset Sums" problem: Given a list of integers $A_1, A_2, ..., A_N$ and a goal value $V$, find a subset of the integers that add to exactly $V$.

There are three nutrients, so this is a bit harder, but the problem can be solved in a similar way. (If you have never heard of the Subset Sums problem, I encourage the reader to Google it to learn more!)

Subsets Sums is $NP-HARD$, which means there is no known polynomial time solution to this problem. It can be solved by a variety of methods, such as Dynamic Programming. In this case, $N$, the number of items is very small ($N \leq 20$), so we can actually "enumerate" all possible choices of subset. With a little bit of counting we can prove that, for any $N$-element set, there are $2^N$ possible subsets. In this case, $N = 20$ so $2^N = 1,048,576$. There are around a million choices. If we "try" each possible choice (i.e.: by brute force), and see what they add up to (in terms of total amount of each macro-nutrient), then we can see if there is a configuration that works.

To implement this, you can try a recursive function with "Backtracking" or use "Bitmasks".

1. $|N|$ is small, at most $20$. This means a brute force (O($2^N$)) solution would pass.

2. With $N$ items, there are exactly $2^N$ ways to pick a subset of them.

3. If we were to pick a subset, we can quickly check if it works.

4. Immediately upon seeing this problem, advanced coders will use the constraints to their advantage. Since $N$ is small, even a highly inefficient (exponential) solution would pass. This guided our ideas towards a brute-force solution using "subsets".

5. Instead of asking "How do we find a set of food that works", we can ask a form of reverse question: "If I have a set of food, can I quickly check that it works?" In this case, the answer is YES. If I know what food I was going to eat, I could check the total amount of protein, carbs, and fat, and check if these are equal to my targets. Because of this fact, it was easy to check every possibility to find our answer.

• "Keep it Simple Stupid" (KISS) and "Exploit the Constraints". These "catch-phrases" can help minimize your risk of errors, save you time, and increase your chance of getting AC/Accepted on the first try.

• Brute Force / Exhaustive Search / Subsets and Bitmasks

• Dynamic Programming / DP / Subset Sums

• DP / Bitmask DP

• NP Hard Problems

• FB Hacker Cup 2015 Qualification Round, Problem A - Cooking the Books Both these problems have an "easy" brute force solution, and a "harder" solution that takes more work and thought, but is probably more efficient. Try to compare and contrast these.

• Prove that an $N$-element set has exactly $2^N$ possible subsets (including the empty set). A combinatorics exercise for beginners. For example, the set $\{a,b\}$ has 4 subsets: $\{a\}, \{b\}, \{a,b\}, \{\}$ (where the last one is the empty set). It's non-trivial to prove if you haven't seen it before, and if you haven't been exposed to counting / combinatorics.

• What if the constraints were larger? What if $N \approx 40$ or $N \approx 100$ or $N \approx 1000$ (but all other constraints were kept the same)? Now, the naive brute force won't really work ($2^{40}$ is colossal). Are these even solvable anymore? How would you solve them? Have you heard of Subset Sums? Can you generalize the Subset Sums DP approach to work here? Can you break apart the problem and consider $P$, $C$, and $F$ (the different macro-nutrients) separately? How would you recombine the answers? I'm not sure how to solve this right away, but these are just ideas. Good luck!!!