TopCoder problem "KSubstring" used in SRM 404 (Division I Level Two)



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

0)
    
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.
1)
    
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.
2)
    
53
13
9
65535
500
Returns: {244, 0 }
3)
    
12
34
55
7890
123
Returns: {35, 4 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8154

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12176&pm=8154

Writer:

boba5551

Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Problem categories:

Greedy, Simple Math, Sorting