816E

816E.md

Task

Div2E / Div1C https://codeforces.com/contest/816/problem/E

Given an array C, D, X of length n of positive integers and a integer budget B. You need to sum most number of elements in C such as the sum <= B, but you can optionally apply a coupon D[i] when choosing C[i] so it becomes C[i] - D[i] instead. But in order to be able to apply the coupon for an index i, you need to have used coupon on index x[i].

Initial Intuitions

1. An implicit graph can be built from the coupon dependencies.
2. The graph is a tree rooted at 1.

Observation and Reasoning

1. Enumerating the solution can be done exploring the tree.
2. A recursive solution on the children's subtrees can be considered.
3. We should combine different solutions to children's subtree. For example, pick two elements from subtree of child A, then pick three elements from subtree of child B. It easily extends to more than two children.
4. It turns out that picking a specific number of elements from a subtree is desired to build larger solutions.
5. Hence, we should compute the minimum cost on a subtree for every possible number of elements, save them, them combine combinations from different children subtrees.
6. It looks like a dynamic programming state.
7. In addition, we should differentiate between "can use" coupon to "cannot use" coupon further in a subtree.
8. Combining solutions can be done in O(N) time per node. The idea is to So the total complexity is O(N^2).

Notes

The DP equation takes the sum of two previous DP values, and minimizes this over some set of pair of DP states. It makes sense to set the value initially to inf or an equivalent value. It turns out that setting the initial DP values to a value strictly larger than the largest budget (i.e 1e9) such that it doesn't overflow when multiplied by 2 works well because:

1. The inf value does not fit within any budget.
2. It will never overflow because we always minimize from inf and inf + inf will not overflow.

Using vector<vector<vector<int>>> for DP table caused MLE. Turns out that using vector for DP states has to be done cautiously because it might over-allocate.