Minimal Coverage
Contest: Codeforces Round 744 (Div. 3)
Difficulty rating: 2200
Tags: dp

You are given $$$n$$$ lengths of segments that need to be placed on an infinite axis with coordinates.

The first segment is placed on the axis so that one of its endpoints lies at the point with coordinate $$$0$$$. Let's call this endpoint the "start" of the first segment and let's call its "end" as that endpoint that is not the start.

The "start" of each following segment must coincide with the "end" of the previous one. Thus, if the length of the next segment is $$$d$$$ and the "end" of the previous one has the coordinate $$$x$$$, the segment can be placed either on the coordinates $$$[x-d, x]$$$, and then the coordinate of its "end" is $$$x - d$$$, or on the coordinates $$$[x, x+d]$$$, in which case its "end" coordinate is $$$x + d$$$.

The total coverage of the axis by these segments is defined as their overall union which is basically the set of points covered by at least one of the segments. It's easy to show that the coverage will also be a segment on the axis. Determine the minimal possible length of the coverage that can be obtained by placing all the segments on the axis without changing their order.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The next $$$2t$$$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — the number of segments. The second line of the description contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$1 \le a_i \le 1000$$$) — lengths of the segments in the same order they should be placed on the axis.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output format:
Print $$$t$$$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the minimal possible length of the axis coverage.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the third sample test case the segments should be arranged as follows: $$$[0, 6] \rightarrow [4, 6] \rightarrow [4, 7] \rightarrow [-2, 7]$$$. As you can see, the last segment $$$[-2, 7]$$$ covers all the previous ones, and the total length of coverage is $$$9$$$.

In the fourth sample test case the segments should be arranged as $$$[0, 6] \rightarrow [-2, 6] \rightarrow [-2, 2] \rightarrow [2, 7]$$$. The union of these segments also occupies the area $$$[-2, 7]$$$ and has the length of $$$9$$$.

Example input:
6
2
1 3
3
1 2 3
4
6 2 3 9
4
6 8 4 5
7
1 2 4 6 7 7 3
8
8 6 5 1 2 2 3 6

Example output:
3
3
9
9
7
8

Editorial:
One possible solution involves the method of dynamic programming. As a state of DP we will use the number of already placed segments $$$i$$$, and the distance $$$l$$$ from the "end" of the last segment to the current left boundary of the coverage, and in the DP we will store the minimal possible distance from the "end" of the last segment to the current right boundary of the coverage.
We can prove that the answer never exceeds $$$2 \cdot l_{\mathtt{max}}$$$, where $$$l_\mathtt{max} = \max(a)$$$ is the maximal length of the segments. To do this, let us define a region of length $$$2 \cdot l_{\mathtt{max}}$$$, specifically the segment $$$[-l_{\mathtt{max}}, l_{\mathtt{max}}]$$$. If the "end" of the last segment has a coordinate $$$x > 0$$$, we put the next segment to the left, otherwise, we put it to the right. With this algorithm, none of the "end" endpoints of the segments will go beyond the marked boundaries, because to do so, the segment must be placed from the coordinate of one sign beyond the boundary of the opposite sign, and thus must have a length greater than $$$l_{\mathtt{max}}$$$ which contradicts how we defined $$$l_{\mathtt{max}}$$$.
Using this fact, we will consider the DP $$$\mathtt{dp}_{i, l}$$$ for $$$0 \le i \le n$$$ and $$$0 \le j \le 2 \cdot l_{\mathtt{max}}$$$ as the minimum distance between the "end" of the $$$i$$$-th segment and the right boundary of the axis coverage of the first $$$i$$$ segments when the distance to the left boundary of the coverage equals to $$$l$$$. The "end of the $$$0$$$-th segment" here is the "beginning" of the first one, that is, the point $$$0$$$.
The base of DP is $$$\mathtt{dp}_{0, 0} = 0$$$, since when no segments are placed, the coverage boundaries and the current point $$$0$$$ are all coincident. Next, we consider the forward dynamic programming relaxation: for every $$$(i, l)$$$ there are two cases to consider, the case of the next segment being placed to the left and the case of it being placed to the right (value $$$r$$$ below refers to the distance to the right boundary of the coverage and is an alias for $$$\mathtt{dp}_{i, l}$$$):
• If a segment of length $$$a_{i + 1}$$$ is placed to the left side, then the new distance to the left boundary will be equal to $$$\max(0, l - a_{i + 1})$$$, and distance to the right boundary will always be $$$r + a_{i + 1}$$$, which gives us the relaxation formula $$$$$$\mathtt{dp}_{i + 1, \max(0, l - a_{i + 1})} \leftarrow \mathtt{dp}_{i, l} + a_{i + 1}$$$$$$
• If a segment of length $$$a_{i + 1}$$$ is placed to the right side, then the new distance to the right boundary will be equal to $$$\max(0, r - a_{i + 1})$$$, and distance to the left boundary will always be $$$l + a_{i + 1}$$$, which gives us the relaxation formula $$$$$$\mathtt{dp}_{i + 1, l + a_{i + 1}} \leftarrow \max(0, \mathtt{dp}_{i, l} - a_{i + 1})$$$$$$
The values in array $$$\mathtt{dp}$$$ can be calculated in ascending order by $$$i$$$. Then the answer for the problem can be found as the minimum sum of $$$l$$$ and $$$r$$$ in the last row of $$$\mathtt{dp}$$$, that is $$$\min\limits_{l} l + \mathtt{dp}_{i, l}$$$.
The time complexity is $$$\mathcal{O}(n \cdot l_{\mathtt{max}})$$$.