CircularSequence

Problem Statement

Plugin users: There is a picture in the problem statement.

Given a circular sequence of integers, calculate the maximum sum of a (contiguous) sequence of these numbers. You should also calculate how many different sequences yield this maximum sum. Two sequences are different if they don't contain the same elements from the original sequence (see example 1). At least one integer in the circular sequence will be positive (greater than zero).

For instance, consider the circular sequence in the picture below.

There are four different ways to select a sequence of integers so the sum becomes 19 (which is the maximum sum):

0 3 2 2 -3 3 1 -1 6 -1 -2 4 1 4
3 2 2 -3 3 1 -1 6 -1 -2 4 1 4
3 1 -1 6 -1 -2 4 1 4 -3 0 3 2 2
4 1 4 -3 0 3 2 2 -3 3 1 -1 6

The circular sequence will be generated by the following formula: (a, b, c, d and n are parameters)

	int seed = 0;
	for(int i = 0; i < n; i++)
	{
		seed = (seed * a + b) % 32768;
		int val =(seed * c) / 32768 - d;
		// val is the i'th value in the circular sequence
	}

Create a class CircularSequence containing the method maxSequence which takes ints a, b, c, d and n used as described above, and returns a int[] containing exactly two elements: The first element being the maximum sum, and the second element the number of different sequences yielding this sum (you can assume that this value won't exceed 2,000,000,000). Two sequences are different if they don't contain the same elements from the original sequence.

Definition

Class:

CircularSequence

Method:

maxSequence

Parameters:

int, int, int, int, int

Returns:

int[]

Method signature:

int[] maxSequence(int a, int b, int c, int d, int n)

(be sure your method is public)

Notes

• The parameter c determines the span of the integers while d determines the lower bound. The range of the integers will thus be between -d and -d+c-1, inclusive.

Constraints

• a and b will be between 0 and 32767, inclusive.
• c will be between 2 and 1000, inclusive.
• d will be between 0 and c-2, inclusive.
• n will be between 1 and 1,000,000, inclusive.
• At least one integer in the circular sequence will be greater than zero.
• There will be at most 2,000,000,000 different contiguous sequences yielding the maximum sum.

Examples

1. 8087

   1869

   10

   3

   15

   Returns: { 19,  4 }

   This is the example above.

2. 1234

   46

   2

   0

   5

   Returns: { 1,  11 }

   The generated sequence is {0, 1, 0, 0, 0}. The maximum sum is obviously 1. There are 11 ways to get this sum: 1 way to select a single element: {1} 2 ways to select two elements: {0, 1} and {1, 0} 3 ways to select three elements: {0, 0, 1}, {0, 1, 0} and {1, 0, 0} 4 ways to select four elements: {0, 0, 0, 1}, {0, 0, 1, 0}, {0, 1, 0, 0} and {1, 0, 0, 0} 1 way to select all five elements: {0, 0, 0, 0, 1} (or any rotation of this)

3. 4810

   8393

   20

   10

   18

   Returns: { 45,  1 }

   These parameters yield the circular sequence {-5, -5, 7, 5, 0, 8, 1, 0, 6, 0, 1, 7, -10, -5, 5, 5, 5, 5}. The maximum value is achieved by taking all elements except -10 and -5 at the near end.

4. 1943

   3184

   9

   5

   100000

   Returns: { 14,  195 }

5. 1

   10922

   3

   1

   16383

   Returns: { 1,  59645042 }

   The generated sequence looks like this: {-1, 0, 1, -1, 0, 1, -1, 0, 1, ... }, i.e. the sequence {-1, 0, 1} is repeated 5461 times. The maximum sum is obviously 1. There are 2 essentially different ways to get this sum: Start at a 0, end at a 1. There are 5461 0's to start at, and 5461 1's to end at, i.e. 54612 ways. Start at a 1, end at a 1. Again there are 54612 such ways. There are thus 2 * 54612 = 59645042 ways to get the sum 1.