Round G 2021 - Kick Start 2021 Banana Bunch

help
, ,
1

Question: Barbara goes to Alan’s banana farm, where the NN banana trees are organized in one long line represented by an array BB. The tree at position ii has BiBi banana bunches. Each tree has the same cost. Once Barbara buys a tree, she gets all the banana bunches on that tree.
Alan has a special rule: because he does not want too many gaps in his line, he allows Barbara to buy at most 22 contiguous sections of his banana tree line.

Barbara wants to buy some number of trees such that the total number of banana bunches on these purchased trees equals the capacity KK of her basket. She wants to do this while spending as little money as possible. How many trees should she buy?

My approach: I have used a stateful 0-1 knapsack approach to solve this, I used the recursive approach because it is easier to think it in that way, and also commented code appropriately. The code is passing sample test cases but failing main test cases. Please help, thanks.
The main problem is to understand why the recursive solution is failing, making it dp, using memoizing can be done when the above is clear.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//pair<isValid, numTrees>
pair<int, ll> dpHelper(ll i, vector<int> &b, int currBananaCapacity, int remainingSections)
{
    // if (currBananaCapacity == 2)
    // cout << currBananaCapacity << ":i" << i << " \n";
    if (currBananaCapacity == 0)
    { // got the bananas exact quantity, cant choose any more, Valid = True

        return {1, 0};
    }
    if (i == -1)
    { //invalid index
        return {0, 0};
    }

    //choice diagram
    if (remainingSections == 2)
    {
        if (currBananaCapacity < b[i])
        { //cant choose banana
            auto x = dpHelper(i - 1, b, currBananaCapacity, 2);
            int valid = x.first;
            ll numTrees = x.second;
            // return {valid, numTrees};
            if (valid == 1)
            {
                return {1, numTrees};
            }
            else
            {
                return {0, 0};
            }
        }
        else
        {
            // currBananaCapacity >= b[i]
            // can choose banana

            // dont choose banana
            auto x1 = dpHelper(i - 1, b, currBananaCapacity, 2);
            int valid1 = x1.first;
            ll numTrees1 = x1.second;

            // choose banana
            auto x2 = dpHelper(i - 1, b, currBananaCapacity - b[i], 1);
            int valid2 = x2.first;
            ll numTrees2 = x2.second;
            numTrees2++; // since this tree is chosen

            if (valid1 == 1 && valid2 == 1)
            {
                return {1, min(numTrees1, numTrees2)};
            }
            else if (valid1 == 1 && valid2 == 0)
            {
                return {1, numTrees1};
            }
            else if (valid1 == 0 && valid2 == 1)
            {
                return {1, numTrees2};
            }
            else if (valid1 == 0 && valid2 == 0)
            {
                return {0, 0};
            }
        }
    }
    else if (remainingSections == 1)
    {
        if (currBananaCapacity < b[i])
        { //cant choose banana
            auto x = dpHelper(i - 1, b, currBananaCapacity, 0);
            int valid = x.first;
            ll numTrees = x.second;
            if (valid == 1)
            {
                return {1, numTrees};
            }
            else
            {
                return {0, 0};
            }
        }
        else
        {
            // currBananaCapacity >= b[i]
            // can choose banana

            // dont choose banana
            auto x1 = dpHelper(i - 1, b, currBananaCapacity, 0);
            int valid1 = x1.first;
            ll numTrees1 = x1.second;

            // choose banana
            auto x2 = dpHelper(i - 1, b, currBananaCapacity - b[i], 1);
            int valid2 = x2.first;
            ll numTrees2 = x2.second;
            numTrees2++;

            if (valid1 == 1 && valid2 == 1)
            {
                return {1, min(numTrees1, numTrees2)};
            }
            else if (valid1 == 1 && valid2 == 0)
            {
                return {1, numTrees1};
            }
            else if (valid1 == 0 && valid2 == 1)
            {
                return {1, numTrees2};
            }
            else
            {
                return {0, 0};
            }
        }
    }
    else
    {
        // remainingSections == 0 // have to choose banana or die

        if (currBananaCapacity < b[i])
        { //cant choose banana // return invalid
            return {0, 0};
        }
        else
        { // currBananaCapacity >= b[i]
            auto x = dpHelper(i - 1, b, currBananaCapacity - b[i], 0);
            int valid = x.first;
            ll numTrees = x.second + 1;
            // return {valid, numTrees};
            if (valid == 1)
            {
                return {1, numTrees};
            }
            else
            {
                return {0, 0};
            }
        }
    }
}
ll solve(ll n, ll k, vector<int> &b)
{
    auto x = dpHelper(n - 1, b, k, 2);
    if (x.first == 0)
        return -1;
    else
        return x.second;
}

int main()
{

    // #ifndef ONLINE_JUDGE

    //     // For getting input from input.txt file
    //     freopen("input.txt", "r", stdin);

    //     // Printing the Output to output.txt file
    //     freopen("output.txt", "w", stdout);

    // #endif

    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        ll n, k;
        cin >> n >> k;
        vector<int> b(n);
        for (ll i = 0; i < n; i++)
        {
            int x;
            cin >> x;
            b[i] = x;
        }

        printf("Case #%d: %lld\n", i, solve(n, k, b));
    }
}
2

OK turns out I completely forgot the midGap situation, Here is the working code, still working on memoizing it though.
Using enums for such states is so better.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

enum state
{
    nothing,
    oneThing,
    midgap,
    twothing
};

