Shopping Offers

Solution Approach

State-Space DP

Since there are at most 5 products each with quantity at most 5, the state space is at most $6^5 = 7{,}776$ states. Define: \[ \mathrm{dp}[q_1][q_2][q_3][q_4][q_5] = \text{minimum cost to buy exactly } (q_1, q_2, \ldots, q_5) \text{ items.} \]

Base Case

$\mathrm{dp}[0][0][0][0][0] = 0$.

Transitions

For each state $(q_1, \ldots, q_b)$ with at least one $q_i > 0$:

1. \textbf{Buy one unit of product $i$:} If $q_i > 0$, transition from $(q_1, \ldots, q_i - 1, \ldots, q_b)$ with cost increase $c_i$.

2. \textbf{Use offer $j$:} If $q_i \ge o_{j,i}$ for all $i$, transition from $(q_1 - o_{j,1}, \ldots, q_b - o_{j,b})$ with cost increase equal to the offer price.

3. We compute the DP bottom-up, iterating through all quantity tuples in lexicographic order. Each state takes its value as the minimum over all valid predecessors.

C++ Solution

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int b; // number of products (1..5)
int price[6]; // unit price for each product (1-indexed)
int want[6];  // desired quantity for each product
int code[6];  // product code mapping

int s; // number of offers
struct Offer {
    int qty[6]; // quantity of each product in offer (1-indexed)
    int cost;
};
Offer offers[100];

int dp[6][6][6][6][6];

int main() {
    scanf("%d", &s);

    // Read offers (product codes used directly for now)
    for (int i = 0; i < s; i++) {
        int nk;
        scanf("%d", &nk);
        memset(offers[i].qty, 0, sizeof(offers[i].qty));
        for (int j = 0; j < nk; j++) {
            int c, q;
            scanf("%d %d", &c, &q);
            offers[i].qty[c] = q; // store by product code
        }
        scanf("%d", &offers[i].cost);
    }

    scanf("%d", &b);
    for (int i = 1; i <= b; i++)
        scanf("%d %d %d", &code[i], &want[i], &price[i]);

    // Remap offer quantities from product codes to indices 1..b
    Offer mapped[100];
    for (int i = 0; i < s; i++) {
        mapped[i].cost = offers[i].cost;
        memset(mapped[i].qty, 0, sizeof(mapped[i].qty));
        for (int j = 1; j <= b; j++)
            mapped[i].qty[j] = offers[i].qty[code[j]];
    }

    // Initialize DP to infinity
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0][0][0] = 0;

    // Set up quantity bounds
    int w[6];
    for (int i = 1; i <= 5; i++)
        w[i] = (i <= b) ? want[i] : 0;

    // Bottom-up DP over all quantity tuples
    for (int q1 = 0; q1 <= w[1]; q1++)
    for (int q2 = 0; q2 <= w[2]; q2++)
    for (int q3 = 0; q3 <= w[3]; q3++)
    for (int q4 = 0; q4 <= w[4]; q4++)
    for (int q5 = 0; q5 <= w[5]; q5++) {
        if (q1 == 0 && q2 == 0 && q3 == 0 && q4 == 0 && q5 == 0)
            continue; // base case already set

        int best = 0x3f3f3f3f;
        int qq[6] = {0, q1, q2, q3, q4, q5};

        // Option 1: buy a single unit of product j
        for (int j = 1; j <= b; j++) {
            if (qq[j] > 0) {
                int prev[6] = {0, q1, q2, q3, q4, q5};
                prev[j]--;
                int val = dp[prev[1]][prev[2]][prev[3]][prev[4]][prev[5]];
                if (val < 0x3f3f3f3f)
                    best = min(best, val + price[j]);
            }
        }

        // Option 2: use an offer
        for (int o = 0; o < s; o++) {
            bool ok = true;
            int prev[6] = {0, q1, q2, q3, q4, q5};
            for (int j = 1; j <= b; j++) {
                prev[j] -= mapped[o].qty[j];
                if (prev[j] < 0) { ok = false; break; }
            }
            if (ok) {
                int val = dp[prev[1]][prev[2]][prev[3]][prev[4]][prev[5]];
                if (val < 0x3f3f3f3f)
                    best = min(best, val + mapped[o].cost);
            }
        }

        dp[q1][q2][q3][q4][q5] = best;
    }

    printf("%d\n", dp[w[1]][w[2]][w[3]][w[4]][w[5]]);
    return 0;
}

Correctness

The DP processes states in non-decreasing order of the quantity tuple (lexicographically). Every predecessor state $(q_1, \ldots, q_i - 1, \ldots, q_b)$ or $(q_1 - o_{j,1}, \ldots, q_b - o_{j,b})$ is componentwise $\le$ the current state, so it has already been computed when needed. The base case $\mathrm{dp}[\mathbf{0}] = 0$ is correct, and each transition adds exactly the cost of one purchase, so by induction the DP computes the minimum cost for every reachable state.

Complexity Analysis

• Time complexity: $O(Q^b \cdot (b + s))$, where $Q = \max(q_i) + 1 \le 6$, $b \le 5$, and $s \le 99$. With these bounds: $6^5 \times 104 \approx 810{,}000$ operations.

• Space complexity: $O(Q^5) = O(7{,}776)$ for the DP table.