UVa 10930

From Algorithmist
Jump to navigation Jump to search

10930 - A-Sequence[edit]

Summary[edit]

Part of this problem is a standard Dynamic Programming problem - the Subset Sum problem. Using that, we can incrementally determine if any is the sum of two or more distinct earlier terms.

Explanation[edit]

Since each integer is less than or equal to 1000, we don't even have to keep track of integers greater than that - we just have to incrementally maintain (using Dynamic Programming) rather the list of numbers is reachable as the subset sum of the previous 's. If it is, then it is not an A-sequence, but if not, we incrementally run the DP algorithm for the current .

Input[edit]

2 1 2
3 1 2 3
10 1 3 16 19 25 70 100 243 245 306
3 1 2 4
4 1 2 4 8
5 1 3 9 27 81
6 1 2 3 4 5 6 
5 1 2 4 8 12 
5 1 5 7 9 12 
5 10 11 12 13 21 
5 1 2 4 12 8
5 1 3 5 7 13

Output[edit]

Case #1: 1 2
This is an A-sequence.
Case #2: 1 2 3
This is not an A-sequence.
Case #3: 1 3 16 19 25 70 100 243 245 306
This is not an A-sequence.
Case #4: 1 2 4
This is an A-sequence.
Case #5: 1 2 4 8
This is an A-sequence.
Case #6: 1 3 9 27 81
This is an A-sequence.
Case #7: 1 2 3 4 5 6
This is not an A-sequence.
Case #8: 1 2 4 8 12
This is not an A-sequence.
Case #9: 1 5 7 9 12
This is not an A-sequence.
Case #10: 10 11 12 13 21
This is not an A-sequence.
Case #11: 1 2 4 12 8
This is not an A-sequence.
Case #12: 1 3 5 7 13
This is not an A-sequence.