TopCoder Statistics - Problem Statement

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.
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 }
53

7

11

40003

30

Returns: {5, 5 }
2

4001

17

1000003

200

Returns: {7, 1 }
0

6

12

1000209

2000

Returns: {781, 9 }
0

6

13

1000305

3000

Returns: {658, 2 }
0

6

13

1000338

3000

Returns: {663, 1 }
0

6

13

1000342

2900

Returns: {311, 1 }
0

6

13

1000344

3000

Returns: {41, 12 }
1

1

1

2

3000

Returns: {1500, 0 }
3

4

5

978951371

2756

Returns: {36, 12 }
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.
10

18

10

3672

12

Returns: {5, 180 }
18

2

4698

4999

12

Returns: {1, 75 }
10

18

6

4884

12

Returns: {5, 132 }
10

18

7

2714

12

Returns: {5, 118 }
53

13

9

65535

500

Returns: {244, 0 }
12

34

55

7890

123

Returns: {35, 4 }
0

1

12345678

1000000000

3000

Returns: {9, 82 }
0

1

1234567

999999999

100

Returns: {1, 1234567 }
961751977

961752983

961751491

961905521

3000

Returns: {83, 1 }
999999999

999999999

999999999

1000000000

3000

Returns: {1500, 0 }
982450801

982450981

982451161

982451333

3000

Returns: {65, 2 }
941084101

941093911

941101729

941482127

2500

Returns: {113, 1 }
941083987

941083993

941083987

941084531

1700

Returns: {349, 89 }
941083987

941083993

941083987

941084831

170

Returns: {71, 1604 }
941083987

941083993

941083991

941084821

1200

Returns: {413, 107 }
941083987

941083993

941084777

941088461

1700

Returns: {505, 71 }
2

7

941084303

941089453

2234

Returns: {854, 62 }
7

3

11

1000000000

30

Returns: {1, 25 }
2

7

941088167

941093551

2500

Returns: {173, 6 }
11

4003

7

4007

1000

Returns: {312, 1 }
2

19

37

941084201

2234

Returns: {21, 4 }
2

19

941089207

941092013

2500

Returns: {1054, 5 }
2

19

941089207

941092013

3000

Returns: {9, 1 }
2

7

2

9

3000

Returns: {1497, 0 }
2

7

2

941084983

3000

Returns: {1174, 10 }
5

55

555

5555

555

Returns: {255, 0 }
91

37

13

1000007

2222

Returns: {930, 1 }
53

13

9

65535

3000

Returns: {1464, 0 }
5

3

4

25

3000

Returns: {1500, 0 }
12

34

55

7890

3000

Returns: {1441, 0 }
1

2

3

12334455

3000

Returns: {1145, 1 }
12

34

55

29989

3000

Returns: {1231, 1 }
247830

423144

528351

100000000

3000

Returns: {1100, 0 }
7523

11111

1234

12345

3000

Returns: {1085, 0 }
5

199

817238

999666111

3000

Returns: {143, 4 }
3000

3000

3000

99999999

3000

Returns: {1300, 0 }
1

1000

0

100000007

3000

Returns: {87, 1 }
12

123

44

1000000000

3000

Returns: {390, 16 }
53

13

9

1165535

3000

Returns: {1200, 0 }
1

31

17

12345679

3000

Returns: {1093, 4 }
6456

456456456

546456456

1000000000

3000

Returns: {1098, 512 }
0

1

1

1000000000

3000

Returns: {1, 1 }
5

3

4

25234234

3000

Returns: {944, 2 }
123456789

777777779

888888889

987654321

3000

Returns: {583, 1 }
5

3453

345321

6574432

3000

Returns: {448, 0 }
5

1000

1000

1000000000

3000

Returns: {1498, 0 }
999999999

1

1

1000000000

3000

Returns: {1, 1 }
8

19

17

999999999

3000

Returns: {176, 1 }
12389823

12340934

58439581

939829834

3000

Returns: {316, 2 }
878782

1231154

78914542

92345677

3000

Returns: {219, 1 }
235

327

125

100090123

3000