//pair<isValid, numTrees>
pair<int, ll> dpHelper(ll i, vector<int> &b, int currBananaCapacity, enum state st)
{
    // if (currBananaCapacity == 2)
    // cout << currBananaCapacity << ":i" << i << " \n";
    // cout << remainingSections << ":i" << i << " \n";
    if (currBananaCapacity == 0)
    { // got the bananas exact quantity, cant choose any more, Valid = True

        // cout << endl;
        // cout << endl;
        return {1, 0};
    }
    if (i < 0 || currBananaCapacity < 0)
    { //invalid index || invalid capacity
        // cout << endl;
        return {0, 0};
    }

    //choice diagram
    if (st == nothing)
    {
        if (currBananaCapacity < b[i])
        { //cant choose banana
            auto x = dpHelper(i - 1, b, currBananaCapacity, nothing);
            int valid = x.first;
            ll numTrees = x.second;
            // return {valid, numTrees};
            if (valid == 1)
            {
                return {1, numTrees};
            }
            else
            {
                return {0, 0};
            }
        }
        else
        {
            // currBananaCapacity >= b[i]
            // can choose banana

            // dont choose banana
            auto x1 = dpHelper(i - 1, b, currBananaCapacity, nothing);
            int valid1 = x1.first;
            ll numTrees1 = x1.second;

            // choose banana
            auto x2 = dpHelper(i - 1, b, currBananaCapacity - b[i], oneThing);
            int valid2 = x2.first;
            ll numTrees2 = x2.second;
            numTrees2++; // since this tree is chosen

            if (valid1 == 1 && valid2 == 1)
            {
                return {1, min(numTrees1, numTrees2)};
            }
            else if (valid1 == 1 && valid2 == 0)
            {
                return {1, numTrees1};
            }
            else if (valid1 == 0 && valid2 == 1)
            {
                return {1, numTrees2};
            }
            else if (valid1 == 0 && valid2 == 0)
            {
                return {0, 0};
            }
        }
    }
    else if (st == oneThing)
    {
        if (currBananaCapacity < b[i])
        { //cant choose banana
            auto x = dpHelper(i - 1, b, currBananaCapacity, midgap);
            int valid = x.first;
            ll numTrees = x.second;
            if (valid == 1)
            {
                return {1, numTrees};
            }
            else
            {
                return {0, 0};
            }
        }
        else
        {
            // currBananaCapacity >= b[i]
            // can choose banana

            // dont choose banana
            auto x1 = dpHelper(i - 1, b, currBananaCapacity, midgap);
            int valid1 = x1.first;
            ll numTrees1 = x1.second;

            // choose banana
            auto x2 = dpHelper(i - 1, b, currBananaCapacity - b[i], oneThing);
            int valid2 = x2.first;
            ll numTrees2 = x2.second;
            numTrees2++;

            if (valid1 == 1 && valid2 == 1)
            {
                return {1, min(numTrees1, numTrees2)};
            }
            else if (valid1 == 1 && valid2 == 0)
            {
                return {1, numTrees1};
            }
            else if (valid1 == 0 && valid2 == 1)
            {
                return {1, numTrees2};
            }
            else
            {
                return {0, 0};
            }
        }
    }
    else if (st == midgap)
    {
        if (currBananaCapacity < b[i])
        { //cant choose banana
            auto x = dpHelper(i - 1, b, currBananaCapacity, midgap);
            int valid = x.first;
            ll numTrees = x.second;
            if (valid == 1)
            {
                return {1, numTrees};
            }
            else
            {
                return {0, 0};
            }
        }
        else
        {
            // currBananaCapacity >= b[i]
            // can choose banana

            // dont choose banana
            auto x1 = dpHelper(i - 1, b, currBananaCapacity, midgap);
            int valid1 = x1.first;
            ll numTrees1 = x1.second;

            // choose banana
            auto x2 = dpHelper(i - 1, b, currBananaCapacity - b[i], twothing);
            int valid2 = x2.first;
            ll numTrees2 = x2.second;
            numTrees2++;

            if (valid1 == 1 && valid2 == 1)
            {
                return {1, min(numTrees1, numTrees2)};
            }
            else if (valid1 == 1 && valid2 == 0)
            {
                return {1, numTrees1};
            }
            else if (valid1 == 0 && valid2 == 1)
            {
                return {1, numTrees2};
            }
            else
            {
                return {0, 0};
            }
        }
    }
    else if (st == twothing)
    {
        // remainingSections == 0 // have to choose banana or die

        if (currBananaCapacity < b[i])
        { //cant choose banana // return invalid
            return {0, 0};
        }
        else
        { // currBananaCapacity >= b[i]
            auto x = dpHelper(i - 1, b, currBananaCapacity - b[i], twothing);
            int valid = x.first;
            ll numTrees = x.second + 1;
            // return {valid, numTrees};
            if (valid == 1)
            {
                return {1, numTrees};
            }
            else
            {
                return {0, 0};
            }
        }
    }
}
ll solve(ll n, ll k, vector<int> &b)
{
    auto x = dpHelper(n - 1, b, k, nothing);
    if (x.first == 0)
        return -1;
    else
        return x.second;
}

int main()
{

// #ifndef ONLINE_JUDGE

//     // For getting input from input.txt file
//     freopen("input.txt", "r", stdin);

//     // Printing the Output to output.txt file
//     freopen("output.txt", "w", stdout);

// #endif

    int t;
    std::cin >> t;
    for (int i = 1; i <= t; i++)
    {
        ll n, k;
        std::cin >> n >> k;
        vector<int> b(n);
        for (ll i = 0; i < n; i++)
        {
            int x;
            std::cin >> x;
            b[i] = x;
        }

        printf("Case #%d: %lld\n", i, solve(n, k, b));
    }
}