KSubstring

SRM 404 · 2008-06-05 · by boba5551

SRM 404 · 2008-06-05 · by boba5551 · Greedy, Simple Math, Sorting

Show categories

Class Name: KSubstring

Return Type: int[]

Method Name: maxSubstring

Arg Types: (int, int, int, int, int)

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.

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.

7
37
23
4007
23
Returns: {4, 2 }

7
37
23
4003
500
Returns: {231, 1 }

7
37
23
4003
700
Returns: {268, 1 }

1
32
1
65536
1700
Returns: {848, 0 }

14)

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.

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

Coding Area

Language: C++17 · define a public class KSubstring with a public method vector<int> maxSubstring(int A0, int X, int Y, int M, int n) · 122 test cases · 2 s / 256 MB per case