Contest Duration: - (local time) (100 minutes) Back to Home

## F - Programming Contest Editorial by evima

We can see that this problem is NP-hard, since it is a difficult version of the subset sum problem.

Let us focus on the fairly small $$N$$ ($$N \leq 40$$).

If you search all the combinations of tasks to solve, it takes $$O(2^N)$$ and it will TLE. Instead, we can use a technique called “meet-in-the-middle” searching.

1. Split a sequence $$A$$ into two so that the number of elements are halved. Let us call them $$B$$ and $$C$$.
2. Enumerate all the possible sums of combinations from $$B$$ and sort them, which we will call $$D$$. It takes $$O(N 2^{N/2})$$ time for this.
3. Brute force all the possible combinations from $$C$$ and obtain the maximum value, with $$B$$ combined. Here, the optimal choice of $$B$$ can be found by performing binary searching on $$D$$. The time complexity for these operations are $$O(N 2^{N/2})$$.

Now, the problem can be solved in a total of $$O(N 2^{N/2})$$ time.

Sample Code (C++): https://atcoder.jp/contests/abc184/submissions/18301274 Sample Code (Python): https://atcoder.jp/contests/abc184/submissions/18300926

We can improve each step so that the problem can be solved in a total of $$O(2^{N/2})$$ time.

Let $$D_i$$ be a sorted sequence, each of whose element is a possible sum of choices from $$B_1, B_2, \ldots, B_i$$. Initially, $$D_0 = [0]$$. $$D_x$$ can be obtained by merging $$D_{x-1}$$ and “$$D_{x-1}$$, each of whose element is added by $$B_x$$”. Since $$|D_0| + |D_1| + |D_2| + \cdots + |D_x| \leq 1 + 2 + 4 + \cdots + 2^x = O(2^x)$$, we can obtain $$D_{N/2}$$ in a $$O(2^{N/2})$$ time.

Enumerate all the possible sums of choices from $$B$$, enumerate all the possible sums of choices from $$C$$ too, and combine them with sliding windows, so that the problem can be solved in a total of $$O(2^{N/2})$$ time.

Sample Code (C++): https://atcoder.jp/contests/abc184/submissions/18301551 Sample Çode (Python): https://atcoder.jp/contests/abc184/submissions/18301408

posted:
last update: