Connection Status:
Competition Arena > RochesterSequence

RochesterSequence

TCO19 SRM 747 · 2019-01-09 · by misof

TCO19 SRM 747 · 2019-01-09 · by misof · Dynamic Programming, Sorting
Class Name: RochesterSequence
Return Type: int[]
Method Name: solve
Arg Types: (vector<int>, int, int, int, int)
Problem Statement

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:

  1. Going from 0 to x-1, each person picks one of the objects that haven't been picked so far.
  2. 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

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
0)
{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.

1)
{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}

2)
{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.

3)
{0}
1000
0
0
1
Returns: {1000, 1 }
4)
{47}
1000
3156353
3232535
1000000007
Returns: {256, 706709384 }
5)
{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.

Submissions are judged against all 42 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RochesterSequence with a public method vector<int> solve(vector<int> Sprefix, int n, int a, int b, int m) · 42 test cases · 2 s / 256 MB per case

Submitting as anonymous