Solution to NZIC 2015 Round 1 Problem 4 (The Greatest Stew)

gistfile1.md

Abridged problem statement

Given a total cooking time of T and a list of ingredients with properties: t[i], a[i], b[i].
The value of each ingredient put in is (a[i] + (brew time) * b[i]) where brew time = T - (time the ingredient was put in).
Each ingredient put in has to cook for t[i] time before another ingredient can be put in.
Each ingredient can only be used once.
Our task is to output the maximum value that can be obtained.

Algorithm

• Sort ingredients according to b[i].
• initialize f1[i] and f2[i] to 0.
• Do knapsack DP on positive half (f1[j] represents the maximum value with exactly j time left at the end):

// n_positive = number of ingredients that (b[i] >= 0)
for (int i = 0; i < n_positive; i++) {
    for (int j = 0; j <= T; j++) {
        if (j + t[i] <= T) {
            int value = a[i] + (j + t[i]) * b[i];
            f1[j] = max(f1[j], f1[j + t[i]] + value);
        }
    }
}

• Do knapsack DP on negative half with the items backwards (f2[j] represents the maximum value with exactly j time left at the start):

// go though the negative b[i] ingredients backwards
for (int i = n - 1; i >= n_positive; i--) {
    for (int j = 0; j <= T; j++) {
        if (j + t[i] <= T) {
            int value = a[i] + (T - j) * b[i];
            f2[j] = max(f2[j], f2[j + t[i]] + value);
        }
    }
}

• Turn exactly into at least:

for (int i = total_t - 1; i >= 0; i--) f1[i] = max(f1[i], f1[i + 1]);
for (int i = total_t - 1; i >= 0; i--) f2[i] = max(f2[i], f2[i + 1]);

• Output the maximum value of (f1[j] + f2[T - j]) where 0 <= j <= T

<script> if (typeof ga !== 'function') { (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) })(window,document,'script','//www.google-analytics.com/analytics.js','ga'); } ga('create', 'UA-58914980-2', 'auto', {'name' : 'UA_58914980_2'}); ga('UA_58914980_2.send', 'pageview'); </script>

<script type="text/javascript"> /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */ var disqus_shortname = 'llkiwi2006';

/* * * DON'T EDIT BELOW THIS LINE * * */
(function() {
    var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
    dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
    (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();

</script> Please enable JavaScript to view the comments powered by Disqus.