SimilarSequences
TCO13 Round 3B · 2013-02-19 · by gojira_tc
TCO13 Round 3B · 2013-02-19 · by gojira_tc · Brute Force, Sorting, String Manipulation
Problem Statement
Problem Statement
Two sequences A and B are called similar if they are both non-empty, have the same length, and have the following property:
we can obtain two identical sequences by deleting one element of A and one element of B.
(The deleted elements do not necessarily have to have the same index.
The order of the remaining elements in each sequence has to be preserved.)
You are given aint[] seq and a int bound.
Consider all sequences such that each element is an integer between 1 and bound, inclusive.
Count how many of such sequences are similar to seq.
Return this count modulo 1,000,000,009.
You are given a
Constraints
- seq will contain between 1 and 40 elements, inclusive.
- bound will be between 1 and 1,000,000,000, inclusive.
- Each element in seq will be between 1 and bound, inclusive.
Examples
0)
{1, 1}
3
Returns: 5
We need to count the number of sequences which consist of elements in [1, 3] and are similar to (1, 1). These sequences are (1, 1), (1, 2), (2, 1), (1, 3) and (3, 1).
1)
{1, 2}
2
Returns: 4
Any valid sequence is similar to (1, 2).
2)
{999999999}
1000000000
Returns: 1000000000
Note that after deleting the elements from the sequences, the resulting sequences may be empty.
3)
{1, 2, 3, 4, 5}
5
Returns: 97
4)
{5, 8, 11, 12, 4, 1, 7, 9}
1000000000
Returns: 999999363
Submissions are judged against all 151 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SimilarSequences with a public method int count(vector<int> seq, int bound) · 151 test cases · 2 s / 256 MB per case