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: