SuffixDecomposition | Topcoder Archive

Problem Statement

An array A is considered to be smaller than an array B (denoted A < B) if each element of A is strictly smaller than all the elements of B.

An array A can be decomposed into subarrays A1, A2, ... Ak, if and only if A = A1 + A2 + ... + Ak and A1 < A2 < â¦. < Ak. In words, the original array is the concatenation of the pieces (without any reordering) and each piece is smaller than the next one.

Let's define fun value f(A) of an array A as : f(A) = maximum number of subarrays that the array A can be decomposed into. Given an array S of length N, you need to find the sum of f(B), where B are all the possible suffixes of the given array S. In other words, given an array S, you need to find f(S[0..n - 1]) + f(S[1..n - 1]) + â¦.. f(S[n - 1..n - 1]).

You are given integers A0, X, Y, B0, X1, Y1, N and an integer array P. Use the pseudocode below to generate the array S.

A[0] = A0 for i = 1 to N-1: 	A[i] = (A[i-1] * X + Y) modulo 1812447359 B[0] = B0 for i = 1 to N-1: 	B[i] = (B[i-1] * X1 + Y1) modulo 1812447359 S = P for i = size(P) to N-1: 	S[i] = max(A[i], B[i])

Definition

Class:: SuffixDecomposition
Method:: findTotalFun
Parameters:: int[], int, int, int, int, int, int, int
Returns:: long
Method signature:: long findTotalFun(int[] P, int A0, int X, int Y, int B0, int X1, int Y1, int N)
(be sure your method is public)

Constraints

The length of P will be between 0 and min(N, 100) (inclusive)
Integers in P will be between 0 and 1812447358 (inclusive)
A0 will be between 0 and 1812447358 (inclusive)
X will be between 0 and 1812447358 (inclusive)
Y will be between 0 and 1812447358 (inclusive)
B0 will be between 0 and 1812447358 (inclusive)
X1 will be between 0 and 1812447358 (inclusive)
Y1 will be between 0 and 1812447358 (inclusive)
N will be between 1 and 200,000 (inclusive)

Examples

```
{3, 9, 5}
```
```
0
```
```
0
```
```
0
```
```
0
```
```
0
```
```
0
```
```
3
```
```
Returns: 4
```
Here, there are three possible suffixes {5}, {9, 5}, {3, 9, 5}. Now, f({5}) = 1, f({9,5}) = 1 (as it cannot be decomposed into more than one subarrays), f({3, 9, 5}) = 2 (the two-subarray decomposition will be {3}, {9, 5}). Hence, the total fun value is 1 + 1 + 2 = 4.
```
{10}
```
```
1
```
```
2
```
```
2
```
```
3
```
```
1
```
```
2
```
```
4
```
```
Returns: 8
```
Here, the array is {10, 5, 10, 22}. There are four possible suffixes : {22}, {10, 22}, {5, 10, 22}, {10, 5, 10, 22}. f({22}) = 1, f({10, 22}) = 2, f({5, 10, 22}) = 3, f({10, 5, 10, 22}) = 2. Hence, total fun = 1 + 2 + 3 + 2 = 8.
```
{}
```
```
1000001
```
```
1000001
```
```
1000001
```
```
5000001
```
```
5000001
```
```
5000001
```
```
4
```
```
Returns: 6
```
Here, the array is {5000001, 1344505193, 919789863, 999879289}. f({5000001, 1344505193, 919789863, 999879289}) = 2, f({1344505193, 919789863, 999879289}) = 1, f({919789863, 999879289}) = 2, f({999879289}) = 1. Hence, total fun value = 2 + 1 + 2 + 1 = 6.

{}

1812447358

1812447358

1812447358

Returns: 7

{}

Returns: 10

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.