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]
.
- An implicit graph can be built from the coupon dependencies.
- The graph is a tree rooted at 1.
- Enumerating the solution can be done exploring the tree.
- A recursive solution on the children's subtrees can be considered.
- 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 childB
. It easily extends to more than two children. - It turns out that picking a specific number of elements from a subtree is desired to build larger solutions.
- 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.
- It looks like a dynamic programming state.
- In addition, we should differentiate between "can use" coupon to "cannot use" coupon further in a subtree.
- Combining solutions can be done in O(N) time per node. The idea is to So the total complexity is O(N^2).
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:
- The
inf
value does not fit within any budget. - It will never overflow because we always minimize from
inf
andinf
+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.