Statistics

Problem Statement for "PurpleSubsequences"

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

  1. {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}.

  2. {1,1,2,2,3,3}

    3

    Returns: 8

  3. {1,2,3,1,2,3}

    3

    Returns: 17

  4. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

    6

    Returns: 1152898822228099896

  5. {12, 3, 14, 18, 15, 19, 11, 9, 17, 13, 13, 20, 2, 14, 1, 4, 1, 9, 16, 18, 1, 11, 19, 14, 8, 8, 17, 17, 12, 15, 8, 2, 18, 12, 12, 20, 11, 18, 19, 7, 8, 2, 5, 11, 4, 12, 19, 13, 17, 18, 9, 4, 8, 11, 7, 16, 4, 14, 20, 12}

    6

    Returns: 268574657113953744

  6. {10, 8, 18, 9, 12, 18, 19, 2, 16, 10, 19, 13, 9, 17, 8, 20, 4, 7, 13, 16, 9, 20, 18, 5, 15, 1, 6, 18, 3, 3, 9, 17, 20, 18, 16, 14, 12, 2, 20, 9, 20, 17, 16, 11, 1, 19, 8, 7, 12, 14, 6, 6, 16, 7, 5, 4, 5, 19, 12, 17}

    6

    Returns: 389631254955639148

  7. {13, 4, 9, 15, 1, 4, 14, 3, 12, 1, 9, 2, 5, 6, 17, 16, 7, 16, 17, 15, 19, 19, 1, 3, 6, 5, 18, 11, 2, 20, 8, 2, 13, 4, 1, 3, 10, 2, 18, 10, 8, 20, 18, 5, 18, 19, 9, 20, 19, 3, 19, 16, 11, 18, 2, 4, 14, 14, 12, 10}

    6

    Returns: 300866071514810752

  8. {19, 16, 20, 5, 3, 17, 4, 15, 15, 1, 14, 19, 17, 3, 10, 16, 17, 4, 8, 12, 11, 6, 15, 1, 19, 4, 15, 15, 9, 18, 1, 18, 7, 10, 2, 9, 18, 16, 13, 3, 4, 17, 19, 20, 16, 18, 12, 19, 10, 14, 7, 3, 4, 17, 10, 13, 11, 18, 12, 4}

    6

    Returns: 481756041593597088

  9. {3, 20, 14, 12, 2, 12, 19, 2, 13, 9, 9, 7, 10, 7, 15, 10, 15, 15, 11, 2, 5, 19, 16, 1, 1, 14, 15, 17, 15, 20, 9, 10, 4, 10, 4, 6, 14, 11, 16, 14, 8, 17, 19, 17, 9, 11, 18, 1, 20, 13, 20, 19, 20, 20, 15, 20, 18, 6, 13, 2}

    6

    Returns: 61251162319144348

  10. {6, 20, 6, 20, 3, 16, 14, 2, 8, 15, 6, 20, 13, 1, 20, 5, 3, 18, 13, 1, 13, 16, 15, 12, 4, 17, 13, 4, 3, 14, 14, 18, 4, 20, 6, 16, 16, 15, 20, 3, 13, 17, 17, 11, 14, 7, 11, 13, 3, 5, 16, 11, 4, 9, 16, 3, 12, 1, 13, 20}

    6

    Returns: 218607137579352974

  11. {3, 20, 8, 17, 7, 17, 9, 10, 17, 20, 4, 18, 2, 10, 6, 16, 8, 13, 20, 16, 1, 19, 13, 20, 8, 18, 12, 4, 11, 3, 6, 19, 4, 8, 6, 3, 5, 17, 6, 6, 3, 3, 5, 19, 13, 12, 4, 14, 10, 18, 8, 12, 3, 11, 4, 2, 7, 18, 5, 11}

    6

    Returns: 372711124215178096

  12. {3, 11, 14, 17, 18, 19, 12, 17, 17, 14, 15, 14, 14, 16, 1, 7, 11, 2, 20, 14, 4, 15, 19, 4, 4, 11, 14, 2, 11, 6, 14, 16, 17, 16, 17, 4, 8, 7, 1, 18, 16, 11, 5, 6, 10, 3, 2, 20, 10, 2, 20, 1, 9, 12, 7, 18, 7, 12, 12, 5}

    6

    Returns: 116980655733920012

  13. {7, 15, 20, 2, 10, 20, 10, 14, 4, 14, 14, 12, 16, 9, 2, 19, 16, 8, 9, 13, 2, 1, 13, 7, 14, 12, 17, 3, 12, 20, 11, 15, 3, 3, 16, 9, 3, 6, 7, 8, 14, 16, 7, 10, 1, 4, 20, 19, 1, 9, 18, 7, 18, 12, 16, 7, 11, 13, 2, 19}

    6

    Returns: 249655692031876294

  14. {14, 11, 18, 12, 1, 4, 1, 10, 2, 20, 7, 17, 20, 1, 2, 18, 19, 2, 13, 15, 7, 3, 9, 13, 17, 12, 2, 3, 10, 20, 10, 2, 20, 15, 15, 14, 11, 3, 9, 14, 12, 4, 13, 13, 6, 10, 1, 1, 19, 19, 7, 5, 18, 8, 3, 1, 14, 14, 14, 14}

    6

    Returns: 61713373450497536

  15. {1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10}

    6

    Returns: 1124185827456106271

  16. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

    6

    Returns: 512381999006784876

  17. {3, 6, 10, 4, 11, 17, 7, 11, 19, 4, 3, 16, 20, 15, 18, 6, 16, 17, 10, 6, 12, 14, 4, 7, 14, 3, 16, 3, 1, 15, 2, 3, 4, 12, 14, 6, 8, 4, 17, 1, 6, 14, 1, 7, 8, 9, 1, 2, 18, 6, 20, 5, 17, 8, 3, 1, 11, 3, 16, 20 }

    4

    Returns: 655198429158065318

  18. {12, 10, 5, 10, 14, 10, 2, 5, 13, 8, 1, 1, 13, 17, 20, 9, 10, 8, 4, 2, 18, 17, 6, 11, 7, 16, 3, 12, 19, 14, 10, 19, 15, 13, 7, 12, 8, 13, 10, 12, 15, 19, 8, 18, 12, 7, 7, 17, 20, 18, 8, 4, 10, 2, 8, 17, 6, 11, 11, 15 }

    6

    Returns: 272925743322442612

  19. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    6

    Returns: 1152898822228099896

  20. {2, 4, 6, 6, 10, 19, 18, 15, 8, 7, 12, 1, 1, 17, 12, 9, 16, 5, 4, 1, 1, 13, 4, 13, 12, 9, 16, 1, 1, 9, 8, 5, 8, 17, 12, 1, 1, 17, 12, 9, 16, 5, 4, 1, 1, 13, 4, 13, 12, 9, 16, 1, 1, 9, 8, 5, 8, 17, 12, 1 }

    6

    Returns: 54187582977443888

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.
This problem was used for: