0
$\begingroup$

Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers cannot be reused.

Initial data. The first line contains two natural numbers N and K - desired sum and length of excluded number list. The second line lists the K distinct numbers that are excluded.

Results. Output the numbers a1 , . . . , am, whose sum is N and which satisfy the listed conditions. They can be listed in any order. If it's impossible to satisfy the conditions, output "IMPOSSIBLE".

Constraints. 1 ≤ N ≤ 1000 000 000, 0 ≤ K ≤ 1000 and all excluded number list members are between 1 and 1,000,000,000 inclusive.

This seems similar to the subset sum problem. I have implemented a tabular Dynamic Programming solution, however, that is not fast and memory-efficient enough. The time-complexity of my algorithm is O(N*(N-K)) while space-complexity is O(N).

Any ideas?

$\endgroup$
1
  • 1
    $\begingroup$ Did you faithfully reported the problem statement ? $\endgroup$
    – user16034
    Commented Aug 14, 2023 at 16:46

1 Answer 1

1
$\begingroup$

This is an instance of the subset sum problem. The set is the range of naturals up to $N$ from which you remove the excluded numbers.

$\endgroup$
1
  • $\begingroup$ Which means that either your solution is wrong, or the estimated complexity is wrong. $\endgroup$
    – user16034
    Commented Aug 14, 2023 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.