a bit of codeforces: Round #213 (Div. 2)

Codeforces Round #213 (Div. 2)

Problem D
D. Free Market

Summary:
Given \(n\) elements with values \(a_1, a_2, \ldots, a_n\), starting from \( S_0 = \{ \} \), define sum(\(S_i\)) the sum of elements in \(S_i\), and in each step \(i\) we can add and/or remove elements from \(S_i\) to form \(S_{i+1}\) such sum(\(S_{i+1}\)) - sum(\(S_i\)) is less then D. Find the maximum sum(\(S\)) and the minimum steps needed to construct the set.
Constraint: \(n \leq 50, D \leq 10^4, a_i \leq 10^4\).

Solution:
This is a cool problem.
The idea is by maintaining an array s[0 .. 500000] which ranges all the possible sum of elements (maximum is \(50 \times 10^4 = 500000\)). Iterating through \(a_i\), we can find all possible sum \(i\) reachable and mark s[i] = 1 if the state is achievable and 0 otherwise. After constructing such array, starting from 0, we can find a path to the farthest element reachable, with the constraint that at position \(i\), we can only transit to another state \(j\) iff \(|i-j| \leq D\). (You can also see this transition as an edge on a graph)