ShortestMissingSubsequences
SRM 766 · 2019-09-09 · by misof
Problem Statement
Aliens on the planet Htrae have G different bases in their DNA. In this problem, we will number the bases 0 through G-1.
You are given the DNA of an alien specimen: the
During an alien's life their DNA changes: some bases disappear (without changing order of the remaining ones). Hence, the future DNA is always a subsequence of the current DNA. For example, if the current DNA is {10, 20, 30, 40, 50}, one possible future DNA is {10, 40} and another one is {}.
Clearly, the set of possible future DNAs for our specimen is finite. Let I be its infinite complement: the set of DNAs such that our specimen cannot have them.
We are interested in two values:
- L = the length of the shortest DNA in I
- X = the number of DNAs of length L in I, modulo 10^9 + 7
Return { L, X }.
Use the following pseudocode to generate A:
A = Aprefix
state = last element of Aprefix
while length(A) < N:
state = (state * 1103515245 + 12345) modulo 2^31
A.append( state modulo G )
Notes
- As usual, the reference solution does not depend on the properties of the pseudorandom generator and it would work within the time limit for any other input of the same size.
Constraints
- G will be between 1 and 10^9, inclusive.
- N will be between 1 and 2,000,000, inclusive.
- Aprefix will have between 1 and 100 elements, inclusive.
- Each element of Aprefix will be between 0 and G-1, inclusive.
2
4
{1, 0, 0, 1}
Returns: {3, 5 }
The shortest impossible DNAs are {0,0,0}, {0,1,0}, {0,1,1}, {1,1,0}, and {1,1,1}.
5
4
{1, 0, 0, 1}
Returns: {1, 3 }
The shortest impossible DNAs are {2}, {3}, and {4}.
7
7
{0, 1, 2, 3, 4, 5, 6}
Returns: {2, 28 }
The shortest impossible DNAs have the form {x, y} where x >= y.
7
14
{0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6}
Returns: {2, 21 }
The shortest impossible DNAs have the form {x, y} where x > y.
3
10
{1, 2, 0}
Returns: {3, 6 }
The sequence A you should generate is {1, 2, 0, 0, 1, 2, 1, 2, 2, 2}. The six DNAs of length 3 this alien cannot have are {0, 0, 0}, {0, 1, 0}, {0, 2, 0}, {1, 1, 0}, {2, 1, 0}, and {2, 2, 0}.
Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ShortestMissingSubsequences with a public method vector<int> count(int G, int N, vector<int> Aprefix) · 113 test cases · 2 s / 256 MB per case