KSubstring | Topcoder Archive

Problem Statement

You are given numbers A0, X, Y, M and n. Generate a list A of length n using the following recursive definition:
A[0] = A0
A[i] = (A[i - 1] * X + Y) MOD M (note that A[i - 1] * X + Y may overflow 32-bit integer)

Let s(i, k) be a sum of k consecutive elements of the list A starting with the element at position i (0 indexed). More formally, s(i, k) = A[i] + A[i + 1] + ... + A[i + k - 1].
Your task is to find the smallest difference between s(i, k) and s(j, k) (where difference is defined as abs(s(i, k) - s(j, k))) such that i + k <= j. In other words, you must find the smallest difference between two subsequences of the same length that do not overlap.
Call this smallest difference val, and return a int[] containing exactly two elements. The first element should be k, and the second element should be val. If there are multiple solutions with the same val, return the one among them with the highest k.

Definition

Class:: KSubstring
Method:: maxSubstring
Parameters:: int, int, int, int, int
Returns:: int[]
Method signature:: int[] maxSubstring(int A0, int X, int Y, int M, int n)
(be sure your method is public)

Constraints

M will be between 1 and 1,000,000,000, inclusive.
A0 will be between 0 and M-1, inclusive.
X will be between 0 and M-1, inclusive.
Y will be between 0 and M-1, inclusive.
n will be between 2 and 3,000, inclusive.

Examples

```
5
```
```
3
```
```
4
```
```
25
```
```
5
```
```
Returns: {2, 1 }
```
The elements of the list are {5, 19, 11, 12, 15}. There is no way to find two subsequences that have equal sums and do not overlap, so there is no way to obtain 0 as a difference. |s(0, 2) - s(2, 2)| = 1 and that is the minimal difference. Note that |s(2, 1) - s(3, 1)| is also 1, but we don't choose these subsequences because they have a lower value for k.
```
8
```
```
19
```
```
17
```
```
2093
```
```
12
```
```
Returns: {5, 161 }
```
The elements of the list are {8, 169, 1135, 652, 1940, 1296, 1618, 1457, 491, 974, 1779, 330}. The smallest difference is |s(1, 5) - s(7, 5)| = 161.
```
53
```
```
13
```
```
9
```
```
65535
```
```
500
```
```
Returns: {244, 0 }
```
```
12
```
```
34
```
```
55
```
```
7890
```
```
123
```
```
Returns: {35, 4 }
```

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.