PurpleSubsequences
TCO19 SRM 750 · 2019-01-09 · by misof
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
Note that each sequence should only be counted once, even if it has multiple occurrences in A.
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.
{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
{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
{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
Submissions are judged against all 20 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PurpleSubsequences with a public method long long count(vector<int> A, int L) · 20 test cases · 2 s / 256 MB per case