ShortestMissingSubsequences | Topcoder Archive

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 int[] A with N elements.

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) &lt; N:
    state = (state * 1103515245 + 12345) modulo 2^31
    A.append( state modulo G )

Definition

Class:: ShortestMissingSubsequences
Method:: count
Parameters:: int, int, int[]
Returns:: int[]
Method signature:: int[] count(int G, int N, int[] Aprefix)
(be sure your method is public)

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.

Examples

```
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.

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

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.