Returns: {395, 1 }
14365109

2874294

93092422

999999997

3000

Returns: {266, 3 }
53

13

9

65535

2999

Returns: {1463, 0 }
999997777

1

1

1000000000

3000

Returns: {1, 1 }
999999999

987654321

987654327

1000000000

3000

Returns: {584, 8 }
345345

345

45345534

1000000000

3000

Returns: {1488, 0 }
12

34

55

123456789

3000

Returns: {503, 1 }
5

3

4

1000000000

3000

Returns: {662, 8 }
1

2

2

1000000000

3000

Returns: {1, 3 }
0

1

1

100000000

3000

Returns: {1, 1 }
12

34

55

999999999

3000

Returns: {38, 1 }
9876543

987654321

987654321

987654322

2997

Returns: {1498, 0 }
999999991

872341235

987654321

999999999

3000

Returns: {473, 9 }
53

2003

123314

1201231

3000

Returns: {1202, 0 }
0

0

0

3

3000

Returns: {1500, 0 }
1000000

1000000

1000000

10000000

3000

Returns: {1500, 0 }
999999999

999799951

999999999

1000000000

3000

Returns: {197, 1 }
100

789

422

1000000000

3000

Returns: {47, 18 }
5

21

31

10000007

3000

Returns: {235, 0 }
1

1

1

1000000000

3000

Returns: {1, 1 }
3

4

5

99987

3000

Returns: {1280, 1 }
53

31337

1337

65535

3000

Returns: {1496, 0 }
12

34

55

1000000000

3000

Returns: {500, 0 }
752752727

727737527

134537377

999999999

3000

Returns: {430, 9 }
21

214435

325326435

1000000000

3000

Returns: {1488, 0 }
999999999

1

999999999

1000000000

3000

Returns: {1, 1 }
12345678

1234567

12345

1000000000

3000

Returns: {198, 8 }
1

782

99

1000000000

3000

Returns: {1000, 0 }
78

12972351

2418255

111626124

3000

Returns: {669, 3 }
999999999

999999999

999999999

1000000000

55

Returns: {27, 0 }
2

997137

5

999999983

3000

Returns: {1, 4 }
0

0

1

1000000000

3000

Returns: {1499, 0 }
12345

37523

39727

999999937

3000

Returns: {6, 9 }
1

1

1

10

3000

Returns: {1500, 0 }
100

7

123

100000

3000

Returns: {1460, 0 }
65465

456546

456456

4564501

3000

Returns: {1428, 0 }
50000

50000

50000

1000000000

3000

Returns: {1499, 0 }
999887763

999887763

999887763

1000000000

3000

Returns: {657, 3 }
1

2

23213

222222

3000

Returns: {1476, 0 }
3948867

58976

487847855

909689084

3000

Returns: {311, 4 }
32133

197999997

213123213

997999999

3000

Returns: {134, 1 }
13

2354234

1371

1000000000

3000

Returns: {1250, 0 }
32767234

99991232

78231232

999999999

2999

Returns: {899, 121 }
17

2

11

1000000000

3000

Returns: {1, 28 }
453

125

5476

134123

3000

Returns: {1012, 0 }
1

31

17

999999997

3000

Returns: {174, 4 }
12341234

12341237

12341233

999999991

3000

Returns: {116, 6 }
999999998

9997

999999998

999999999

3000

Returns: {48, 3 }
9546

3546

134

100000000

2

Returns: {1, 33840704 }
946455541

1

1

1000000000

3000

Returns: {1, 1 }
999999999

1000000

1000000

1000000000

3000

Returns: {1499, 0 }
145

0

0

99999989

389

Returns: {194, 0 }
1234123

9871366

9163245

29999997

3000

Returns: {595, 3 }
99999

0

0

9999999

3000

Returns: {1499, 0 }
13

62381318

83219

1000000000

3000

Returns: {1484, 0 }
37894325

43214321

54325432

999999997

3000

Returns: {27, 7 }
10

1

0

1000

3000

Returns: {1500, 0 }

Statistics

Problem Statement for "KSubstring"

Problem Statement

Definition

Constraints

Examples