UVa 10871

From Algorithmist
Jump to navigation Jump to search

10871 - Primed Subsequence[edit]

Summary[edit]

Use an algorithm with a sieve.

Explanation[edit]

First, we reduce the problem of finding the sum between two indices to by linearly summing the elements - . We can then find the sum between two indices by simply taking the difference - . Try out all possibilities of and , cohering to the problem specs, and it should run within reasonable time.

Notes[edit]

  • The worst case for the input is not as bad as the problem actually denotes.

Implementations[edit]

Input[edit]

3
5 3 5 6 3 8
5 6 4 5 4 12
21 15 17 16 32 28 22 26 30 34 29 31 20 24 18 33 35 25 27 23 19 21

Output[edit]

Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.