## Monday, September 15, 2014

### 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)