# UVa 10871

Jump to navigation
Jump to search

## Contents

## 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.