CF 1807G1 - Subsequence Addition (Easy Version)

Rating: 1100
Tags: brute force, data structures, dp, greedy, implementation, sortings
Solve time: 29s
Verified: no

Solution

Problem Understanding

We start with an array containing a single element [1]. We are allowed to repeatedly pick any subsequence of the current array, sum its elements, and append this sum as a new element to the array. The goal is to determine if a given array c can be obtained through some sequence of these operations.

The input consists of multiple test cases. Each test case provides the target array c of length n with elements up to 5000. The sum of n over all test cases does not exceed 5000, which means we can afford algorithms with overall complexity around O(n log n) or O(n^2) per test case.

A naive approach might try to simulate all possible sequences of operations. For instance, starting from [1], we could try every subsequence sum we can append. However, the number of subsequences grows exponentially with the size of the array, so this approach quickly becomes infeasible even for n around 20 or 30.

An edge case occurs when the target array has only one element greater than 1, for example [2]. The initial array [1] cannot directly produce [2] as its sole element because any operation would append a new element without removing 1, so the array cannot reduce in size. Another subtle case is when all elements are 1, which is trivially achievable by repeatedly summing [1] subsequences.

Approaches

The brute-force solution is to simulate all sequences of operations starting from [1]. At each step, we choose every non-empty subsequence, append its sum, and recursively try to reach the target array. This works in principle but has a complexity exponential in n because each array of length k has 2^k - 1 non-empty subsequences. For n up to 5000, this is completely infeasible.

The key insight is that the operations always produce sums of existing elements. This means the multiset of elements in the array must always be less than or equal to the sum of all previous elements. In other words, if we sort the target array in descending order, the largest element must be obtainable as the sum of some subsequence of smalle