RochesterSequence | Topcoder Archive

Problem Statement

This problem has a nonstandard time limit: 4 seconds.

In a Rochester draft there are x people (numbered from 0 to x-1) and 2*x objects of different value. The purpose of the draft is that each person should acquire two of the objects. The draft works as follows:

Going from 0 to x-1, each person picks one of the objects that haven't been picked so far.
Going back from x-1 to 0, each person picks another object. (The very last pick is forced, as there is only one object left.)

A Rochester sequence is a sequence of length 2*x that represents the values of objects in the order in which they have been picked. A Rochester sequence is called nondecreasing ("NRS" for short) if the total values acquired by the people form a nondecreasing sequence. For example, {10, 5, 9, 9, 12, 7} is a NRS because 10+7 <= 5+12 <= 9+9.

You are given a sequence S. You want to erase some (possibly none) elements of S in such a way that what remains will be a NRS. Let L be the largest possible length of that NRS. Let W be the number of ways in which you can erase some elements and obtain a NRS of length L. Return a int[] with two elements: { L, W modulo (10^9 + 7) }.

The sequence S is given in the following format: You are given the int[] Sprefix and the ints n, a, b, and m. Use the following pseudocode to generate S:

for i = 0 to length(Sprefix)-1:
    S[i] = Sprefix[i]
for i = length(Sprefix) to n-1:
    S[i] = ( S[i-1] * a + b ) modulo m

Definition

Class:: RochesterSequence
Method:: solve
Parameters:: int[], int, int, int, int
Returns:: int[]
Method signature:: int[] solve(int[] Sprefix, int n, int a, int b, int m)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the pseudorandom generator.

Constraints

n will be between 2 and 1000, inclusive.
Sprefix will contain between 1 and n elements, inclusive.
Sprefix will contain at most 200 elements.
Each element of Sprefix will be between 0 and 10^9 + 6, inclusive.
m will be between 1 and 10^9 + 7, inclusive.
Each of a and b will be between 0 and m-1, inclusive.

Examples

```
{10, 5, 9, 9, 12, 7}
```
```
6
```
```
0
```
```
0
```
```
1
```
```
Returns: {6, 1 }
```
The example from the problem statement. As this is a NRS, the only optimal solution is to erase nothing and obtain a NRS of length 6.
```
{10, 20, 30, 40, 50, 60, 70}
```
```
7
```
```
0
```
```
0
```
```
474747
```
```
Returns: {6, 5 }
```
There are five valid ways to erase a single element and obtain a NRS of length 6. Note that the following are not NRSs: {10, 20, 30, 40, 50, 70} {10, 20, 30, 40, 60, 70}
```
{64, 32, 16, 8, 4, 2, 1}
```
```
7
```
```
0
```
```
0
```
```
1
```
```
Returns: {2, 21 }
```
Here the optimal solution is to erase any five of these seven elements. There are 21 ways to do so.
```
{1}
```
```
10
```
```
1000
```
```
1
```
```
1000000007
```
```
Returns: {8, 10 }
```
Watch out for integer overflow when generating the sequence S. This sequence S looks as follows: 1 1001 1001001 1000994 993994 993994001 993994050 994043050 43043043 43042700.

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.