PurpleSubsequences | Topcoder Archive

Problem Statement

The sequence S is a subsequence of T if we can obtain S from T by erasing some (possibly none) elements of T, while keeping the others in their original order. For example, {1,3,5} is a subsequence of {1,2,3,4,5}, but {1,4,3} is not.

The sequence S is called purple if it has a strictly increasing subsequence of length L. For example, {1,4,3,10,9} is purple if L=3 but it is not purple if L=4.

You are given the int[] A: a sequence of small positive integers. You are also given a very small positive int L. Count all distinct non-empty purple sequences that are subsequences of A.

Note that each sequence should only be counted once, even if it has multiple occurrences in A.

Definition

Class:: PurpleSubsequences
Method:: count
Parameters:: int[], int
Returns:: long
Method signature:: long count(int[] A, int L)
(be sure your method is public)

Constraints

A will contain between 1 and 60 elements, inclusive.
Each element of A will be between 1 and 20, inclusive.
L will be between 1 and 6, inclusive.

Examples

```
{4,7,4,7}
```
```
1
```
```
Returns: 11
```
All sequences are purple. The 11 purple subsequences of the given sequence are {4}, {7}, {4,4}, {4,7}, {7,4}, {7,7}, {4,4,7}, {4,7,4}, {4,7,7}, {7,4,7}, and {4,7,4,7}.
```
{1,1,2,2,3,3}
```
```
3
```
```
Returns: 8
```
```
{1,2,3,1,2,3}
```
```
3
```
```
Returns: 17
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.