Editorial for ICPC NAQ 2016 H - Nine Packs

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Considering only hotdog packs $h_1, \dots, h_i$ $h_{1}, \dots, h_{i}$ , let $\operatorname{opt}_h(i, k)$ ${opt}_{h} (i, k)$ denote the minimum number of packs you need to buy to have exactly $k$ $k$ hotdogs, or $+\infty$ $+ \infty$ if impossible.
Similarly, let $\operatorname{opt}_b(i, k)$ ${opt}_{b} (i, k)$ denote the corresponding value for the packs of buns $b_1, \dots, b_i$ $b_{1}, \dots, b_{i}$ .
If $C = \min\left(\sum_{i=1}^H h_i, \sum_{i=1}^B b_i\right)$ $C = min (\sum_{i = 1}^{H} h_{i}, \sum_{i = 1}^{B} b_{i})$ , the answer is: $\displaystyle \min_{1 \le k \le C} \operatorname{opt}_b(B, k) + \operatorname{opt}_h(H, k)$ $min_{1 \leq k \leq C} {opt}_{b} (B, k) + {opt}_{h} (H, k)$
Note that $C \le 100 \cdot 1\,000 = 10^5$ $C \leq 100 \cdot 1 000 = 10^{5}$ .
Computing $\operatorname{opt}_h(i, k)$ ${opt}_{h} (i, k)$ is an instance of the Knapsack problem (or a variant thereof), and can be solved in a similar manner as follows.
Based on whether we buy the $i^\text{th}$ $i^{th}$ pack of hotdogs ( $h_i$ $h_{i}$ ) or not, we get the following recurrence: $\displaystyle \operatorname{opt}_h(i, k) = \min(1 + \operatorname{opt}_h(i-1, k-h_i), \operatorname{opt}_h(i-1, k))$ ${opt}_{h} (i, k) = min (1 + {opt}_{h} (i - 1, k - h_{i}), {opt}_{h} (i - 1, k))$
We also have the base cases: $\displaystyle \operatorname{opt}_h(i, k) = \begin{cases}0 & \text{if }k = 0 \\ +\infty & \text{if }i = 0\text{ or }k < 0\end{cases}$ ${opt}_{h} (i, k) = {\begin{cases} 0 & if k = 0 \\ + \infty & if i = 0 or k < 0 \end{cases}$
We have a similar recursion for $\operatorname{opt}_b(i, k)$ ${opt}_{b} (i, k)$ .
Finally, $\operatorname{opt}_h(H, k)$ ${opt}_{h} (H, k)$ and $\operatorname{opt}_b(B, k)$ ${opt}_{b} (B, k)$ can be computed for all $1 \le k \le C$ $1 \leq k \leq C$ in $\mathcal O((B+H)C)$ $O ((B + H) C)$ using dynamic programming (or memoization).

Comments

There are no comments at the moment.